图论基础 - 简书

图是由顶点V和边E的集合组成的二元组，记G=(V,E)

有向图、无向图、有权图、无权图、连通图（联通分量）、二分图

顶点的度（无向图种与顶点相连的边的数目）、入度（有向图中以该顶点为终点的边的数目）、出度（有向图中以该顶点为起点的边的数目），度等于入度和出度之和，所有边的入度和=所有边的出度和=边数

图的定义是指将边作为一个集合，从而允许两个无向边具有相同的端点。对于两个有向边可以有相同的起点和终点。这种边称为平行边或者多重边。另一种边的特殊类型是顶点和自己连接，也就是说两个顶点重合，我们称这样的边为自循环。除了少数例外，图没有平行边和自循环

图G中从顶点u到顶点v有一条路径，我们称u到达v，并且v是从u可达的。在无向图中，可达性的概念是对称的。

如果一个图是连通的，则意味着对于任何两个顶点，它们中间都是有路径的。

如果对于G的任何两个顶点u和v，都有u可达v并且v可达u，则有向图是强连通的

图G的子图是顶点和边是G的顶点和边的各自的子集的图H。G的生成子图是包含图G的所有顶点的图。

如果图G是不连通的，它的最大联通子图称为G的连通分支。

森林是没有循环的图。树是连通的森林，即没有循环的联通图。图的生成树是树的生成子图

特性1：如果G是由m条边和顶点集V的图，那么 $\sum_{v\ in\ V}deg(v)=2m$ ，即边对顶点度数的总贡献度是边数目的两倍

特性2：如果G是有m条边和顶点集V的有向图，那么 $\sum_{v\ in\ V}in\ deg(v)=\sum_{v\ in\ V}out\ deg(v)=m$ 即边对它的起点u的出度贡献了一个单元，对终点v的入度贡献了一个单元。因此边对顶点出度的总贡献和边的数目相等，入度也是一样。

特性3：给定G为具有n个顶点m条边的简单图。如果G是无向的，那么 $m<=\frac{n(n-1)}{2}$ ，如果G是有向的，那么 $m<=n(n-1)$

假设G是无向的。因为没有两条边可以有相同的端点且没有自循环，在这种情况下G的顶点的最大度是n-1，通过特性1可知， $2m<=n(n-1)$ 。假设G是有向的，因为没有两条边具有相同的起点和终点，且没有自循环，这种情况下G的顶点的最大入度是n-1，通过特性2， $m<=n(n-1)$

特性4：给定G是有n个顶点和m条边的无向图。

边列表：对所有边采用无序的列表。但是没有有效的办法找到特定的边(u,v)，或者将所有的边入射到顶点v

邻接列表：为每个顶点维护一个单独的列表，包括入射到顶点的那些边。可以通过取较小集合的并集来确定完整的边集合，也可以更高效地找到所有入射到给出顶点的边

邻接图：和邻接列表非常相似，但是所有入射到顶点的边的次级容器被组织成一个图，而不是一个列表，用相邻的顶点作为键。这允许在O(1)的时间内访问特定的边(u,v)

邻接矩阵：对于有n个顶点的图维持一个n*n矩阵来提供最坏的情况下访问特定边(u,v)的时间O(1)。每一项专用于为顶点u和v的特定对存储一个参考边(u,v)；如果没有这样的边存在，该表项即为空

可能是最简单的，但不是最有效的。所有顶点存储在一个无序的列表V中，并且所有的边对象存储在一个无序的列表E中

将图形的边存储在较小的位置来对其进行分组，从而和每个单独的顶点相关联的次级容器结合起来。具体的，对每个顶点v维持一个集合l(v)，该集合被称为v的入射列表，其中全部都是入射到v的边。（在有向图的情况下，输出边和输入边分别存储在两个单独的集合lout(v)和lin(v)中。

同时要求邻接列表的基本结构在某种程度上保持顶点集合V，因此可以在O(1)时间内为给出的顶点v找出次级结构l(v)

命题：对于i=1，...，n，当且仅当有向图 $G$ 从 $v_i$ 到 $v_j$ 有一条有向路径时，有向图 $G_k$ 有边 $(v_i,v_j)$ ，其中中间的顶点在集合 ${v_1,...,v_k}$ 中，特别的， $G_k$ 和 $G^*$ 相等， $G^*$ 是 $G$ 的传递闭包

该命题为计算G的依赖于一系列界限的每个 $G_k$ 传递闭包提出了一个简单算法。这个算法被称为Floyd_Warshall算法

没有有向循环的有向图被叫作有向非循环图，或者简称DAG