若 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 = (V, E),若 V'\subseteq V 且 G\left[V\setminus V'\right](即从 G 中删去 V' 中的点)不是连通图,则 V' 是图 G 的一个 点割集 (Vertex cut/Separating set)。大小为一的点割集又被称作 割点 (Cut vertex)。
对于连通图 G = (V, E) 和整数 k,若 |V|\ge k+1 且 G 不存在大小为 k-1 的点割集,则称图 G 是 k- 点连通的 (k-vertex-connected),而使得上式成立的最大的 k 被称作图 G 的 点连通度 (Vertex connectivity),记作 \kappa(G)。(对于非完全图,点连通度即为最小点割集的大小,而完全图 K_n 的点连通度为 n-1。)
对于图 G = (V, E) 以及 u, v\in V 满足 u\ne v,u 和 v 不相邻,u 可达 v,若 V'\subseteq V,u, v\notin V',且在 G\left[V\setminus V'\right] 中 u 和 v 不连通,则 V' 被称作 u 到 v 的点割集。u 到 v 的最小点割集的大小被称作 u 到 v 的 局部点连通度 (Local connectivity),记作 \kappa(u, v)。
还可以在边上作类似的定义:
对于连通图 G = (V, E),若 E'\subseteq E 且 G' = (V, E\setminus E')(即从 G 中删去 E' 中的边)不是连通图,则 E' 是图 G 的一个 边割集 (Edge cut)。大小为一的边割集又被称作 桥 (Bridge)。
对于连通图 G = (V, E) 和整数 k,若 G 不存在大小为 k-1 的边割集,则称图 G 是 k- 边连通的 (k-edge-connected),而使得上式成立的最大的 k 被称作图 G 的 边连通度 (Edge connectivity),记作 \lambda(G)。(对于任何图,边连通度即为最小边割集的大小。)
对于图 G = (V, E) 以及 u, v\in V 满足 u\ne v,u 可达 v,若 E'\subseteq E,且在 G'=(V, E\setminus E') 中 u 和 v 不连通,则 E' 被称作 u 到 v 的边割集。u 到 v 的最小边割集的大小被称作 u 到 v 的 局部边连通度 (Local edge-connectivity),记作 \lambda(u, v)。
对于无向简单图 G = (V, E),它的 补图 (Complement graph) 指的是这样的一张图:记作 \bar G,满足 V \left( \bar G \right) = V \left( G \right),且对任意节点对 (u, v),(u, v) \in E \left( \bar G \right) 当且仅当 (u, v) \notin E \left( G \right)。
两个图 G 和 H,如果存在一个双射 f : V(G) \to V(H),且满足 (u,v)\in E(G),当且仅当 (f(u),f(v))\in E(H),则我们称 f 为 G 到 H 的一个 同构 (Isomorphism),且图 G 与图 H 是 同构的 (Isomorphic),记作 G \cong H。
交 (Intersection):图 G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right) 的交定义成图 G \cap H = \left( V_1 \cap V_2, E_1 \cap E_2 \right)。
容易证明两个无向简单图的交还是无向简单图。
并 (Union):图 G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right) 的并定义成图 G \cup H = \left( V_1 \cup V_2, E_1 \cup E_2 \right)。
和 (Sum)/直和 (Direct sum):对于 G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right),任意构造 H' \cong H 使得 V \left( H' \right) \cap V_1 = \varnothing(H' 可以等于 H)。此时与 G \cup H' 同构的任何图称为 G 和 H 的和/直和/不交并,记作 G + H 或 G \oplus H。