作者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/cn.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