伤城文章网 >  > 图论课件特殊平面图与平面图的对偶图-PPT精选文档_图文

图论课件特殊平面图与平面图的对偶图-PPT精选文档_图文


1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

图论及其应用

应用数学学院

1

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

本次课主要内容
特殊平面图与平面图的对偶图
(一)、一些特殊平面图
1、极大平面图及其性质
2、极大外平面图及其性质

(二)、平面图的对偶图

2

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

(一)、一些特殊平面图
1、极大平面图及其性质
对于一个简单平面图来说,在不邻接顶点对间加边, 当边数增加到一定数量时,就会变成非平面图。这样, 就启发我们研究平面图的极图问题。 定义1 设G是简单可平面图,如果G是Ki (1≦i≦4),或 者在G的任意非邻接顶点间添加一条边后,得到的图均是 非可平面图,则称G是极大可平面图。 极大可平面图的平面嵌入称为极大平面图。

3

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

极大平面 图

非极大平 面图

极大平面 图

注:只有在单图前提下才能定义极大平面图。
引理 设G是极大平面图,则G必然连通;若G的阶数大 于等于3,则G无割边。 (1) 先证明G连通。 若不然,G至少两个连通分支。设G1与G2是G的任意两 个连通分支。

4

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

把G1画在G2的外部面上,并在G1,G2上分别取一点u与v. 连接u与v得到一个新平面图G*。但这与G是极大平面图相 矛盾。

(2) 当G的阶数n≥3时,我们证明G中没有割边。
若不然,设G中有割边e=uv,则G-uv不连通,恰有两 个连通分支G1与G2。 设u在G1中,而v在G2中。由于n≥3, 所以,至少有一 个分支包含两个以上的顶点。设G2至少含有两个顶点。 又设G1中含有点u的面是 f , 将G2画在 f 内。

由于G是单图,所以,在G2的外部面上存在不等于点 v的点t。现在,在G中连接点u与t得新平面图G*,它比G 多一条边。这与G的极大性相矛盾。
5

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

下面证明极大平面图的一个重要性质。 定理1 设G是至少有3个顶点的平面图,则G是极大平 面图,当且仅当G的每个面的次数是3且为单图。 注:该定理可以简单记为是“极大平面图的三角形特 征”,即每个面的边界是三角形。 证明:“必要性” 由引理知,G是单图、G无割边且G的每个面的次数 至少是3。

假设G中某个面f的次数大于等于4。记f的边界是 v1v2v3v4…vk。如下图所示。

6

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

v1

vk

v2

f
v3
v4

v5

如果v1与v3不邻接,则连接v1v3,没有破坏G的平面性, 这与G是极大平面图矛盾。所以v1v3必须邻接,但必须在 f 外连线;同理v2与v4也必须在f外连线。但边v1v3与边 v2v4在 f 外交叉,与G是平面图矛盾! 所以,G的每个面次数一定是3. 定理的充分性是显然的。

7

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

推论:设G是n个点,m条边和ф 个面的极大平面图, 且n≥3.则:(1) m=3n-6; (2) ф =2n-4.

证明:因为G是极大平面图,所以,每个面的次数为3. 由次数公式:
2 m ?? d e g (f)? 3 ?
f? ?

由欧拉公式:

??2? n ? m

所以得:

2 m ? 2?n?m 3
8

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

所以得: m ?3 n? 6 又

m ?n? ??2

所以:? ? 2n?4

注:顶点数相同的极大平面图并不唯一。例如:

正20面体

非正20面体

9

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

还在研究中的问题是:顶点数相同的极大平面图的个 数和结构问题。 与极大平面图相对应的图是极小平面图。

2、极大外平面图及其性质
定义2 若一个可平面图G存在一种平面嵌入,使得其所 有顶点均在某个面的边界上,称该图为外可平面图。外可 平面图的一种外平面嵌入,称为外平面图。

外可平面图

外平面图1

外平面图2

10

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

注:对外可平面图G来说,一定存在一种外平面嵌入, 使得G的顶点均在外部面的边界上。这由球极投影法可 以说明。 下面研究极大外平面图的性质。 定义3 设G是一个简单外可平面图,若在G中任意不邻 接顶点间添上一条边后,G成为非外可平面图,则称G是 极大外可平面图。极大外可平面图的外平面嵌入,称为极 大外平面图。

极大外平面图
11

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

引理 设G是一个连通简单外可平面图,则在G中有 一个度数至多是2的顶点。 证明 我们对G的阶数n作数学归纳。 当n≦3时,引理结论显然成立;当n=4时,由于K4不 能是外可平面图,所以,四阶的外可平面图至少有一个 顶点度数不超过2。事实上,更强一点的结论是:当n=4 时,有两个不邻接顶点,其度数不超过2. 设当G是一个阶数小于n的简单连通外可平面图时, 存在两个不邻接顶点,其度数不超过2。

