[線代] clique 問題

[anoymouse (沒有暱稱)]

For an incidence matrix A with related matrix B defined by Bij = 1 if
i is related to j and j is related to i, and Bij = 0 otherwise, prove that
i belongs to a clique if and only if (B3)ii > 0.

解答:

Let G = G(B) be the graph associated to the symmetric matric B.
And (B3)ii is the number of walk of length 3 from i to i. If i is in some
clique, then there must be a walk of length 3 from i back to i since a clique must
have number of vertex greater than 3.
不是三個點就好了嗎? 為什麼是>3?

Conversely, if (B3)ii is greater than zero,
this means there is at least one walke of length 3 from i to i, say
i → j → k → i. Note that i, j, and k should be different vertices since
length is 3 and there is no loop.
i → j → k → i → j → k → i ... 這樣不算loop?
So i, j, and k must be a triangle, this
means three vertices adjacent to each others. So i is contained in {i, j, k}
and so contained in some clique.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.136.42.73 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1690807644.A.ABC.html
推 wrvuxci     : clique只要三個點就好，我想是的，這樣邏輯前後是通
→ wrvuxci     : 順的，只要你課堂上/書上是這樣定的就沒問題(我學的
→ wrvuxci     : 定義沒有點數的限制，但不同書的定義略有不同不奇怪
→ wrvuxci     : )，然後loop是只一個有向邊的兩端是同一點，也就是
→ wrvuxci     : i→i