图论

图论是数学的一个分支，研究图的数学性质。图论中的图由顶点（或节点）和连接它们的边（或弧）组成。图论的概念可追溯到1736年，欧拉用图论解决了柯尼斯堡七桥问题。此后，图论逐渐发展为一个成熟的数学领域，并在计算机科学、网络科学、生物学等多个领域得到了广泛应用。

概念

有向图

无向图

图的定义：图 $G=(V,E)$ 是由顶点集 $V$ 和边集 $E$ 组成的，其中 $V$ 是非空有限集合， $E$ 是 $V$ 中元素对（无向图）或有序对（有向图）所组成的集合。

边（Edge）：边是图中连接两个顶点的线段。在无向图中，边是顶点对 $(u,v)$ ，顺序无关；在有向图中，边是顶点的有序对 $(u,v)$ ，顺序相关，表示从顶点 $u$ 指向顶点 $v$ 。
端点（Endpoint）：边连接的两个顶点称为端点。设边 $e=(u,v)$ ，则顶点 $u$ 和 $v$ 是边 $e$ 的端点。
环（Loop）：如果一条边的两个端点重合，即 $(u,u)$ ，则称为环。
空图（Empty Graph）：一个没有顶点和边的图称为空图。
零图（Null Graph）：一个有 $n$ 个顶点但没有边的图称为 $(n,0)$ 图，也叫零图。
平凡图（Trivial Graph）：只有一个顶点的图称为平凡图，记为 $(1,0)$ 图。
简单图（Simple Graph）：没有环和平行边（具有相同端点的多条边）的图称为简单图。
偶图（Bipartite Graph）：如果图 $G$ 的顶点集 $V(G)$ 能分解为两个不相交子集 $V_{1}$ 和 $V_{2}$ （即 $V_{1}\cup V_{2}=V(G)$ ， $V_{1}\cap V_{2}=\varnothing$ ），且子集内的顶点互不相邻，则称图 $G$ 是偶图，记为 $G=(V_{1},V_{2},E)$ 。
有向图（Directed Graph）：图 $G=(V,E)$ 称为有向图，如果边集 $E$ 由顶点集 $V$ 中元素的有序对组成。在有向图中，顶点 $u$ 是边 $e=(u,v)$ 的尾，边 $e$ 与顶点 $u$ 出关联；顶点 $v$ 是边 $e=(u,v)$ 的头，边 $e$ 与顶点 $v$ 入关联。
无向图（Undirected Graph）：图 $G=(V,E)$ 称为无向图，如果边集 $E$ 由顶点集 $V$ 中元素的无序对组成。
孤立点（Isolated Vertex）：没有关联边的顶点称为孤立点。
悬点（Pendant Vertex）：恰有一条关联边的顶点称为悬点。
悬边（Pendant Edge）：与悬点关联的边称为悬边。

历史

图论的历史始于1736年，欧拉通过解决柯尼斯堡七桥问题，奠定了图论的基础。在19世纪和20世纪，随着数学家们对图论问题的研究，图论逐渐发展为一个成熟的数学领域。20世纪下半叶，随着计算机科学的发展，图论在计算机科学中的应用越来越广泛，成为计算机科学的一个重要分支。

图论问题

图的计数：计算某类图的数量。例如，计算具有 $n$ 个顶点的无向图的数量。
子图相关问题：在给定的图 $G$ $G$ 中寻找具有特定性质的子图。例如：
- 子图同构问题：给定两个图 $G$ 和 $H$ ，判断 $G$ 中是否存在一个子图与 $H$ 同构。这是一个NP完全问题。
- 哈密顿回路问题：给定一个图 $G$ ，判断是否存在一个子图与具有 $n$ 个顶点的圈同构。
染色问题：将图的顶点或边染色，使得满足特定条件。例如：
- 四色问题：证明任何平面图的顶点可以用不超过四种颜色染色，使得相邻顶点具有不同颜色。
- 边色数问题：求一个图的最少边色数，使得相邻边具有不同颜色。
路径问题：在给定的图中寻找满足特定条件的路径。例如:
- 柯尼斯堡七桥问题：求解是否存在一条经过柯尼斯堡七桥且仅经过一次的路径。
- 哈密顿回路问题：在给定图中寻找一条包含所有顶点且仅访问一次的回路。
- 最小生成树问题：在给定的带权无向图中寻找权值最小的生成树。
- 中国邮路问题：求解经过所有边至少一次的最短路径。
- 最短路问题：求解给定两个顶点之间的最短路径。
- 斯坦纳树：求解包含给定顶点集合的最小生成树。
- 旅行商问题：求解经过所有顶点且仅访问一次的最短路径（NP困难问题）。
网络流与匹配问题：
1. 最大流问题、最小割问题和最大流最小割定理：在给定的网络中求解最大流和最小割。
2. 最小费用最大流问题：在给定的网络中求解具有最小费用的最大流。
3. 二分图及任意图上的最大匹配：求解给定图中的最大匹配。
4. 带权二分图的最大权匹配：求解给定带权二分图中的最大权匹配。
覆盖问题：
- 最大团：在给定图中寻找最大的完全子图。
- 最大独立集：在给定图中寻找最大的无边导出子图，即独立集。
- 最小覆盖集：求解包含所有顶点的最小边集。
- 最小支配集：求解能支配给定图中所有顶点的最小顶点集。

重要算法

迪克斯特拉算法（Dijkstra's Algorithm, D.A）：求解给定图中两个顶点之间的最短路径。
克鲁斯卡尔算法（Kruskal's Algorithm, K.A）：求解给定带权无向图的最小生成树。
普里姆算法（Prim's Algorithm, P.A）：求解给定带权无向图的最小生成树。
拓扑排序算法（Topological Sorting Algorithm, TSA）：对有向无环图（DAG）进行拓扑排序。
关键路径算法（Critical Path Algorithm, CPA）：求解给定图中的关键路径。
广度优先搜索算法（Breadth-First Search, BFS）：对图进行广度优先遍历。
深度优先搜索算法（Depth-First Search, DFS）：对图进行深度优先遍历。