考虑G是一个阶数等于n的简单连通外可平面图。
情形1,如果G有割点x

12

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

x

由归纳假设,G-x的两个不同分支中分别有一个异于 x的顶点z与z1,使得度数不超过2。这说明G中有两个不邻 接顶点, 使得度数都不超过2;

情形2 若G是2连通的。 考虑G的任意一种外平面嵌入。则G的外部面边界一 定是圈。否则,容易推出G有割点。 设C是G的外平面嵌入的外部面边界。若除C外,图 中没有其它的边,则G=C, 显然G中有不邻接点,度数 不超过2;
13

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

若除C外,图中至少有边xy。如下图所示:
x

y

则在C上的两条xy路上的点在G中的两个导出子图H1 与H2是外平面图。 有归纳假设,在H1,H2中分别存在异于x ,y的点z与z1, 使得,它们的度数不超过2.
x

z
y

z1

14

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

定理2 设G是一个有n (n≥3)个点,且所有点均在外部面 上的极大外平面图,则G有n-2个内部面。 证明:对G的阶数作数学归纳。 当n=3时,G是三角形,显然只有一个内部面; 设当n=k时,结论成立。

当n=k+1时,首先,注意到G必有一个2度顶点u在G的 外部面上。(这可以由上面引理得到)
考虑G1=G-v。由归纳假设,G1有k-2个内部面。这样G 有k-1个内部面。于是定理2得证。

15

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

定理3 设G是一个有n (n≥3)个点,且所有点均在外部面 上的外平面图,则G是极大外平面图,当且仅当其外部面 的边界是圈,内部面是三角形。

注:这是极大外平面图的典型特征。 证明:先证明必要性。 (1) 证明G的边界是圈。
设W=v1v2…vnv1是G的外部面边界。若W不是圈,则存 在i与j,使得:1≦i,j≦n,且j-i≠±1(modn),使vi=vj=v.此 时,G可以示意如下:
vj-1 vj+1 vn v1 v2
W

v vi+1
vi-1

16

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

vi-1与vi+1不能邻接。否则W不能构成G的外部面边界。 这样,我们连接vi-1与vi+1:
vj-1

vj+1
vn v1 v2

v

vi+1

vi-1

得到一个新外平面图。这与G的极大性矛盾。

(2) 证明G的内部面是三角形。 首先,注意到,G的内部面必须是圈。因为,G的外部 面的边界是生成圈,所以G是2连通的,所以,G的每个面 的边界必是圈。
17

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

其次,设C是G中任意一个内部面的边界。如果C的长度 大于等于4,则C中一定存在不邻接顶点,连接这两点得到 一个新平面图,这与G的极大性矛盾。又由于G是单图, 所以C的长度只能为3. 下面证明充分性。

设G是一个外平面图,内部面是三角形,外部面是圈W. 如果G不是极大外平面图,那么存在不邻接顶点u与v,使 得G+uv是外平面图。
但是,G+uv不能是外平面图。因为,若边uv经过W的 内部,则它要与G的其它边相交;若uv经过W的外部,导 致所有点不能在在G的同一个面上。 所以,G是极大外平面图。
18

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

定理4 每个至少有7个顶点的外可平面图的补图不是外 可平面图,且7是这个数目的最小者。 我们用枚举方法证明。 证明:对于n=7的极大外可平面图来说,只有4个。如 下图所示。

直接验证:它们的补图均不是外可平面的。 而当n=6时,我们可以找到一个外可平面图G(见下图), 使得其补图是外可平面图。
19

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

G

G

(二)、平面图的对偶图
1、对偶图的定义
定义4 给定平面图G,G的对偶图G*如下构造: (1) 在G的每个面fi内取一个点vi*作为G*的一个顶点; (2) 对G的一条边e, 若e是面 fi 与 fj 的公共边,则连接vi* 与vj*,且连线穿过边e;若e是面fi中的割边,则以vi为顶点
20

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

作环,且让它与e相交。 例如,作出平面图G的对偶图G*

G

21

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

2、对偶图的性质 (1)、G与G*的对应关系
1) G*的顶点数等于G的面数;
2) G*的边数等于G的边数; 3) G*的面数等于G的顶点数; 4) d (v*)=deg( f )
平面图G 对应 对偶图

点 边 环 割边 回路 边割集

面 边 割边 环 边割集 回路

22

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

(2)、定理5
定理5 平面图G的对偶图必然连通 证明:在G*中任意取两点vi*与vj*。我们证明该两点连 通即可! 用一条曲线 l 把vi*和vj*连接起来,且 l 不与G*的任意 顶点相交。 显然,曲线 l 从vi*到vj*经过的面边序列,对应从vi*到 vj*的点边序列,该点边序列就是该两点在G*中的通路。 注: (1) 由定理5知:(G*)*不一定等于G;

