图论
图（Graph） 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则表示这两个事物之间具有的某种关系。图中的边可以是有方向或没有方向的，分别称为有向图和无向图。
图¶
图 (graph) 是一个二元组 \(G=(V(G), E(G))\)。其中 \(V(G)\) 是非空集，称为 点集 (vertex set)，对于 \(V\) 中的每个元素，我们称其为 顶点 (vertex) 或 节点 (node)，简称 点；\(E(G)\) 为 \(V(G)\) 各结点之间边的集合，称为 边集 (edge set)。
当 \(V,E\) 都是有限集合时，称 \(G\) 为 有限图。 当 \(V\) 或 \(E\) 是无限集合时，称 \(G\) 为 无限图。
图有多种，包括 无向图 (undirected graph)，有向图 (directed graph)，混合图 (mixed graph) 等：
-
若 \(G\) 为无向图，则 \(E\) 中的每个元素为一个无序二元组 \((u, v)\)，称作 无向边 (undirected edge)，简称 边 (edge)，其中 \(u, v \in V\)。设 \(e = (u, v)\)，则 \(u\) 和 \(v\) 称为 \(e\) 的 端点 (endpoint)。
-
若 \(G\) 为有向图，则 \(E\) 中的每一个元素为一个有序二元组 \((u, v)\)，有时也写作 \(u \to v\)，称作 有向边 (directed edge) 或 弧 (arc)，在不引起混淆的情况下也可以称作 边 (edge)。设 \(e = u \to v\)，则此时 \(u\) 称为 \(e\) 的 起点 (tail)，\(v\) 称为 \(e\) 的 终点 (head)，起点和终点也称为 \(e\) 的 端点 (endpoint)。并称 \(u\) 是 \(v\) 的直接前驱，\(v\) 是 \(u\) 的直接后继。【起点 (tail) 和 终点 (head) 指的是箭头符号的尾部和头部。边通常用箭头表示，而箭头是从“尾”指向“头”的。】
-
若 \(G\) 为混合图，则 \(E\) 中既有向边，又有无向边。
-
若 \(G\) 的每条边 \(e_k=(u_k,v_k)\) 都被赋予一个数作为该边的 权，则称 \(G\) 为 赋权图。如果这些权都是正实数，就称 \(G\) 为 正权图。
图 \(G\) 的点数 \(\left| V(G) \right|\) 也被称作图 \(G\) 的 阶 (order)。
相邻¶
在无向图 \(G = (V, E)\) 中，若点 \(v\) 是边 \(e\) 的一个端点，则称 \(v\) 和 \(e\) 是 关联的 (incident) 或 相邻的 (adjacent)。对于两顶点 \(u\) 和 \(v\)，若存在边 \((u, v)\)，则称 \(u\) 和 \(v\) 是 相邻的 (adjacent)。
一个顶点 \(v \in V\) 的 邻域 (neighborhood) 是所有与之相邻的顶点所构成的集合，记作 \(N(v)\)。
一个点集 \(S\) 的邻域是所有与 \(S\) 中至少一个点相邻的点所构成的集合，记作 \(N(S)\)，即：