当前位置：文档之家 › 图论 平面图与对偶图

图论 平面图与对偶图

  • 格式：ppt
  • 大小：44.00 KB
  • 文档页数：7

下载文档原格式

  / 7

合集下载

图论重要结论

图论重要结论

定理1： 图G= (V, E)中所有顶点的度的和等于边数m 的2倍，即：推论1 在任何图中，奇点个数为偶数。

推论2 正则图的阶数和度数不同时为奇数 。

定理2 若n 阶简单图G 不包含Kl+1，则G 度弱于某个完全 l 部图 H ，且若G 具有与 H 相同的度序列，则: 定理3设T 是(n, m)树，则：偶图判定定理: 定理4图G 是偶图当且仅当G 中没有奇回路。

敏格尔定理: 定理5 (1) 设x 与y 是图G 中的两个不相邻点，则G 中分离点x 与y 的最小点数等于独立的(x, y)路的最大数目； (2)设x 与y 是图G 中的两个不相邻点，则G 中分离点x 与y 的最小边数等于G 中边不重的(x, y)路的最大数目。

欧拉图、欧拉迹的判定: 定理6 下列陈述对于非平凡连通图G 是等价的：(1) G 是欧拉图；(2) G 的顶点度数为偶数； (3) G 的边集合能划分为圈。

推论： 连通非欧拉图G 存在欧拉迹当且仅当G 中只有两个顶点度数为奇数。

H 图的判定: 定理H 图，则对V(G)的任一非空顶点子集S定理8 (充分条件) 对于n ≧3的单图G ，如果G 定理9 (充分条件) 对于n ≧3的单图G ，如果G 中的任意两个不相邻顶点u 与v ，有：定理10 (帮迪——闭包定理) 图G 是H 图当且仅当它的闭包是H 图。

定理11(Chv átal ——度序列判定法) 设简单图G 的度序列是(d1,d2,…,dn), 这里，d1≦d2≦…≦m<n/2,或者 dm>m,或者dn-m ≧ n-m,则定理12 设G 是n 阶单图。

