图的定义及性质

图的概念

定义1：
一个图可以被表示为，其中是大小为的节点的集合，是大小为的边的集合。
图的大小定义为图的节点数量，即。

定义2:
给定一个图，对应的邻接矩阵可以表示为。邻接矩阵的第i行第j列的元素表示节点和的连接关系。具体来讲，如果和相邻，则，否则则。

图的性质

度：节点的度定义为图中与节点相关联的边的数目。

领域：与节点相邻的节点的集合。

途径：节点到节点所经过的所有节点和边的集合，且为节点和边的交替序列。

迹：边各不同的途径，可以节点出现相同的情况。

路：节点各不相同的途径。

子图：图的子图由节点集的子集和边的子集组成。此外，集合必须包含集合涉及的所有节点。

连通分量：如果图的子图中任意一对节点之间都至少存在一条路，且子图中的节点不与非子图中的节点相连，那么该子图就是一个连通分量。

连通图：如果一个图只有一个连通分量，那么该图即为连通图。

最短路：节点到节点的最短路的长度。

直径：图中最长的最短路的长度。

中心性

度中心性
核心思想：如果有许多其他节点连接到某个节点，那么后者可以被认为是重要的。
(1)

特征向量中心性
核心思想：度的中心性认为相邻节点的贡献度一致，然而相邻节点的本身的重要性是不同的。
(2)
(3)
由公式2和公式3可得，节点的中心性为邻接矩阵的特征向量，一般选择最大特征值对应的特征向量。

Katz中心性
核心思想：Katz中心性认为节点的中心性，不仅仅与相邻节点的中心性有关，也与自身的中心性有关。
(4)
其中， 为常数。
(5)
其中， 为向量。
(6)
一般选择。

介数中心性
核心思想：如果有许多路径通过同一节点，那个该节点较为重要。
(7)