简单图
图的定义及其相关概念
简介
图是用于表示对象之间存在某种关系的数据结构。在图中，对象称作节点或者顶点（Vertex），对象之间的关系称作边（Edge）。
图中的边可以是有方向或没有方向的。例如在一张图中，如果节点表示聚会上的人，而边表示两人曾经握手，则该图就是没有方向的，因为甲和乙握过手也意味着乙一定和甲握过手。如果一条从甲到乙的边表示甲欠乙的钱，则该图就是有方向的，因为“欠钱”这个关系不一定是双向的。前一种图称为无向图，后一种称为有向图。
在计算机科学数据结构中，可以认为无向图是一种特殊的有向图。
有向图的定义
有向图是一个二元组 \(G=(V,E)\)，其中
- \(V\) 是节点的集合；
- \(E \subseteq \{(x,y)|(x,y) \in V^2\}\) 是边的集合。
\((x,y)\) 表示节点 \(x\) 到节点 \(y\) 的边，节点 \(x\) 称为边的起点，节点 \(y\) 称为边的终点。
多重图
如果图中存在多条起点和终点均分别相同的边，这样的图为多重图，这样的边称为多重边。
自环
图中起点和终点为相同节点的边称为自环，即形如 \((x,x)\) 的边。
简单图
不含多重边和自环的图称为简单图。
节点的度
有向图中的节点有出度和入度之分。节点的出度是指起点为该节点的边的数量；节点的入度是指终点为该节点的边的数量。
无向图不区分出度和入度。
若把图的所有顶点的度数按照非递增顺序排成一个序列，称该序列为这个图的度序列。同构图具有相同的度序列。
Havel–Hakimi算法 （根据度序列判定是否可图）
图的同构
必要条件：
- 边数相同，顶点数相同
- 度数相同的顶点数目相等，即度序列相同
加权图
加权图也称赋权图（weighted graph），指每条边都对应一个数字（即权重，weight）的图。在实际应用中，权重可以表示诸如费用、距离、容量等意义。这样的图经常出现在最短路问题和旅行商问题等问题中。
子图和生成子图
对于图 \(G\) 和 图 \(G{'}\)，若 \(V(G{'}) \in V(G)\) 且 \(E(G{'}) \subseteq E(G)\)，则称 \(G{'}\) 是\(G\) 的子图。
生成子图是满足条件 \(V(G{'})=V(G)\) 的\(G\) 的子图 \(G{'}\)。
连通图
强连通图
有向无环图
二分图
欧拉图
欧拉路径