若n ≧3且则G 是H 图；并且，具有n 个顶点 条边的非H 图只有C1,n 以及C2,5.定理13 (Hall G 存在饱和X 每个顶推论：若G 是k (k>0)正则偶图，则G 存在完美匹配。

定理14 (哥尼，1931) 在偶图中，最大匹配的边数等于最小覆盖的顶点数。

图论及其应用

图论及其应用
χ（G）表示。若χ（G）=k，就称G是k-点可 色图。
顶点染色
定理：对于任何一个图χ（G）≤ω（G）。 ω（G）为图G的团数，用来描述χ（G）的下 界，其中ω（G）=max{k|Kk属于G}。
顶点染色
给定图G=（V，E）的一个k-点染色。用Vi表示G中染以 第i色的顶点集合（i=1,2，…，k），则每个Vi都是G 的独立集。因而G的每一个K-点染色对应V(G)的一个划 分[V1,V2,…,Vk]，其中每一个Vi是一个独立集。反之 ，给出V(G)的这样一个划分（V1,V2,…,Vk），其中每 一个Vi均是独立集（1≤i≤k），则相应得到G的一个k点染色，称V(G)的这样一个划分为G的一个色划分，每 一个Vi称为色类。因此，G的色数χ(G)就是使这种划 分成为可能最小自然数k。
推论：若G是p(G) 3且g(G) 3的平图，则 q(G) g(G) ( p(G) 2)。 g(G) 2
平面图的性质
推论：任何一个简单平面图G，有 q(G)≤3p(G)-6
推论：设G是简单平面图，则δ(G)≥6.
定理：仅存在5种正多面体，即正四面体、正 方体、正八面体、正十二面体和正二十面体。
定理：每一个平面的色数不超过5
边染色
定义：无环图G的一个正常染色k-边染色（简 称k-边染色）是指一个映射φ：E(G)→{1,2， …，k}，使对G中任意两条相邻的边e1和e2，有 φ(e1)≠φ(e2)。若G有一个正常k-边染色，则 称G是k-边染色的。G的边色数是指G为k-边染 色的最小整数k的值，记为
χ'(G)。若χ'(G)=k，则称G是k-边可色的。
边染色
设G有一个正常k-边染色，置Ei为G中所有染 以第i种颜色的边的全体，则E1，E2，…，Ek 是G的k个边不相交的对集，并且

图论 7-6 对偶图与着色

图论 7-6 对偶图与着色

(c) v*=5,e*=6,r*=3
(d) v*=7,e*=12,r*=7
2、自对偶图 定义7-6.2 如果图G的对偶图G*同构于G,则称G
是自对偶图。
练习 321页 （4）
证明：若图G是自对偶的，则e=2v-2。
若图G是自对偶的，则v=v*，e=e*，即
r*=v=v*=r，e=e*则由欧拉定理v-e+r=2
证明一个图的色数为n，首 先必须证明用n种颜色可以着色 该图，其次证明用少于n种颜色 不能着色该图。
4、对点着色的鲍威尔方法： 第一步：对每个结点按度数递减次序进行排列(相 同度数的结点次序可随意) 第二步：用第一种颜色对第一个结点着色，并按次
序对与前面着色点不相邻的每一点着同样的颜色。
第三步：用第二种颜色对未着色的点重复第二步，
一、对偶图
1、对偶图 定义7-6.1 对具有面F1 ,F2,..., Fn的连通平面图 G=<V,E>实施下列步骤所得到的图G*称为图G的对 偶图（dual of graph）：
如果存在一个图G*=<V*，E*>满足下述条件： （a）在G的每一个面Fi的内部作一个G*的顶点vi* 。 即对图G的任一个面Fi内部有且仅有一个结点vi*∈V*。
边界时，作vi*的一条环与ek相交（且仅交于一处）。
所作的环不与 G*的边相交。 则称图G*为G的对偶图。
v*=r，e*=e， r*=v
例 画出下图的对偶图。
说明：v*=r，e*=e，r*=v。
平面图的对偶图仍满足欧拉定理，且仍是平
面图。
练习 321页（1）
(a) v*=5,e*=8,r*=5
(b) v*=7,e*=13,r*=12
指出肯普的方法 虽不能证明地图着色用四种颜色就

离散数学-图论

离散数学-图论

图论
补图
• 给定一个图G=〈V，E〉，构造另一个图， 它的结点集合与G相同，而边的集合则为 相同完全图中边集合与E的差集，称该图 为原图G相对于完全图的补图，记作~G。
图论
子图
• 设G=〈V，E〉是一个图，如果有另一个 图G‘=〈V’，E‘〉，使得V’是V的子集， E‘是E的子集，则称G‘是G的子图。 • 如果G的子图G‘包含G的所有结点，则称 该子图为G的生成子图。
图论
可达性矩阵
• 设G=〈V，E〉是图，V={v1, v2,…, vn}， 建立n阶方阵P(G)=(aij)，使得 aij =1， 从vi到vj至少存在一条路； aij =0，否则， 则称P(G)为图G的可达性矩阵。 比较：可达性矩阵与邻接矩阵的区别
图论
思考
• 邻接矩阵与可达矩阵之间有什么联系？ • 如何从邻接矩阵计算出可达矩阵？
图论
邻接边
• 关联于同一结点的两条不同的边则称为 邻接边。 • 关联于同一结点的两条相同的边则称为 自回路或环。环既可以是有向的，也可以 是无向的。
图论
有向图的度
• 设〈vi, vj〉是有向图G=〈V，E〉中的任 意一条有向边， vi是该边的起始结点， vj是终止结点。 • 在有向图G=〈V，E〉中，以一结点为起 始结点的边的个数称为该结点的出度； 以一结点为终止结点的边的个数称为该 结点的入度。 • 一结点的出度和入度之和称为该结点的 度数，记作deg(v)。
图论
思考
• 结点的连通性是结点集V上的一个等价关 系！ • 连通性所划分的等价类是什么？
图论
点割集
• 设无向图G〈V，E〉为连通图，若有点 集V1是V的真子集，使得图G在删除了V1 中所有结点后，所得的子图是不连通的， 而在删除了V1的任意真子集后，所得的 子图仍然是连通的，则称V1是G的一个点 割集； • 如点割集中仅有一个结点则称此结点为 割点。

图论习题

图论习题

第三章 平面图
7.若G的顶点数不少于11个，则G c 不是平面图 证明：ε (G ) + ε (G c ) = v(v − 1) 2 , 又ε (G ) ≤ 3v(G ) − 6 则ε (G c ) ≥ 1 （v 2 − 7v + 12） 2 当v ≥ 11时，ε (G c ) > 3v(G c ) − 6, 从而G c 不是平面图
第四章 匹配理论及其应用
• 2.树上是否可能有两个不同的完备匹配？为什么？ • 解：不可能。
设M1，M 2为两个不同的完备匹配，则M1 ⊕ M 2 ≠ φ 且T[M1 ⊕ M 2 ]中的每个顶点的度为2. 由例1.9可知，T中包含圈。这与T为树矛盾。
第五章 着色理论
• 1.求n顶轮的边色数 • hints：n-1
' '
第五章 着色理论
第一条边颜色不变，其余边两色互换。 直至vl −1处无i h 色，多i l -1色； 得出矛盾：v l -1v l 着i h 色; vl 处i h = i l 色出现至少三次； 从而G中i h 和i l -1色边的导出子图中含v l的分支不可能是奇圈， 从而得出矛盾。
第五章 着色理论
• 8. 4名老师4个班级上课问题。 • 计算，一天应分几节课？若每天8节课，需几 间教室？ • hints： ∆(G ) = 16, ε (G ) = 48
16 = 4 一天分4节课 5 48 = 2 需2间教室 5*8
若 13. δ是单图G顶的最小次数，证明；若δ > 1则存在δ − 1边着色， 使与每顶关联的边种有δ − 1种颜色。 h int s : 反证法：设C = (E1 , E 2 ,..., E δ −1 )为G的(δ − 1) − 最佳边着色 构造点列：v1 , v2 ,..., vh , vh +1 ,....., vl ,.... v1处无i 0色，v j v j +1着i j色，且在v j点处i j 色重复出现，仅一个i j-1色；h = i l i 着色调整：v j v j +1着i j-1色( j = 1,2,..., h) 奇圈，颜色互换：E( Eih ∪ Eik )(k = h + 1, h + 2,..., l − 2),

二：平面图、对偶和作色、树和生成树

二：平面图、对偶和作色、树和生成树

一个平面图，一定可以用四种颜色进行着色，
使得邻接的结点都有不同的颜色。
2、着色
图G的正常着色（简称着色）是指对它的每一个结点指定一 种颜色，使得没有两个邻接的结点有同一种颜色。如果图G在着 色时用了n种颜色，我们称G为n-色的。最小着色数用x(G)表示。 虽然目前还没有一个简单的方法，可以确定任一图G是n-色的。 但我们可以用韦尔奇鲍威尔(Welch Powell)对图G着色： a) 将图G中的结点按照度数的递减次序进行排列（这种排列可能 并不是唯一的，因为有些点有相同度数）；
3×5－6＝9＜10
K5
K3,3 推论： 如果图Ｇ＝<Ｖ,Ｅ>是连通的简单平面图，若v ≥ 3，
且每个区域至少由四条边围成，则有ｅ≤２v－４。
作业Ｐ317 (1) (2) (4)
7－6
对偶与着色
这个问题最早起源于地图着色，一个地图中相邻两个国家
以不同的颜色，那么最少需用多少种？
一百多年前，英国格色里(Guthrie)提出用四种猜想即可对地 图进行着色的猜想，1879年肯普(Kempe)给出该猜想的第一个证 明，但到了1890年希伍德(Hewood)发现肯普的证明是错误的，指
1 4
3
5
2 带权树 2
6
三、最小生成树
定义：在图G的所有生成树中，树权最小的那棵生成树， 称作最小生成树。 最小生成树的生成算法： (1)避回路法 (2)破圈法 作业Ｐ327 (3) (6)
deg(v ) 2e
i 1 i
v
故2e ≥6v，所以e ≥3v>3v-6，与ｅ≤3v-6矛盾。 定理3 任意平面图G最多是5-色的。
7-7
一、树
树与生成树
定义： 一个连通且无回路的无向图称为树。树中度数为1

