概念
$G=$<$V, E$>
基本属性
- 度数：与结点关联的边数，环贡献两个度数；有向图中，出度与入度之和为度数；
最大度：$\Delta (G)$；
最小度：$\delta (G)$； - 直径：图中两点间最大距离；
基本概念
- 邻接点：由一条边关联的两个结点；
- 自回路/环：关联于同一结点的两条边，不等于回路；
- 平行边：连接于同一结点的边；
- 简单图：不含平行边的图；
多重图：含有平行边的图； - 无向完全图：$K_n$，每一对结点间都有边相连；
n个节点的无向完全图边数：$K_n=\frac{1}{2}n(n-1)$ - 有向完全图：两个不同结点间总有两条反向的边；
但是这本教材的定义有所不同，是“每两个点任意确定一个方向”；
补图
- 补图：给定图G，由G中所有节点和所有能使G成为完全图的添加边组成的图，称为G相对于完全图的补图，记作$\overline{G}$；
设有$G=$<$V, E$>，$G'=$<$V', E'$>，$G''=$<$V'', E''$>
- 子图：若有$E'\in E$, $V'\in V$；
- 生成子图：若G的子图包含G的所有节点，则该子图为G的生成子图；
- 相对补图：若$G'$是$G$的子图，$E''=E-E'$，且$V''$仅包含$E''$的边所关联的结点，则$G''$是子图$G'$相对于$G$的补图。即，补上$G''$中所有边，使$G'$成为完全图，且$G''$中不含孤立节点。
图同构
$G\simeq G'$
图同构的必要条件：
- 节点数目相同
- 边数相同
- 度数相同的节点数目相同
相关定理
- 每个图中，节点数的总和等于边数两倍；
推论1： 任何图中，度数为奇数的结点必定是偶数个；
路与回路
路
- 路：依次由点和边组成的序列；
有向图中，可用边序列表示；无向图中，可用点序列表示； - 回路：起点等于终点的路；
- 迹：没有重复边的路；
- 通路：没有重复结点的路；
- 圈：起点等于重点的通路；
相关定理：
- 在n个结点的图中，若存在从$v_i$到$v_j$的路，则必然存在从$v_i$到$v_j$且节点数量小于n的通路。
连通性
连通性是在无向图中讨论的。
连通性是等价关系，因此可以诱导出图节点集$V$的一个划分，子图$G(V)$称为连通分支（图），连通分支数记为$W(G)$。
- 对任何一个图，有$k(G)\leq \lambda(G)\leq \delta(G)$
- G中v是割点的充分必要条件是，存在两个节点u和w，u和w的每一条路都通过v。
可达
可达是在有向图中讨论的，即节点u到v有一条路。
可达是自反和传递的，一般不是对称的。
“图代表的关系”和“可达”并不一样，例如7-2(7)题问，该图对应的关系是否可传递，答案是否。
因为有<$v_1, v_2$>，<$v_2, v_3$>，但没有<$v_1, v_3$>。
- 单侧联通：图中任意一对节点至少从一个到另一个可达。
- 强联通：任意两点双向可达；值得注意的是，不一定是直接相连，只要是可达就行。因此强联通的充分条件是，当且仅当有一个回路，他至少包含每个节点一次。
- 弱连通：忽略有向边的方向后若图连通，则为弱连通。
欧拉图与汉密尔顿图
Euler Graph
具有欧拉路的图叫做欧拉图。
-
欧拉路：经过图中每边一次且仅一次。
无向图G中有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。
推论：无向图G中有欧拉回路，当且仅当G是连通的，且所有节点度数全为偶数。 -
单向欧拉路：有向图G中，经过每边一次且仅一次的单向路。
有向图G有一条单向欧拉路：当且仅当每个节点入度等于出度；
有一条单向欧拉回路：当且仅当除两个节点外，其他所有节点入度等于出度，且这两个结点其中一个入度比出度大一，另一个的出度比入度大一。
Hamilton Graph
具有汉密尔顿路的图叫做汉密尔顿图。
- 汉密尔顿路：经过每个结点恰好一次。
汉密尔顿回路图中，对V的每个非空子集S，都有$W(G-S)\leq |S|$。
n个结点简单图中：
存在汉密尔顿路的充分条件：若G中每一对结点度数之和大于等于n-1，则存在。
存在汉密尔顿回路的充分条件：若每一对结点度数之和大于等于n，则存在。
判断一个图是否为汉密尔顿图的方法：求原简单图闭包（在一对度数和至少为n的结点间连线，然后重复上述过程），若闭包为汉密尔顿图，则原图为汉密尔顿图。
判断不存在汉密尔顿路的方法：标A、B，看能否交替排列。
平面图
欧拉定理
- 面的次数：$\rm{deg}(r)$，面的边界回路长度；
- 有限平面图中，面的次数之和为边数两倍；
欧拉定理：
设有连通平面图G，有$v$个节点，$e$条边，$r$块面，则：$v-e+r=2$。
根据欧拉公式，可以得到以下定理：
- 若G是连通平面简单图，且$v\geq 3$，则$e\leq 3v-6$。
该定理用于判断某个图不是平面图，即不满足一定不是平面图，但满足不一定是平面图。
Kuratowski's theorem
- 若$G_1$和$G_2$同构，若反复插入或删除度数为2的结点，可以使得二者同构，则称这两个图在2度结点内同构。
- 一个图是平面图，当且仅当它不包含与$K_{3,3}$或$K_5$在2度节点内同构的子图。
