欧拉图

  • 包含图GG的所有边的简单通路为GG的欧拉通路，包含图GG所有边的简单回路为GG的欧拉回路。
  • 具有欧拉回路且不含孤立点的图为欧拉图

无向欧拉图的性质

  • 连通无向图是欧拉图当且仅当每个顶点的度是偶数。
  • 推论：连通无向图中两个不同顶点之间有欧拉通路当且仅当它们的度为奇数，且其他顶点的度为偶数。

有向欧拉图的性质

  • 弱连通的有向图是欧拉图当且仅当每个顶点的入度和出度相等
  • 推论：弱连通的有向图中两个不同的顶点之间有欧拉通路当且仅当其中一个顶点入度与出度之差为1，另一个顶点出度与入度之差为1，且其他顶点的出度与入度相等。

哈密顿图

  • 包含图GG的所有顶点的基本通路为gg的哈密顿通路。包含图GG的所有顶点的基本回路为GG的哈密顿回路。具有哈密顿回路的图为哈密顿图。
  • 哈密顿图中：能找到一条恰好经过每个顶点一次的回路
  • Kn(n≥3)K_n(n\ge 3)是哈密顿图

无向哈密顿图的性质

  • 必要条件：若连通无向图G=(V,E)G = (V,E)是哈密顿图，则对VV的任意非空子集SS,有

ω(G−S)≤∣S∣\omega(G-S)\le |S|

  • 引理：nn阶简单无向图G=(V,E)G = (V,E)，u,vu,v是两个不相邻的顶点，d(u)+d(v)≥nd(u)+d(v) \ge n，则对无向图G1=G+u,vG_1 = G +{u,v}，若G1G_1是哈密顿图，则GG也是哈密顿图。

  • 充分条件：若n(n≥3)n(n\ge 3)阶无向简单图GG的每对不相邻顶点的度之和都不小于nn，则GG是哈密顿图。

  • 哈密顿图的其它必要条件：

    • 没有1度的顶点
    • 2度顶点的关联边必定在哈密顿回路上
    • 与一个顶点关联的边中有且仅有两条在哈密顿回路上
    • 哈密顿回路中没有小回路

竞赛图

  • 在循环赛中，每个队伍和其他各个队伍恰好比赛一次，而且队伍之间不允许平局，这种比赛用有向图建立：顶点表示队，从一个顶点到另一个顶点有一条有向边当且仅当这个队伍打败了另一个队伍。这种有向图为竞赛图。
  • 任意竞赛图都有有向哈密顿通路。

平面图

  • 若无向图GG有一种在平面上的画法，其中边只相交于图中顶点，则GG是平面图。该几何图形表示称为平图。
  • 在平面图GG的一个平图中，边把平面划分为若干区域，若一个区域内部不含GG的边，则这块区域是一个面。包围一个面的最短回路是该面的边界。面的边界的长度称为面的次数，记作deg(R)deg(R)。面积有限的面为有限面，反之为无限面。

对偶图

  • 设平面图GG有rr个面R1,R2,...,RrR_1,R_2,...,R_r，nn个顶点，mm条边e1,e2,...,eme_1,e_2,...,e_m。对偶图G∗=(V∗,E∗)G^*=(V^*,E^*)构造方法如下：
  • 在GG的每个面取一个点作为G∗G^*的顶点，V∗={v1,v2,...,vr}V^* = \{v_1,v_2,...,v_r\}
  • 对于GG的每条边，若该边属于两个不同面Ri,RjR_i,R_j的边界，则构造对应的一条边ek∗={vi,vj}e_k^* = \{v_i,v_j\}，若仅仅属于一个面的边界，构造ek∗={vi,vi}e_k^* = \{v_i,v_i\}，E∗={e1∗,...,em∗}E^* = \{e_1^*,...,e_m^*\}
  • 性质：
    • G∗G^*和GG的边的数目相同。
    • G∗G^*的顶点数为GG的面数。
    • G∗G^*的每个顶点的度数等于GG对应面的次数。

平面图的性质

  • 平面图各面的次数之和是其边数的两倍

∑R是G的面deg(R)=∑v∗∈V∗d(v∗)=2∣E∣\sum_{R是G的面} deg(R) = \sum_{v^* \in V^*} d(v^*)=2|E|

  • 若连通平面图有nn个顶点，mm条边，rr个面，则

n−m+r=2n-m+r = 2

  • 若连通平面图每个面次数不小于k(k≥3)k(k\ge 3)，则

m≤kk−2(n−2)m \le \frac{k}{k-2}(n-2)

同胚

  • 对一个无向图的一些边上插入一些度数为2的点，将一条边分为几条边，得到的图于原图同胚。

收缩

  • 在一个无向图中删除一些边，并将每对与被删之边关联的顶点合并为一个顶点，得到的图为原图的收缩。

库拉托夫斯基定理

  • 无向图GG是平面图当且仅当GG中不存在与K3,3K_{3,3}或K5K_5同胚的子图
  • 无向图GG是平面图当且仅当GG中不存在可收缩到K3,3K_{3,3}或K5K_5的子图

四色定理

  • 对于任意平面图，χ(G)≤4\chi (G)\le 4

无向树

  • 连通且没有长度大于0的基本回路的无向图为无向树。

  • 树中度为1的顶点为叶子，叶节点。度数大于1的为分支节点。

  • 只有一个顶点的树为平凡树。否则为非平凡树

  • 没有长度大于0的基本回路的无向图称为无向森林，简称森林。

  • 设无向图GG，以下命题等价：

    • GG是树
    • GG中没有长度大于0的基本回路且，∣E∣=∣V∣−1|E| = |V| - 1
    • GG是连通图，且∣E∣=∣V∣−1|E| = |V|-1
    • GG中没有长度大于0的基本回路，且在GG中任意两个不相邻顶点之间添加一条边后得到的图有且仅有一条不同的长度大于0的基本回路。
    • GG是连通图，删去任意一边后得到的图不是连通图。
    • GG是简单图，且GG的任意一对不同的顶点之间有且仅有一条不同的基本通路。

  • 非平凡的树至少有两个叶子。

  • 在nn阶连通图中，若边的数目大于n−1n-1则必有长度大于0的基本回路。

  • 生成树：无向图GG的某个生成子图TT是树，则TT是GG的生成树。

有向树

  • 底图是无向树的有向图为有向树。
  • 若有向树有且仅有一个顶点入度为0，其他顶点入度均为1，则为根树。
  • 根树中入度为0的顶点为根节点，出度为0的顶点为叶节点。出度大于0的结点为分支节点/内节点。
  • 由根到某一顶点的基本通路的长度为该顶点的层次，顶点的最大层次为根树的高度。
  • 在根树中，根到其他任意顶点的通路存在且唯一。
  • 若在根树中规定了兄弟之间的某种排列次序则为有序树。
  • 若根树中所有顶点的出度不大于m，且至少有一个顶点的度为m，则为m叉树。
  • 若根树中所有顶点的出度均为m或0，则为完全m叉树。
  • 二叉树中n0=n2+1n_0 = n_2 +1，nin_i为出度为ii的结点数目。

决策树

  • 根树，其中的每个内部结点都对应于某个问题的一个决策，内部结点上的子树用于展示该决策的每个可能结果。问题的可能解决方案对应于通往这棵根树叶子的路径。
  • 决策树描述了一种分而治之 (Divide & Conquer) 的过程，不断将问题分解为更简单的问题。