图论第6章

图论第6章

面的连通平面图，则有
n – m + ф =2
（1.2）
证明 对ф 用归纳法。
当ф =1时 ，G 无圈又连通，从而是树，有
于是
n =m+1 n -m+ф =（m+1）- m + 1= 2
设 ф = k 时，（1.2）式成立。
9
当 ф = k+1 时，此时 G 至少两个面，从而有 圈 C。删去 C 中一条边，记所得之图为 G ’ 。并 设 G ’ 的点数、边数和面数依次为 n’ , m’ 和 ф ’, 易知 G ’ 仍连通，但只有 k 个面，由归纳假设有
(1.7）
证明 只需在定理4的证明中将所有不等号改为等号即可得 (1.7)式。
例3 在右图所示的图中， m=12，n = 8，l = 4
有 12×(4-2) = 4×(8-2)， 满足（1.7）式。
例4 证明 K5 和 K 3,3 是不可平面图。
16
证明 若 K5 是可平面图，则因 K5 是至少三个点的简单图， 由推论1，K5 应满足 m≤3n -6。而 K5 中 m=10， n = 5，代
例1
=
平面图
可平面图
3
不可平面图
=
可平面图
不可平面图
4
= 可平面图
= 可平面图
5
定义： 设G 是一个平面图，G 将所嵌入的平 面划分为若干个区域，每个区域的内部连同边界 称为 G 的面，无界的区域称为外部面或无限面。 每个平面图有且仅有一个外部面。设 f 是 G 的一 个面，构成 f 的边界的边数（割边计算两次）称 为 f 的次数，记为 deg(f )。
y1
y2
y3
但如果在 x3 与y1 之间也要修一条铁路，则 可验证满足要求的方案不存在。

第七章 图论

第七章 图论

Graphs/图论
三、子图和补图
定义 无向简单图G＝<V,E>中，若每一对结点间都有 边相连，则称该图为完全图。有n个结点的无向完全 图，记作Kn。 图10：
K 4图
Graphs/图论
定理 4 证明：
n个节点的无向完全图Kn的边数为：(1/2)*n*(n-1)。
在Kn中，任意两点间都有边相连，n个结点中任取两 点的组合数为：cn = (1/2)*n*(n-1) 故Kn的边数为： |E| ＝(1/2)*n*(n-1)。 （证毕）
推论：在一个具有n个结点图中，若从结点u到结点v存在 一条路，则必存在一条从u到v而边数小于n的通路。 删去所有结点s到结点s 的那些边，即得通路。
Graphs/图论
二、无向图的连通性
定义 在无向图G中，结点u和结点v之间若存在一条路， 则称结点u和结点v是连通的。
连通性是结点集合上的一种等价关系。
证明： 设：V1 ：图G中度数为奇数的结点集。 V2：图G中度数为偶数的结点集。 由定理1可知
vv 1
deg( v ) deg( v ) deg( v ) 2 | E |
vv 2 vV
因为
vv 2
deg( v) 为偶数。 deg(v) 和2|E|均为偶数，所以 v v1
b
b
Graphs/图论
四、图的同构
定义 设图G=<V,E> 及G’=<V’,E’>，如果存在一一对 应的映射ｇ：V → V’且ｅ=(vi ，vj)(或<vi ，vj>)是Ｇ的一条 边，当且仅当ｅ’=(g(vi ) ，g(vj))(或 <g(vi ) ，g(vj)>是Ｇ’的 一条边,则称Ｇ与G’同构，记作Ｇ ～ －G’ 。

图论5-8章-习题课

图论5-8章-习题课
6. 设 G 是连通的平面图，证明：G 为二部图当且仅当 G 的对偶图为欧 拉图。
证明：设 G 的对偶为 G*，则 G* 是连通的。必要性： G 为二部图，则 G 中无奇数长度回路，故 G* 中无奇数度顶点，因此 G* 是一个欧拉 图。充分性：G* 是一个欧拉图，则 G* 中无奇数度顶点，故 G 中 无奇数长度回路，因此 G 为一个二部图。
第二十八页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
14. 匈牙利算法求二部图的可增广道：如图，设初始匹配 {(x2, y2), (x3, y3), (x5, y5)}，求其最大匹配。
x1
x2
x3
x4
x5
y1
y2
y3
y4
y5
28
第二十九页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
12
第十三页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
7. 证明：k 色图 G 中至少有 k(k1)/2 条边。
13
第十四页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
7. 证明：k 色图G中至少有 k(k1)/2 条边。 证明：按 G 的一个 k 正常着色方案划分 G 的顶点为 k 个集合 V1,
第四页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
2. 证明：Perterson 图不是平面图。
证二：反证。设其为平面图。由图示，每个面至少有5条边，即 l=5，代 入：
m (n 2)l l2
得： 3m 5(n2) 将 n =10, m =15 代入得 45 40，矛盾。
4
第五页，编辑于星期六：八点 分。
v1
v2

第7章 图论 -5二部图、平面图

第7章 图论 -5二部图、平面图

第9章 图论
2）在G中求最大匹配 把边 (a2,b2) 从 M 中去掉，而把 (a1,b2) 和 (a2,b4) 添加到 M 中， 得到新的匹配M′=(a1,b2),(a2,b4),(a3,b3), (a5,b5)，如下图所示。 对于匹配M′= (a1,b2),(a2,b4),(a3,b3), (a5,b5)重复上述过程， 已找不到M′可扩路。所以M′就是最大匹配。
第9章 图论
在子图H中，任一结点至多与M中的一条边关联且与M1中 一条边关联。因而任一结点的度数是1或2。故H的连通分支是 一条路，或者是一个回路。 如果 H的连通分支是一条路 P，则它是 M 交替路，也是 M1 交替路。如果P的两个端点均与M中的边关联，则P是M1可扩路。 由假设知， M1 是最大匹配，所以，不存在 M1 可扩路，得到矛 盾。如果P的两个端点均与M1的边关联，那么P是一条M可扩路 与题设矛盾。故 P 只能是一个端点与 M 中的边关联，另一个端 点与M1中的边关联，这样P中属于M的边数与属于M1的边数相 等。 如果 H的连通分支是一个回路，回路中的边交替地属于 M 和M1，因而属于M的边数与属于M1的边数相等。 从上面可以看到，H中属于M的边与属于M1的边的数目相 等。再加上既属于M又属于M1的边，可以得出：M中的边数与 M1中的边数相等。所以，M是最大匹配。
第9章 图论
由上述讨论可见：利用可扩路可以增加匹配所含的边数。 不断地寻求G的可扩路，直到再也找不到新的可扩路，就可得 到一个最大匹配。将这个结论写成下列的定理。 定理 7.5.2 设 G=V1,V2,E是二部图， M为G的最大匹配的充分 必要条件是G中不存在M可扩路。 证明：设M为G的最大匹配，下证G中不存在M可扩路。 如果G中存在一条M可扩路，则可以得到比M的边数多1的 匹配，所以M 不是最大匹配，矛盾。所以G 中不存在M 可扩路。 设G中不存在M可扩路，下证M为G的最大匹配。 设M1是最大匹配，证明|M|=|M1|。 考察属于M而不属于M1和属于M1而不属于M中的边，由这 些边连同它们的端点一起构成G的子图H。

图论4-6 平面图

图论4-6 平面图

一个平面图。
有些图形不论怎样改画，除去结点外， 总有边相交。故是非平面图。
2、面、边界 定义4-6.2：设G是一连通平面图，由图中的边所 包围的区域，在区域内既不包含图的结点，也不包含 图的边，这样的区域称为G的一个面，包围该面的诸 边所构成的回路称为这个面的边界。面r的边界的长度 称为该面的次数，记为deg(r)。
证明 假设K3,3图是平面图。
在K3,3中任取三个结点，其中必有两个结点不
邻接，故每个面的次数都不小于4，
由4r≤2e，r≤e/2，即 v-e+e/2≥v-e+r=2， v-e/2≥2， 2v- e ≥ 4， 2v-4≥e。 在K3,3中有6个结点9条边， 2v-4=2×6-4=8<9,与 2v-4≥e 矛盾， 故 K3,3不是平面图。
则 v-e+r=2成立。
（3）设G为k条边时，欧拉公式成立，即 vk-ek+rk=2。
考察的情况。 因为在k条边的连通图上增加一条边，使它仍为连通图， 只有下述两种情况： ①加上一个新结点b，b与图上的一点a相 连，此时vk和ek两者都增加1，而面数rk没
变，故
（ vk +1）-（ ek +1）+ rk = vk-ek+rk=2。
在该面的度数中重复记了两次，故定理结论成立。
4、欧拉定理 定理4-6.2（欧拉定理）
式成立 v–e+r=2 证明
设G为一平面连通图，
v为其顶点数，e为其边数，r 为其面数，那么欧拉公
（1）若G为一个孤立结点，则v=1，e=0，r=1，
故 v-e+r=2成立。
（2）若G为一个边，即v=2，e=1，r=1，
4-6
平面图

图论讲义第7章-平面图

图论讲义第7章-平面图

第七章 平面图§7.1 平面图的概念定义7.1.1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S 。

若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。

例如，下面是三个平面图及其平面嵌入。

根据定义，下列定理是显然的。

定理7.1.1 若图G 是平面图，则G 的任何子图都是平面图。

定理7.1.2 若图G 是非平面图，则G 的任何母图都是非平面图。

定理7.1.3 若图G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。

注：由以上定理知(1) K n ( n ≤4 ) 和 K 1,n (n ≥ 1)及其所有子图都是平面图。

(2) 环边和重边不影响图的平面性。

故以下讨论平面性时总假定图G 是简单图。

定义7.1.2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。

其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。

包围一个面的所有边称为该面的边界。

一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg (R )。

定理7.1.4 平面图G 中所有面的次数之和等于G 的边数的两倍，即其中R 1, R 2, … , R r 是G 的所有面。

证明： 对G 的任何一条边e ，若e 是两个面 R i 和 R j 的公共边界，则在计算R i 和 R j 的次数时，e 各提供了1；若e 只是某一个面的边界，则在计算该面的次数时，e 提供了2。

可见每条边在计算总次数时，都提供2。

因而结论成立。

1deg()2().r ii R G ε==∑定义7.1.3设G为简单平面图，若在G的任意不相邻的顶点u, v之间加边uv 后，所得之图成为非平面图，则称G是极大平面图。

易见K1, K2, K3, K4, K5– e 都是极大平面图。

定义7.1.4 若非平面图G任意删除一条边后，所得之图都是平面图，则称G为极小非平面图。

平面图

平面图

，所以2m 3r, 由Euler公式n-m+r=2，得 m≤3n-6。 用此推论可以判定一个图不是平面图, 例如证明K5不是 平面图: K5中有n=5 m=10 3n-6=3×5-6=9 不满足 m≤3n-6,所以K5不是平面图.

d(f ) 2m 又由于
f F
f F
推论2. 若G是简单连通平面图, 则≤5.
f4 : 边界: v5 v6 v5 f5 : 边界: v6 v5 v8 v8 v5 v7 v6 f6 : 边界: v8 v8 注1：在计算面的度时，割边被计算两次。 注2：每个平面恰有一个无界的面----外部分. F(G): 平面G中面的集合 . r(G)=|F(G)|----面的个数.
f3 : 边界: v1 v3 v2 v1 d(f3)=3
v3*

v5

F3
F1 v1* F2 v2*
对偶图的性质




1. G*是唯一的, 且G*是连通的(∵ 任何两个面都存 在相邻边.) 2. G*是平面图. 3. 若G是平面连通图, 则(G*)*=G. 4. m(G*)=m(G), n(G*)=r(G), d(v*)=d(f). 5. 设C是平面图G的一个圈, S*是G*中与C的各边ei 对应的G*的边集合 , 则S*是G*的一个割集. 证明: ∵ C把G的域分成两部分, ∴ E(G*)-S*把G* 的点分成不连通的两部分.




1976年,美国伊利诺斯(Illinois)大学的阿佩尔 (K.Appel) 和黑肯(W.Haken)把四色问题归结 为2000个不同的组合结构图形,利用三台高速 IBM360计算机对这些图形进行分析，用了 1200机时,近百亿次逻辑判断, 证明了“四色定 理”. 1977年, 证明的细节发在文章上, 争议也从此开 始. 争议的中心是我们能不能、该不该接受这个 证明. 1996年, Robertson, Samders, Seymour, Thomas给出另一个机器证明. 他们利用了更有 效的方法, 使机时减到633小时. 值得一提的是这两个依赖计算机给出的证明中所 使用的方法的核心部分依然的1879年,肯普 (Kempe)给出的证明方法。

图论平面图

图论平面图

定理: K5是非可平面图 证明： 反证法 若G是与K5对应的平面图, v1 , v2 , v3 , v4 , v5 是G 的顶 点， 因为G是完全图，任意两点邻接， 所以 回路 C = v1v2 v3v1 是一个Jordan曲线，则 v4 ∈ int C 或 v4 ∈ extC 。
设 v4 ∈ int C ，（v4 ∈ extC 同理），那么边 (v4 , v1),(v4 , v2 ),(v4 , v3 ) int C1 , int C2 , int C3 这里 将 int C 分成3割区域： C1 = v1v4 v2 v1 , C2 = v2 v4 v3v2 , C3 = v3v4 v1v3 v5 一定在4个区域中的一个区域内，如果 v5 ∈ extC 那么因为 v4 ∈ int C 根据 Jordan定理，边(v4 , v5 ) 一定 与 C 相交， 这就与G是平面图的假设矛盾，对于 v5 ∈ int Ci 可以按照同样的方法处理。
v3*
证明：
若
D
v5
v2
D
D
F1 F2 Dv * 2
D v1 Dv1* D v3
F3
D v4ห้องสมุดไป่ตู้
9.2.10 举例说明下列命题： “平面图G有度 数为1 的顶点，则其对偶图G*含有环；若G有 度数为2的顶点，则G*含有重边。”的逆命题不 真。
9.2.10 举例说明下列命题： “平面图G有度 数为1 的顶点，则其对偶图G*含有环；若G有 度数为2的顶点，则G*含有重边。”的逆命题不 真。 提示：它的对偶图既含环又含重边。
定义:如果G1和G2是同构的,或者通过反复插入或删去度 数为2的结点, 使得它们变成同构的图, 称G1和G2 是在2 D 次结点内同构. D D D D D 例如右边3个图就是 D D D D D D 在2度结点内同构. 定理4.7 (Kuratowski定理)一个图是平面图的充分且必 要条件是它不含有任何与K5、K3,3在2次结点内同构的子 图. (此定理证明略.) 判断下面彼得森(Petersen)图: D v1 D v1 Dv6 v Dv6 v Dv1 Dv8 Dv9 v7 v 10 7 10 Dv3 v2 D D Dv4 D Dv5 v2 D D D Dv5 Dv10 Dv8 Dv9 Dv8 Dv9 Dv2Dv7 Dv6 Dv5 Dv3 Dv4 Dv3 Dv4

图论习题答案1

图论习题答案1

图论习题课作业1，3，6，8，10By jgy•作业1：第一章：1,2,4,12,20,29,35•作业3：第二章：14,28,30第三章：1,5,7,8•作业6：第五章：18,33•作业8：第六章：6,12,17•作业10：第七章10 第八章5,6,8作业1|E(G)|,2|E(G)|2G υυ⎛⎫≤ ⎪⎝⎭⎛⎫⎪⎝⎭1.1 举出两个可以化成图论模型的实际问题略1.2 证明其中是单图证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。

•1.20证明每顶皆二次的连通图是圈•证明：（思路）易证每顶皆二次的连通图中有圈。

设图中最大圈为H，假设除H外还有其他顶点集U，任取u k，因为连通，u k 与H中任意顶均有一条道路，存在H中一顶h j与u k相邻，则h j为三次。

•1.29 证明二分图的子图是二分图•方法一：•定理1.2 图G是二分图当且仅当G中无奇圈•反证：设二分图为G，子图为S，假设S非二分图，由定理1.2知S中有奇圈，则G中有奇圈，这与G是二分图矛盾。

•方法二：•（思路）定义：V(G) = X U Y, X n Y=空, 且X中任二顶不相邻，且Y中任二顶不相邻。

•证明：•(a)第一个序列考虑度数7,第二个序列考虑6,6,2•(b)将顶点v分成两部分v’和v’’•v’ = {v|v= vi , 1≤ i≤ k},•v’’ = {v|v= vi , k< I ≤ n}•以v’点为顶的原图的导出子图度数之和小于•然后考虑剩下的点贡献给这k个点的度数之和最大可能为•2.14 画出带权0.2 0.17 0.13 0.1 0.1 0.08 0.06 0.06 0.07 0.03的huffman 树•排序：①0.03 0.06 0.06 0.07 0.08 0.1 0.1 0.13 0.17 0.2•②0.06 0.07 0.08 0.090.1 0.1 0.13 0.17 0.2•③0.08 0.090.1 0.1 0.130.13 0.17 0.2•④0.1 0.10.130.13 0.170.17 0.2•⑤0.130.13 0.170.17 0.20.2•⑥0.170.17 0.20.2 0.26•⑦0.20.20.26 0.34•⑧0.26 0.34 0.4•⑨0.4 0.60.030.060.090.030.060.090.060.070.130.030.060.090.060.070.130.170.08①③②0.030.060.090.060.070.130.170.080.10.10.20.130.26Huffman 树为0.170.340.20.40.61•2.28证明T是顶数至少为2的树，则T是二分图•证明1：•定理1.2 图G是二分图当且仅当G中无奇圈•T是树，所以T中无奇圈，由‘图G是二分图当且仅当G中无奇圈’知T是二分图。

图论课件特殊平面图与平面图的对偶

图论课件特殊平面图与平面图的对偶

嵌入法
首先将原始图嵌入到平面 上，然后根据嵌入的图构 造对偶图。
Hale Waihona Puke 递归构造法通过对原始图的递归分割， 构造出对偶图。
04
特殊平面图与平面图的对 偶关系
欧拉图与对偶图的关系
欧拉图
一个连通图，其每一条边都恰好在一个欧拉路径 上。
对偶图
将原图的每条边替换为其对偶边，即反转边的方 向。
关系
如果一个图是欧拉图，那么其在对偶图中也是欧 拉图。
在其他领域的应用
生物信息学
在生物信息学中，特殊平面图和平面图的对偶可以用于描述基因组序列和蛋白质 相互作用网络。
电子工程
在电子工程中，特殊平面图和平面图的对偶可以用于描述电路设计和信号处理。
THANKS
感谢观看
经过原图每条边至少一次的回路。
表现
在对偶图中，欧拉路径和哈密顿路径的方向也会发生反转。
05
特殊平面图和平面图对偶 的应用
在计算机科学中的应用
1 2
路由算法
在计算机网络中，对偶图可以用于描述数据包的 传输路径，通过对偶图的计算可以找到最优路径。
计算机图形学
在计算机图形学中，特殊平面图和平面图的对偶 可以用于描述图形的渲染和光照计算。
02
特殊平面图
欧拉图
定义
一个连通图，它的边可以按照某 种顺序排列，使得每条边恰好被 走过一次，则称这个图为欧拉图 。
判定条件
一个连通图是欧拉图当且仅当存 在一个顶点，从它出发的边数等 于它与其它顶点的度数之和。
哈密顿图
定义
一个连通图，它的顶点可以由一个顶点开始遍历一次（包括 起点），且只遍历一次所有顶点，则称这个图为哈密顿图。
哈密顿图与对偶图的关系

图论课件-特殊平面图与平面图的对偶

图论课件-特殊平面图与平面图的对偶
图论课件-特殊平面图 与平面图的对偶
https://
REPORTING
目录
• 引言 • 平面图的对偶 • 特殊平面图01
引言
REPORTING
WENKU DESIGN
特殊平面图与平面图对偶的定义
特殊平面图
哈密顿图与对偶图的关系
01
02
03
哈密顿图的对偶图是一 个哈密顿图，其顶点对 应于原图的边，边对应
于原图的顶点。
哈密顿图的哈密顿路径 和哈密顿回路在对偶图 中表现为一个简单的闭
环。
哈密顿图的度数限制为4， 即每个顶点的度数不能超
过4。
PART 04
特殊平面图与平面图对偶 的应用实例
REPORTING
电路设计中的对偶图应用
在电路设计中，对偶图被用于表示电路元件之间的连接关系。通过将对偶图应用 于电路设计，可以简化电路分析和设计过程。
对偶图可以帮助电路设计师更好地理解电路的结构和功能，从而进行有效的电路 优化和改进。此外，对偶图还可以用于电路仿真和测试，以确保电路的性能和可 靠性。
网络设计中的对偶图应用
无环平面图的判定：一个平面 图是无环的当且仅当它的所有 面都是三角形。
欧拉图
欧拉图是指存在一条路径，该路径可以遍历其所有边且每条边只遍历一次的图。
欧拉路径是指遍历欧拉图的路径，而欧拉回路是指起点和终点是同一点的欧拉路径。
欧拉定理：一个连通图是欧拉图当且仅当它的所有顶点的度都是偶数。
哈密顿图
哈密顿图是指存在一条路径，该路径 可以遍历其所有顶点且每条边只遍历 一次的图。
对偶图的性质
对偶图的节点数等于原平面图 的边数，对偶图的边数等于原
平面图的节点数。
对偶图是二部图，即其节点 可以划分为两个不相交的子 集，使得每条边都连接这两

《图论》第5章 平面图

《图论》第5章 平面图
下不需作严格区分。
5.1 平面图及其性质
[区域] 由平面图的边包围而成，其中不含图的顶点。 也称为面。包围域 R 的所有边组成的回路称为该 域的边界，回路长度称为该域的度，记为deg(R)。
[例]
v2
v1
R1
v3
v5 各域的边界：
v4
v6 R2
R0
v7
R3
R0: v1 v2 v4 v5 v7 v7 v4 v3 v1 R1: v1 v2 v4 v3 v1 R2: v4 v5 v7 v4 v6 v4 R3: v7 v7
deg(R0)=8, deg(R1)=4, deg(R2)=5, deg(R3)=1
5.1 平面图及其性质
[定理5-1-1] 平面图 G 的所有域的度之和等于其边数 m 的2倍，即：
r
deg(Ri ) 2m
i1
➢ 域的度也称为域的次数。
[内部面和外部面] 由平面图的边包围且无穷大的域称 为外部面。（如上例的域 R0 为外部面）
5.1 平面图及其性质
[二部图] 图 G=(V, E)，若 V 可划分成 V1 和 V2 两部分， 使得：①任给 v1 V1，若( v1, v2 ) E ，则必 v2V2 ；②任给 v2 V2，若( v1, v2 ) E ，则必 v1V1 。则称G为一个二部图。
[例]
5.1 平面图及其性质
[完全二部图] 设 G=(V, E)为一个二部图， V1 和V2 如 上所述，若 (v1) (v2)(v1V1, v2V2 ( v1, v2 ) E)， 则称 G 为一个完全二部图，记为 Kn1, n2。 ( n1 =|V1| ，n2 =| V2 |)
m (nk 1)l l 2
[证明]
由欧拉公式： nm+d =k+1 得 d = k+1+mn 由[定理5-1-1]：2mld = l (k+1+mn)= (k+1n)l +ml 联立得不等式： (l2)m (n k1)l
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第四章 平面图与对偶图
4.1 平面图 4.2 平面图上的欧拉公式
4.3 对偶图
4.1 平面图
平面上的图(plane graph)：指的是画在平面上的一个图形，它的 所有的边都不相交（除顶点外）。
平面图(planar graph)：如果一个图经过重画之后，可以画成平面 上的一个边不相交的图形，则该图便称为平面图（可嵌入平面 (embeding)）。 Jordan curve：自身不相交的):
1）如果两个图能够从一个图G出发，通过在G的边上插入有限多 个2次顶点得到，则称这两个图是同胚。 2）如果两个图是同构的或通过反复插入或消去2次顶点后是同构 的，则称这两个图是同胚。 Th4.2：一个图为平面图当且仅当它不含与k5或k3.3同胚的子图。
Th4.3：一个图为平面图当且仅当它不含可以缩成k5或k3.3的子图。
4） G* 是连通的且为平面嵌入的。
Lemma4.10：设G为n，m和f且为平面上的连通图，其对偶图G*有n*， m*和f* n*= f， m= m*和n =f*。 Th4.11：设G为平面上的连通图，则G**≌G。 Th4.12：设G为平面上的连通图且G* 为G的对偶图，则G的边集构 成G的一个圈对应的G*的边集构成G*的一个割集。 Corollary4.13：设G为平面上的连通图且G* 为G的对偶图，则G的边 集构成G的一个割集对应的G*的边集构成G*的一个圈。
Th:一个图是可嵌入平面它是可嵌入球面。 Th4.4：设Ｇ是一个连通的平面上的图，n，m和f分别表示图Ｇ的顶 点数，边数和面数，则n-m+f=2。 Cor４.5：设Ｇ为具有n个顶点，m条边，f个面和k个分图的平面上的 图，则n-m+f=k+1。
Cor４.６：Ｇ<V,E>为简单连通平面图|V|=n（n>2）和|E|=m
Jordan closed curve： Jordan curve 两个端点重合。
Jordan curve theorem：C为在平面上的Jordan closed curve，平面 的其余部分被分成不相交的开集，分别称为C的外部和内部，则 连接内部和外部点的任何连续曲线必与C相交。 Th4.1：k5和k3.3不是平面图。
１）m≤3n-6； ２）如果G中不含三角形，则m ≤2n-4。
Cor４.7： k5和k3.3不是平面图。
Th4.8：每个简单平面图均包含一个次数最多为5的顶点。
下面内容见书： 一个图的厚度： Th4.9
4.3 对偶图
1. 对偶图(dual graph)： 任意一个平面上的图G， 如果：1）在G 的每个面Fi中选定一个点vi*作为顶点；
交叉数：为G画在平面上时，它的边出现相交的最少可能的数目。 记为：Cr(G)。
4.2 平面图上的欧拉公式
平面上的一个点x不与Ｇ相交的点：x既不是Ｇ的顶点也不是Ｇ的任 何一条边上的点。
Ｇ的包含ｘ的面：为平面上所有可以从ｘ出发通过一条不与Ｇ相交 的Jordan曲线而能达到的点的集合。
无穷面
Ｇ可嵌入曲面Ｓ：如果一个图Ｇ能够画在一张曲面Ｓ上，使得它的 边除了顶点外再无其它交点。
2）对应于G的每条边e，画一条线e*，它只与e相交，而不与 G的其它边相交，并且连接位于e两边的面Fi中的顶点vi*作为边。
这样构成的图称为图G的对偶图，记为G*。 Note:1）G中的每个悬点都产生G*的一个自环； 2）G中多于一条公共边的面，便产生多重边；
3）H G 但是H* G* 不一定；