图论

图论简介

图论是数学的一个分支，它研究的是图形（在这里指的是“图”）的性质。这里的“图”是由一些点和连接这些点的线构成的结构。在图论中，我们称这些点为“顶点”，而把连接顶点的线称为“边”。

基本术语

• 顶点 (Vertex): 图中的一个点，通常用来表示某个实体或对象。
• 边 (Edge): 连接两个顶点的线段，表示顶点之间的关系或连接。
• 图 (Graph): 由顶点集合和边集合组成的数据结构。

图的类型

• 无向图 (Undirected Graph): 边没有方向，即边是双向的。例如，朋友之间的关系通常是互相的。
• 有向图 (Directed Graph): 边有明确的方向，从一个顶点指向另一个顶点。例如，在互联网上，一个网站链接到另一个网站就是单向的。

图的特性

• 度 (Degree): 一个顶点的度是指与它相连的边的数量。在有向图中，我们区分入度（指向该顶点的边数）和出度（从该顶点出发的边数）。
• 路径 (Path): 一系列顶点和边组成的序列，使得每一对连续的顶点都由一条边连接。
• 环 (Cycle): 一个路径，其中第一个顶点和最后一个顶点相同。
• 连通性 (Connectivity): 无向图中任意两个顶点之间存在路径，则称此图为连通图。有向图则分为强连通（任意两点间都有路径）和弱连通（忽略方向后连通）。
• 子图 (Subgraph): 一个图的子集，包含原图的一些顶点和它们之间的边。

有向无环图

如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。