WonderU
离散数学

11.特殊图

1.欧拉图

  • 欧拉通路：通过图中所有边一次且仅一次的通路（有且仅有2个奇度顶点）
  • 欧拉回路：通过图中所有边一次且仅一次的回路
  • 欧拉图：具有欧拉回路的图
  • 半欧拉图：具有欧拉通路而无欧拉回路的图
  1. 无向图GG 是欧拉图 当且仅当GG是连通图，且没有奇度顶点(所有顶点的度都是偶数)。
  2. 有向图DD 是欧拉图 当且仅当DD是强连通图，且每个顶点的入度等于出度。
  • 例： 不是欧拉图（有奇度顶点）不是欧拉图（有奇度顶点） 是欧拉图（通过所有边一次且仅一次的回路，所有顶点的度都是偶数）是欧拉图（通过所有边一次且仅一次的回路，所有顶点的度都是偶数） 不是欧拉图（有奇度顶点）不是欧拉图（有奇度顶点） 不是欧拉图（有奇度顶点）不是欧拉图（有奇度顶点）

2.哈密顿图

  • 哈密顿通路: 经过图中所有顶点一次且仅一次的通路（有且仅有2个奇度顶点）

  • 哈密顿回路: 经过图中所有顶点一次且仅一次的回路

  • 哈密顿图: 具有哈密顿回路的图

  • 半哈密顿图: 具有哈密顿通路而无哈密顿回路的图

  • 充分条件

    1. 设GG是nn阶无向简单图，若对于GG中任意不相邻的顶点u,vu,v，均有 d(u)+d(v)≥nd(u)+d(v)≥n，则GG是哈密顿通路。
    2. 设GG是n(n≥3)n(n≥3)阶无向简单图, 若对于GG中任意不相邻的顶点u,vu,v，均有 d(u)+d(v)≥nd(u)+d(v)≥n，则GG是哈密顿回路。

  • 哈密顿图判断条件

    • 存在性（充分条件，满足则一定是哈密顿图）

      1. 狄拉克定理 Dirac（简单无向图）

        n≥3n≥3 个顶点，每个顶点度数 ≥ n/2n/2 → 一定是哈密顿图。

      2. 奥尔定理 Ore（简单无向图）

        n≥3n≥3，任意不相邻两点度数和 ≥ nn → 一定是哈密顿图。

      3. 竞赛图

        强连通竞赛图一定是哈密顿图。

    • 非存在性（必要条件，不满足则一定不是）

      1. 必要条件（最常用） 对顶点集 VV 的任意非空真子集 SS，有： w(G−S)≤∣S∣w(G-S) \leq |S|
        • w(G−S)w(G-S)：删去 S 后连通分支数
        • ∣S∣|S|：子集顶点个数
        • 若存在 S 使得分支数 > ∣S∣|S| → 一定不是哈密顿图。
      2. 顶点度数必要条件 存在度数为 0/10/1 的顶点，且无法纳入回路 → 不是哈密顿图。

  • 例1. 设有如下无向图, 则(A‾\underline{A})是一条哈密顿通路 A. V7V1V6V5V4V3V2V_7 V_1 V_6 V_5 V_4 V_3 V_2

    B. V1V2V3V4V5V6V7V_1 V_2 V_3 V_4 V_5 V_6 V_7

    C. V1V2V4V5V6V_1 V_2 V_4 V_5 V_6

    D. V2V3V4V_2 V_3 V_4

    注:哈密顿通路: 经过图中所有顶点一次且仅一次的通路

  • 例2. 设有无向图, 则(A‾\underline{A})是一条哈密顿回路 A. gabcdefggabcdefg

    B. abcdefgabcdefg

    C. cfabcdegcfabcdeg

    D. efgabcdefgabcd

    注: 哈密顿回路: 经过图中所有顶点一次且仅一次的回路

3.偶图

  • 无向图 G=<V,E>G=< V, E> 为偶图（二部图）的充分必要条件是 GG 的所有回路的长度均为偶数。

4.平面图

