【图论】欧拉图、汉密尔顿图



2021年10月23日    Author:Guofei

文章归类: 0x80_数据结构与算法    文章编号: 581

版权声明:本文作者是郭飞。转载随意,但需要标明原文链接,并通知本人
原文链接:https://www.guofei.site/2021/10/23/graph2.html


欧拉回路

【定义】欧拉回路 一个连通图,如果存在一条路,它经过每条边且仅一次,这个路叫做 欧拉路;如果它是个回路,称为 欧拉回路

【定理】 一个无向图 G 有一条欧拉路,当且仅当 G 是连通的,并且有0个或2个奇数度节点。

  • 必要性。如果有一条欧拉路,G 显然就是连通的。假设欧拉路是 $v_0v_1…v_n$,那么对于每个中间的点,它每次出现都对应左右两个边,所以它们“带来”偶数个度。两个端点则带来2个奇数度(如果两个端点相同,带来 0 个奇数度)
  • 充分性。
    • 如果有 2 个奇数度节点,找这两个节点之间的路径 L1;如果没有奇数度节点,找任意闭合路径 L1。
    • G-L1 也构成一个图,其每个节点度必然为偶数,可以找出任意闭合路径L2。
    • 如此重复找到 Ln,直到边全部用完。
    • 由于是连通图,它们之间有共享节点。
    • (得到结论)

对于有向图,有类似结论:有单向欧拉回路当且仅当:

  1. 连通
  2. 每个节点的入度等于出度。或者除了两个节点外其它节点的入度等于出度,这两个节点一个入度比出度多1,一个出度比入度多1

(感觉上面的定理应该从“回路”出发,否则证明和表述会出现)

汉密尔顿图

【定义】汉密尔顿图 一个图,存在一个路径,它经过图上每个节点恰好一次,这个路径叫做 汉密尔顿路径,如果它是回路,叫做 汉密尔顿回路。含有汉密尔顿回路的图叫做 汉密尔顿图

平面图

一个图,如果能画在一个平面上,使边不交叉,叫做 平面图


您的支持将鼓励我继续创作!