[線代] clique 問題
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