发表自话题：512的暗示
图的一些基本知识：图，邻居，度矩阵，邻接矩阵
https://blog.csdn.net/luzaijiaoxia0618/article/details/104718146/
关联矩阵，拉普拉斯矩阵
https://blog.csdn.net/luzaijiaoxia0618/article/details/104720948
图有节点V和边E,边可以是有向的和无向的两种。两个节点之间通过边形成邻居关系。跟某一节点相关联的边的数量形成该节点的度。
——————————————————————
无向图分析
上图中节点为V（v1,v2,v3,v4,v5）.
节点间边的关系形成邻接矩阵A
V1的邻居关系：v1v1, v1v2, v1v3, v1v4, v1v5
V2的邻居关系：v2v1, v2v2, v2v3, v2v4, v2v5
V3的邻居关系：v3v1, v3v2, v3v3, v3v4, v3v5
V4的邻居关系：v4v1, v4v2, v4v3, v4v4, v4v5
V5的邻居关系：v5v1, v5v2, v5v3, v5v4, v5v5
上图节点之间关系没有方向，可以双向表示，邻接矩阵的元素表示如下
0,1,0,0,0
1,0,1,0,1
0,1,0,1,1
0,0,1,0,1
0,1,1,1,0
和每个节点相关联的边的数量叫做度，在矩阵中放在对角位置上。邻接矩阵每一行有几个1，就表示该节点上的度为几。度矩阵D的元素可以表示如下
1,0,0,0,0,
0,3,0,0,0,
0,0,3,0,0
0,0,0,2,0
0,0,0,0,3
拉普拉斯矩阵 = 度矩阵 - 邻接矩阵，表示如下：
1, -1, 0, 0, 0
-1, 3,-1, 0,-1
0, -1, 3,-1,-1
1, 1,-1, 2,-1
1, -1,-1,-1, 3
拉普拉斯矩阵每一行的和均为0
拉普拉斯矩阵是半正定矩阵；
特征值中0出现的次数就是图连通区域的个数；
最小特征值是0，对应的特征向量为全1列向量，因为拉普拉斯矩阵每一行的和均为0（待解）
——————————————————————
有向图分析
上图中节点为V（v0,v1,v2,v3,v4,v5）.
节点间边的关系形成邻接矩阵A
V0的邻居关系：v0v0, v0v1, v0v2, v0v3, v0v4
V1的邻居关系：v1v0, v1v1, v1v2, v1v3, v1v4
V2的邻居关系：v2v0, v2v1, v2v2, v2v3, v2v4
V3的邻居关系：v3v0, v3v1, v3v2, v3v3, v3v4
V4的邻居关系：v4v0, v4v1, v4v2, v4v3, v4v4
上图节点之间关系有向邻接矩阵的元素表示如下
0,1,0,0,0
1,0,0,0,1
0,1,0,1,0
1,0,0,0,0
0,0,0,1,0
和每个节点相关联的边的数量叫做度，在矩阵中放在对角位置上。邻接矩阵每一行有几个1，就表示该节点上的度为几。度矩阵D的元素可以表示如下
1,0,0,0,0,
0,2,0,0,0,
0,0,2,0,0
0,0,0,1,0
0,0,0,0,1
关联矩阵
节点N和边数量M形成的矩阵。
有向图的关联矩阵，两个节点之间有边，一共形成M条边。多某节点而言，若节点在边的起点，则矩阵元素值为1，若节点在边的终点，则矩阵值为-1，若某条边和该节点没有关系，则矩阵元素为0.
上图中，四个节点V1，V2，V3，V4,三条边e1,e2,e3,其中
v1是e1,e2的起点，和e3无关联。矩阵元素为（1,1,0）
v2是e2的终点，和e1、e3无关联。矩阵元素为（0,-1,0）
v3是e1,e3的终点，和e2无关联。矩阵元素为（-1,0,-1）
v4是e3的起点，和e1,e2无关联。矩阵元素为（0,0,1）
四个节点和三条边形成的矩阵如下
节点/边 e1 e2 e3
v1 1, 1, 0
v2 0, -1, 0
v3 -1, 0, -1,
v4 0, 0, 1
可以看出，每一条边和某一个节点是起点关系1，势必和另一个节点是终点关系-1。因此，每一条边作为一个列，每列元素之和为0
矩阵中任一行可以从其他 n-1 行中导出，即只有 n-1 行是独立的（待解）
——————————————————————————
无向图的关联矩阵
节点/边 e1 e2 e3 e4 e5 e6 e7
v1 1, 0, 0, 0, 1, 0, 1
v2 1, 1, 0, 0, 0, 0, 0
v3 0 , 1, 1, 0, 0, 1, 1
v4 0, 0, 1, 1, 0, 0, 0
v5 0, 0, 0, 1, 1, 1, 0
列元素作为边的表示，有且只有两个1；
行元素作为节点的表示，元素之和表示该节点的边的数量度；
某一行所有元素为0，则表示该节点不与其他节点有关联，是孤立点。
重边所对应的列元素完全相同（待解）
—————————————————————————
标签组：[数学] [关联矩阵] [矩阵图] [拉普拉斯] [相关矩阵] [矩阵]
