Definition:

A graph $G=(V , E)$ consists of $V$, a nonempty set of _vertices_ (or _nodes_ ) and $E$, a set of edges . Each edge has either one or two vertices associated with it, called its endpoints . An edge is said to connect its endpoints.

• 图的点数称为图的 阶(order) ， $\nu(G)=n(G)=|V(G)|$，简记为 $\nu$ 或 $n$。
• 边数为 $\epsilon(G)=m(G)=|E(G)|$，简记为 $\epsilon$ 或 $m$。
• 边与它连接的顶点 相关联(incident) 。
• 被同一条边连接的两个顶点 相邻(adjacent) ，互为 邻点、邻居(neighbor) 。
• 与同一顶点相连的边彼此相邻。
• 不与任何定点相邻的顶点称为 孤立点(isolated vertex)
• 两条一样的边称为 重边(multi-edge) 或 平行边(parallel edge)
• 只有一个顶点的图称为 平凡图(trival graph)
• 没有边的图称为 空图(empty edge) 或 零图
• 顶点的度为与顶点关联的边的个数，环计两次。
• 度数为奇数的点称为 奇点(odd vertex) ，偶数为 偶点(even vertex)
• 度数为 1 的顶点称为 悬挂点(end vertex) 或 叶点(leaf)''。 悬挂点的关联边称为''悬挂边(end edge) 。
• 图的最大度数 $\Delta(G)$ ，最小度数 $\delta(G)$。 或 $\Delta$ 与 $\delta$。
• 图中与 $u$ 相邻的点的集合 $\{v|v\in V,(u,v)\in E\}$ 称为 $u$ 的 __邻域(neighborhood)__ ，记为 $N(u)$。
• 连通分量的个数 $\omega(G)$ 。 又叫 分支数(number of components)

独立集(Independent Set)

图 $G$ 的顶点子集 $V'(V'\subset V(G))$ 中任意两个顶点在图 $G$ 中都不相邻，则称 $V'$ 为图 $G$ 的独立集。

A directed graph (or digraph ) $(V , E)$ consists of a nonempty set of vertices $V$ and a set of _directed edges_ (or _arcs_ ) $E$. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair $(u,v)$ is said to _start_ at $u$ and _end_ at $v$.

Ore's Theorem:

If $G$ is a simple graph with $n$ vertices with $n≥3$ such that $deg(u)+deg(v)≥n$ for every pair of nonadjacent vertices $u$ and $v$ in $G$, then $G$ has a Hamilton circuit.

Bipartite Graphs

迹 Trail

边互不相同的途径

路 Path

顶点互不相同的途径

设图 $G=(V(G),E(G))$，对任意非空 $S\subset V(G)$，令 $\bar S=V(G)\backslash S$，记

$$[S,\bar S]_G=\{e=uv\in E(G)\;|\;u\in S,v\in\bar S\}$$

为 边割 或 割集 (cut, edge cut)(也可以简记为$[S,\bar S]$)。

Shortest Path