作者anoymouse (沒有暱稱)
看板Math
標題[線代] clique 問題
時間Mon Jul 31 20:47:22 2023
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://webptt.com/m.aspx?n=bbs/Math/M.1690807644.A.ABC.html
1F：推 wrvuxci : clique只要三個點就好，我想是的，這樣邏輯前後是通 09/16 07:25
2F：→ wrvuxci : 順的，只要你課堂上/書上是這樣定的就沒問題(我學的 09/16 07:26
3F：→ wrvuxci : 定義沒有點數的限制，但不同書的定義略有不同不奇怪 09/16 07:27
4F：→ wrvuxci : )，然後loop是只一個有向邊的兩端是同一點，也就是 09/16 07:28
5F：→ wrvuxci : i→i 09/16 07:28