图论基础
最后更新于
这有帮助吗？
定义图$(graph) \ or$ 网络$(network)$ $G=(V,E)$，其中集合$V$的元素称为顶点$(vertex) \ or $ 结点$node$，集合$E$的元素称为联系$(links)\ or$ 边$(edge)$。
网络与图：
网络：通常是指真实的系统
网络、社交网络
图：网络的数学表示
网络图，社交图，知识图
如果给图的每条边规定一个方向，那么得到的图称为有向图。相反，边没有方向的图称为无向图。
无向图：
有向图：
与$i$结点关联的边的数目称为$i$的度。而在有向图中，从一个顶点出发的边数称为该点的出度，而指向一个顶点的边数称为该点的入度。
无向图：
在无向图中，结点的度就是与该结点相连的边的数目。
例如：$k_A=4$
有向图：
在有向网络中，定义一个入度和出度，节点的(总)度是输入度和输出度的总和。
若图$G^{'}=(v',E')$的顶点集合边集分别是另一个图$G=(V,E)$的顶点集的子集和边集的子集，即$V'\subseteq V$，且$E'\subseteq E$，则称图$G'$是图$G$的子图。
在图$G=(V,E)$中，若从顶点vi出发，沿着一些边经过一些顶点$v_{p1},v_{p2},\cdots,v_{pm}$，到达顶点$v_j$，则称边序列$P_{ij}=(e_{v_iv_{p1}},e_{v_{p1}v_{p2}},\cdots,,e_{v_{pm}v_{j}})$为从顶点$v_i$到顶点$v_j$的一条路径（$Path$，也可称为通路），其中$P_{ij}=(e_{v_iv_{p1}},e_{v_{p1}v_{p2}},\cdots,,e_{v_{pm}v_{j}})$为图$G$中的边。
路径的长度：路径中边的数目通常称为路径的长度$L(P_{ij})=|P_{ij}|$。
顶点的距离：若存在至少一条路径由顶点$v_i$到达顶点$v_j$，则定义$v_i$到$v_j$的距离为：
也即两个顶点之间的距离由它们的最短路径的长度决定。我们设$d(v_i,v_j) = 0$，节点 到自身的距离为$0$。
$k$阶邻居：若$d(v_i,v_j) = k$，我们称$v_j$为$v_i$的$k$阶邻居。
$k$阶子图（k-subgraph）：我们称一个顶点$v_i$的$k$阶子图为：
举例：图中的阴影部分是顶点$V_1$的2阶子图
$N$个节点上的无向图的最大边数为：
一个边数为$E =E_{max}$的无向图称为完全图（每两个顶点都有$1$条边相联的简单图称为完全图），它的平均度数是$N-1$。
节点可以被分成两个不相交集$U$和$V$的图每条链路将$U$中的一个节点连接到$V$中的一个节点； 也就是说，$U$和$V$是独立的集合$(U \cap V = \oslash)$。
如果$U$的顶点与$V$的顶点每个都邻接，则称为完全二部图。
在实际应用中，可以通过二部图进行链路预测：
通过$U$与$V$之间的关系，预测出$U$与$V$内部边的链接情况。
采用一个大小为$V\times V$的矩阵$A$，对于有权图，$A_{ij}$可以表示$V_i$到$V_j$的边的权重，如果是无权图，则可设为$1$表示存在边，$0$表示不存在边。因此邻接矩阵的表示相当的直观，而且对于查找某一条边是否存在、权重多少非常快。但其比较浪费空间，对稠密图（$E>>V$）来说，会比较适合。
无向图的矩阵是对称的，有向图的矩阵可能不对称。
无向图的邻接矩阵属性：
有向图的邻接矩阵属性：
边表
将图表示为一组边：
邻接列表
如果矩阵是稀疏矩阵，采用邻接列表则能够快速检索给定节点的所有邻居。
现实世界中的网络大多数都是稀疏的$(E<<E_{max})$
边的属性
权重(如通讯频率)
排名(最好的朋友，第二好的朋友…)
类型(朋友、亲戚、同事)
标志:朋友vs敌人，信任vs不信任
属性取决于图的其余部分的结构:共同好友的数量
更多类型的图
循环图：
多图：
设关联矩阵$B\in R^{N×M}$来描述节点与边之间的关联，定义如下：
连接(无向)图：任意两个顶点都可以被一条路径连接起来。
如果擦掉了绿色颜色的边缘,那么这个图形就会变成不连通的图:如果擦掉了蓝色颜色的结点,那么这个图形就会断开连接，也会变成不连通的图。
不连通图：是由两个或多个连通子图组成的。
强连通图：在有向图$G$中，如果两个顶点$v_i,$$v_j$间$(v_i>v_j)$有一条从$v_i$到$v_j$的有向路径，同时还有一条从$v_j$到$v_i$的有向路径，则称两个顶点强连通$(strongly\ connected)$。如果有向图$G$的每两个顶点都强连通，称$G$是一个强连通图。有向图的极大强连通子图，称为强连通分量$(strongly\ connected\ components)$。
$e.g.$：$A-B-C$就构成了强连通图。
弱连通图：定义对于有向图 $G$ ，将所有的有向边替换为无向边得到图$G$的基图，若图$G $的基图是连通的，则称图$ G $是弱连通图。
同构图：是指图中的节点类型和关系类型都仅有一种。
异构图：是指图中的节点类型或关系类型多于一种，与同构图相反。
属性图：相较于异构图，属性图给图数据增加了额外的属性信息。
非显示图：是指数据之间没有显示地定义出关系，需要依据某种规则或计算方式将数据的关系表达出来，进而将数据当成一种图数据进行研究。比如计算机3D视觉中的点云数据，如果将节点之间的空间距离转换成关系的话，点云数据就成了图数据。
图的遍历是指从图中的某一顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的遍历主要有两种算法：深度优先搜索（DFS，Depth-First-Search）和广度优先搜索（BFS，Breadth-First-Search）。图的遍历是一种重要的图检索手段，深度优先搜索与广度优先搜索给出了相应的算法基础。
深度优先搜索是一个递归算法，有回退过程。其算法思想是：从图中某一顶点$v_i$开始，由$v_i$出发，访问它的任意一个邻居$w_1$；再从$w_1$出发，访问$w_1$的所有邻居中未被访问过的顶点$w_2$；然后再从$w_2$出发，依次访问，直到出现某顶点不再有邻居未被访问过。接着，回退一步，回退到前一次刚访问过的顶点，看是否还有其他未被访问过的邻居，如果有，则访问该邻居，之后再从该邻居出发，进行与前面类似的访问；如果没有，就再回退一步进行类似访问。重复上述过程，直到该图中所有顶点都被访问过为止。以图为例，可以得到如下深度优先搜索序列：$v_1→v_2→v_4→v_5→v_3$。
广度优先搜索是一个分层的搜索过程，没有回退过程，其算法想是：从图中某一顶点$v_i$开始，由$v_i$出发，依次访问$v_i$的所有未被访问过的邻居$w_1，w_2，…，w_n$；然后再顺序访问$w_1，w_2，…，w_n$的所有还未被访问过的邻居，如此一层层执行下去，直到图中所有顶点都被访问到为止。以图为例，可以得到如下广度优先搜索序列：$v_1→v_2→v_3→v_4→v_5$。