23

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

* )*?G 当且仅当G是连通的。 (2) G是平面图,则 (G (习题第26题)
证明:“必要性” 由于G是平面图,由定理5,G*是连通的。而由G*是平 面图,再由定理5,(G*)*是连通的。

* )*?G 得:G是连通的。 所以,由 (G
“充分性” 由对偶图的定义知,平面图G与其对偶图G*嵌入在同一平 面上,当G连通时,容易知道:G*的无界面 f **中仅含G的唯 一顶点v,而除v外,G中其它顶点u均与G*的有限面形成一一 对应,且对应顶点间邻接关系保持不变,即: (G * )*?G
24

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

(3) 同构的平面图可以有不同构的对偶图。 例如,下面的两个图: G1 ? G2

G1

G2

但 G 1* ? G 2*

这是因为:G2中有次数是1的面,而G1没有次数是1的 面。所以,它们的对偶图不能同构。

25

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

例2 证明: (1) B是平面图G的极小边割集,当且仅当

c * ? E ( G * ) e ? B ? C * ? ?
是G*的圈。

(2) 欧拉平面图的对偶图是偶图。

示意图

26

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

证明: (1) 对B的边数作数学归纳。

当B的边数n=1时,B中边是割边

示意图

显然,在G*中对应环。所以,结论成立。 设对B的边数n<k 时,结论成立。考虑n=k的情形。 设c1 ∈B, 于是B-c1是G-c1=G1的一个极小边割集。由归 纳假设:
c * ? E ( G * ) cB ? ? c ? C * ? ?
1 1 1

是G1*的一个圈。且圈C1*上的顶点对应于G1中的面f, f 的 边界上有极小边割集B-e1的边。
27

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

示意图G1

示意图

现在,把e1加入到G1中,恢复G。

由于G是平面图,其作用相当于圈C1*上的一个顶点对 应于G1中的一个平面区域 f, 被e1划分成两个顶点f1*与f2*, 并在其间连以e1所对应的边e1*。 所以,B对应在G*中的C*仍然是一个圈。由归纳法, 结论得到证明。

28

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

充分性: G*中的一个圈,对应于G中

的边的集合B显然是G中的一 个边割集。

示意图

若该割集不是极小边割集,则它是G中极小边割集之 和。而由必要性知道:每个极小边割集对应G*的一个 圈,于是推出B在G*中对应的边集合是圈之并。但这与 假设矛盾。

(2) 因欧拉图的任意边割集均有偶数条边。于是由 (1),G*中不含奇圈。所以G*是偶图。

29

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

例3 设T是连通平面图G的生成树,

E * ? e * ? E (* G ) eE ? () T ? ?
证明:T*=G*[E*]是G*中的生成树。(习题第27题)

示意图

30

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

证明:情形1,如果G是树。 在这种情况下,E* = Φ .则T*是平凡图,而G*的生成树 也是平凡图,所以,结论成立; 情形2,如果G不是树。 因G的每个面必然含有边e不属于E(T),即G*的每个顶点 必然和E*中的某边关联,于是T*必然是G*的生成子图。 下面证明:T*中没有圈。 若T*中有圈。则由例2知:T的余树中含有G的极小边割 集。但我们又可以证明:如果T是连通图G的生成树,那么, T的余树不含G的极小边割集。这样,T*不能含G*的圈。

31

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

又因在G中,每去掉T的余树中的一条边,G的面减少一 个,当T的余树中的边全去掉时,G变成一颗树T. 于是,有:

E ( T * ) ? E () T ? ? ()1 G ? ? V (* G )1 ?

所以,T*是G*的生成树。

32

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

作业
P143---146 习题5 :3,4,5,6,8, 25, 26,27。
其中 25,26,27结合课件学习。

33

1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .2 0 .4 x 0 .6 0 .8 1

Thank

You !

34


搜索更多“图论课件特殊平面图与平面图的对偶图-PPT精选文档_图文”

学习资料共享网 | 兰溪范文 | 伤城文章网 | 省心范文网 | 酷我资料网 | 海文库 | 学习资料共享网 | 兰溪范文 | 伤城文章网 | 省心范文网 | 学习资料共享网 | 兰溪范文 | 伤城文章网 | 省心范文网 | 酷我资料网 | 海文库 | 学习资料共享网 | 兰溪范文 | 伤城文章网 | 省心范文网 | 学习资料共享网 | 兰溪范文 | 伤城文章网 | 省心范文网 | 酷我资料网 | 海文库 | 学习资料共享网 | 兰溪范文 | 伤城文章网 | 省心范文网 | 网站地图

All rights reserved Powered by 伤城文章网 5xts.com

copyright ©right 2010-2021。
伤城文章网内容来自网络,如有侵犯请联系客服。3088529994@qq.com