基本概念

  1. 二部图定义
    设无向图 G=<V,E>G=< V, E>，若能将 VV 划分成V1V_1和 V2V_2（即 V1∪V2=VV_1 \cup V_2 = V，V1∩V2=∅V_1 \cap V_2 = \emptyset，且 V1≠∅V_1 \neq\emptyset，V2≠∅V_2 \neq\emptyset），使得GG中的每条边的两个端点都是一个属于 V1V_1，另一个属于 V2V_2，则称GG为二部图。
    若GG是二部图，V1V_1 中的每个顶点均与 V2V_2 中的所有顶点相邻，则称GG为完全二部图，记为 Kr,sK_{r, s}，其中 r=∣V1∣r=|V_{1}|，s=∣V2∣s=|V_{2}|。
  2. 平面图定义
    如果能将无向图GG 画在平面上使得除顶点处外无边相交，则称GG为可平面图，简称为平面图。
    • K1K_{1} , K2K_{2} , K3K_{3} , K4K_{4} 都是平面图；K5−eK_{5}-e（K5K_{5} 删除任意一条边）也是平面图。
      完全二部图 K1,n(n≥1)K_{1, n}(n \ge1)，K2,n(n≥2)K_{2, n}(n \ge2) 也都是平面图。
    • K5K_{5} 和 K3,3K_{3,3}，它们都是非平面图。
  3. 面、边界、次数
    给定平面图GG的平面嵌入，GG的边将平面划分成若干个区域，每个区域都称作GG的一个面。
    包围每个面的所有边的回路组称作该面的边界，边界的长度称作该面的次数。
  4. 平面图性质：平面图所有面的次数之和等于边数的两倍。
  5. 极小非平面图
    若在非平面图 GG 中任意删除一条边，所得的图是平面图，则称GG是极小非平面图。
    K5K_{5} 和 K3,3K_{3,3} 都是极小非平面图。
    • 例：图中C‾\underline{C}是平面图

平面图的判定

  • 库拉托夫斯基定理：一个图是平面图的充分必要条件是它的任何子图都不可能收缩为K5K_{5}或K3,3K_{3,3}。

欧拉公式

  • 连通平面图GG的顶点数、边数和面数分别为 nn、mm和rr，则有n−m+r=2n-m+r=2

    • 例1：设GG是连通平面图，有5个顶点，6个面，则GG的边数是9。
      解：5−m+6=25-m+6=2，解得 m=9m=9。
    • 例2：图GG是一个简单的连通平面图，顶点数为8，其无限面的次数为5，其余面都为三角形（次数为3），计算平面图的边数和面数。
      分析：平面图所有面的次数之和 等于边数的两倍。
      解：设平面图GG的边数为 mm，面数为rr
      {8−m+r=25+3(r−1)=2m⇒{m=16r=10 \begin{cases} 8 - m + r = 2 \\ 5 + 3 ( r - 1 ) = 2 m \end{cases} \Rightarrow \begin{cases} m=16 \\ r=10 \end{cases}
      解得：平面图的变数为n=16n=16，面数为 r=10r=10。

  • 设GG是 n(n≥3)n(n \ge3) 阶 mm 条边的简单平面图，则 m≤3n−6m \le3 n-6。

    注：一个简单连通图，若不满足 m≤3n−6m \le3 n-6，则一定是非平面图，但满足该不等式的简单连通图未必是平面图。

    • 例：设图GG有VV个结点，ee条边，当 V>3V>3，若不满足 e≤3V−6e \le3 V-6，它一定不是平面图 √‾\underline{\surd}。

补.最短路径问题

  • 权、带权图 G=<V,E,W>G=< V, E, W>
  • 最短路径 在带权图中，u,v∈Vu,v \in V，当 uu 和 vv 连通时，从 uu 到 vv 长度最短的路径，称其长度为从 uu 到 vv 的距离，记作 d(u,v)d(u, v)。 其中 d(u,u)=0d(u, u)=0，当uu和vv不连通时 d(u,v)=+∞d(u, v)=+\infty。
  • 最短路径问题 给定带权图 G=<V,E,W>G=< V, E, W> 及顶点uu和 vv，求从uu到vv的最短路径。 注：Dijkstra算法。
    得：从 v1v_{1} 到其余各点的最短路径和距离如下：
    d(v1,v2)=3, v1v2d(v_{1},v_{2})=3,\ v_1 v_2
    d(v1,v3)=5, v1v2v5d(v_{1},v_{3})=5,\ v_1 v_2 v_5
    d(v1,v4)=5, v1v4d(v_{1},v_{4})=5,\ v_1 v_4
    d(v1,v5)=8, v1v2v3v5d(v_{1},v_{5})=8,\ v_1 v_2 v_3 v_5
    d(v1,v6)=7, v1v4v6d(v_{1},v_{6})=7,\ v_1 v_4 v_6
    d(v1,v7)=9, v1v4v6v7d(v_{1},v_{7})=9,\ v_1 v_4 v_6 v_7
← 返回 Note