图论基础

图 是由顶点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的图，那么 ，即边对顶点度数的总贡献度是边数目的两倍

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

特性3 ：给定G为具有n个顶点m条边的简单图。如果G是无向的，那么 ，如果G是有向的，那么

特性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的依赖于一系列界限的每个 传递闭包提出了一个简单算法。这个算法被称为 Floyd_Warshall算法

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