集合论与图论课件3
更新时间:2023-10-21 13:15:01 阅读量: 综合文库 文档下载
?顶点连通度和边连通度第三章 连通度、匹配? ?门格尔定理??匹配、霍尔定理本章的特点:(1)理论深;(2)本科基本用不上(计算机体系结构上用到一点),只有
研究生才能用上;(3)只介绍这个领域最基本的概念和一些有用的结果。
一个图是否是连通的,这是图的一个重要性质。
内容:本章首先引入图的顶点连通度和边连通度,由此可以比较两个图中哪个“更加连通”;
接着讨论了它们的一些简单性质; 然后讨论偶图的匹配问题。
?动机和目的?顶点连通度(G)、边连通度(G)???第一节 顶点连通度和边连通度?
?(G)、(G)、(G)关系?????n-顶点连通、n-边连通
1.1 动机和目的
一个图是否是连通的,是图的一个重要性质。于是,我们就想来刻画两个图“连通程
度”的大小,但是刻画两个图“连通程度”的大小方法很多,我们只介绍两个常用的方法:顶点连通度和边连通度
例:树的每个度大于1的顶点都是割点。一个具有割点的连通图,当去掉这个割点时,就产生了一个不连通图。对于一个没有割点的连通图,必须去掉多于一个顶点才有可能得到一个不连通图。于是,具有割点的连通图较之没有割点的连通图的“连通程度”要低。
类似地,树的每条边的都是桥。有桥的连通图,当去掉桥时,就产生了一个不连通图。对于无桥的连通图,要想去掉一些边得到不连通图,至少要去掉两条才有可能得到不连通图。从去掉边来获得不连通图的角度看,有桥的连通图较之无桥的连通图的“连通程度”要低。特别是,一个非平凡树是一个有最少边连通图。
图的顶点和边,在不同应用中有不同意义。在通讯网络中,通讯站是顶点,通讯线路是边。它们的失灵势必危机系统的通讯。所以,网络图的“连通程度”越高,通讯网络越可靠。
这种直观的想法,启发我们建立以下的严格概念:
1.2 顶点连通度(连通度)
定义1 设G=(V,E)是一个无向图,要想从G中得到一个不连通图或平凡图所需要从G中去掉的最少顶点数称为G的顶点连通度,简称连通度。记为???(G)。
说明:(1)对这个定义我们需要说明的是,希望每个图都有顶点连通度。但对完全图Kp,不论去掉哪些顶点,都不会得到不连通图,当去掉p-1个顶点时得到K1-平凡图。为了使这样的连通图也有顶点连通度,所以在定义中加入了“为得到平凡图所需要去掉的顶点的最少数”这一条件。
(2)对于特殊的图顶点连通度是知道的。
K1-平凡图?(K1)?0; 有割点的图?(G)?1; 不连通的图?(G)?0; 完全图Kp (p?2)?(Kp)?p?1。
推论1:若G连通,则?(G)?1;若?(G)?1,则G连通或是非平凡图。
定义2设G=(V,E)是一个无向图,要想从G中得到一个不连通图或平凡图所需要从G中去掉的最少边数称为G的边连通度,简称连通度。记为???(G)。
对于特殊的图边连通度是知道的。
?(K1)?0;当p≥1时,?(Kp)?p?1;
非平凡树T ?(T)?1;有桥的图?(T)?1。
说明:(1)对于连通图来说,边连通度就是割集中最小的那个。
(2)对于一个图来说,割集--可以有多个,但边连通度--却只有一个。 (3)对于非平凡图来说,割集--永远也不能为零(空集),但边连通度--在图不连通时却是零。
(4)连通度与割集的联系和区别?---自己综合。
1.3 顶点连通度?(G)、边连通度?(G)、最小度?(G)之间有以下的关系:
定理1 对任一图G,有
?(G)??(G)??(G)
证 先证λ(G)≤δ(G),若δ(G)=0,则G不连通,从而λ(G)=0。所以,这时λ(G)≤δ(G);若δ(G)>0,不妨设degu =δ(G),从G中去掉与v关联的δ(G)条边后,得到的图中v是弧立顶点。所以,这时λ(G)≤δ(G)。因此,对任何图G有λ(G)≤δ(G)。
其次,证明对任何图G有χ(G)≤λ(G)。若G是不连通的或平凡图,则显然有
χ(G)≤λ(G)=0;
今设G是连通的且非平凡的。若G有桥x,则去掉x的某个端点就得到一个不连通图或平凡图,从而χ(G)=1=λ(G)。所以,这时有χ(G)≤λ(G);若G没有桥,则λ(G)≥2。于是,从G中去掉某些λ(G)边得到一个不连通图。这时从G中去掉这λ(G)条边的每一条的某个端点后,至少去掉了这λ(G)条边。于是,产生了一个不连通图或平凡图,从而χ(G)≤λ(G)。因此,对任何G,χ(G)≤λ(G)。
定理2 对任何整数a,b,c,0≤a≤b≤c,存在一个图G使得
?(G)?a,?(G)?b,?(G)?c。
证 若a=b=c,则图G=Ka+1就是所要求的图。
若a=b Kc+1 Kc+1 a条边 (a) Kc+1 Kc+1 a-1条边 (b) 图1 若a 的图解在平面上画两次,再画出Ka图解,然后在Ka的每个顶点与Kb-a+1的每个顶点间联一条边而得到的图。 若a 引理1 设G=(V,E)是一个图且λ(G)>0,则存在V的真子集A,使得G中联结A中的一个顶点与V\\A中一个顶点的边的总数恰为λ(G). 证 因为λ(G)>0,所以G中有λ(G)条边,把它们去掉后得到一个恰有两个支的不连通图。令其中一个支的顶点集为A,则A是V的一个真子集。由于λ(G)>0,那些被去掉的每一条边,其一个端点在A中,另一个端点在V\\A。这些边当然为λ(G)条。 定理3 设G=(V,E)有p个顶点且δ(G)≥[p/2],则λ(G)=δ(G)。 证 因为δ(G)≥[P/2],所以G是连通的。由定理3.1.1知,λ(G)≤δ(G)。于是只要证明δ(G)≤λ(G)即可。由于G是连通的,所以λ(G)>0。由引理3.1.1,存在V的真子集A使得G中联结A中的一个顶点与V\\A中的一个顶点的边恰有λ(G)条。设|A|=m,则G中两个端点均属于A的边的条数至少为 (mδ(G)-λ(G))/2 于是,假如λ(G)<δ(G),则 (mδ(G)-λ(G))/2>(mδ(G)-δ(G))/2=δ(G)(m-1)/2 若m≤δ(G),则 (mδ(G)-λ(G))/2>m(m-1)/2。 这是不可能的,所以δ(G) m≥δ(G)+1≥[p/2]+1≥(p+1)/2。 同理可证|V\\A|=p-m≥(p+1)/2。因此,|V |>p,矛盾。所以,λ(G)≥δ(G)。于是, λ(G)=δ(G)。 定理4 设G是一个(p,q)图,则 (1 )若q 证(1)若q (1) 若q≥p-1,则有握手定理可知: ?degv?2q,故p?(G)?2q,于是 v?V?(G)??2q/p?。由定理1便得到?(G)??(G)??2q/p?。 1.4 n-顶点连通、n-边连通 定义3 设G是一个图,则 若?(G)≥n,则称G是n-顶点连通的,简称n-连通; 若?(G)≥n,则称G是n-边连通的。 显然,图G是1-连通的,当且仅当是连通的。 定理5 设G =(V,E)是p个顶点的图,p≥3,则G是2-连通图,当且仅当G的任两个不同顶点在G的同一个回路上。 证 <=设G的任意两个顶点在G的同一个回路上,则G是一个没有割点的连通图,所以G是2-连通的。 =>设G是2-连通的,u和v是G的两个不同顶点。施归纳于u与v的距离d(u,v)来证明u与v在一个回路上。当d(u,v)=1,由于χ(G)≥2,所以uv不是桥。由定理2.3.3,边uv必在G的某个回路上,所以u与v在G的某个回路上。 假设对d(u,v)〈k的任意两个不同顶点u和v,u与v必在G的某个回路上。今设 d(u,v)=k,往证u和v在G的某个回路上。考虑G中u与v间的一条长为k的路P:uv1v2 ?vk-1v。显然d(u,vk-1)=k-1。由归纳假设u与vk-1在G的某个回路上。于是,u与vk-1间有两条没有内部公共顶点(即除u与vk-1外)的两条路W,Q。由于χ(G)≥ 2,所以G无割点,从而G-vk-1是连通图。于是,G-vk-1中有u到v的路S。u是W,Q,S的公共顶点。设w是S上从u到v且在Q或W上的最后一个顶点(见图3.1.2)。不妨设w在Q上,则在G中就有含u与v的回路:Q上的u与w间一段后接S上w与v间的那段,然后是边vk-1v,最后是W。 定理6 图G =(V,E)是n-边连通的充分必要条件是不存在V的真子集A,使得G的联结A的一个顶点与V\\A的一个顶点的边的总数小于n 。 证 =>设G是n-边连通的,则χ(G)≥n。若存在V的真子集A,使得G的联结A的一个顶点与V\\A的一个顶点的边的总数j <=若λ(G) 的一个顶点的总数为λ(G) 顶点、边不相交路第二节 门格尔定理? ??门格尔定理凭直观觉得,刻画连通图的“连通程度”,应该与图中任两个不同顶点的路的条数有关。 1927年,门格尔证明了一个图的连通度与联结图中两个不同顶点不相交路的条数有关。 2.1 顶点、边不相交路 定义1 设u与v是图G的两个不同顶点,则 (1)若两条联结u和v的路,除了u与v外没有公共顶点,则称此两条路是联结u和v的不相交路。 (2)若联结u和v的两条路上没有公共边,则称这两条路是联结u和v的边不相交路。 定义2 设G=(V,E)是一个图,S?V,F?E,则 (1)若u和v分别在G-S的两个不同支中,则称图G的顶点集S分离G的两个不邻接 的顶点u和v。 (2)若u和v分在G-F的两个不同支中,则称图G的边集F分离G的两个不同顶点u 和v。 显然,不存在分离G的两个邻接顶点的顶点集。 下述的定理1是门格尔定理的“顶点形式”: 2.2 门格尔定理 定理1(K.Menger,1927)分离图G的两个不邻接的顶点s和t的顶点最少数目等于联结s和t的不相交路的最多数目。(顶点形式) 推论1 图G是n-连通的当且仅当每一对不同顶点间至少有n条不相交路。 定理2 分离一个图的两个不同的顶点s与t的边的最少数目等于不相交s-t路的最多数目。 此定理对多重图也成立。 推论2 图G是k-边连通的当且仅当G的任一对不同的顶点间至少有k条边不相交路。
正在阅读:
集合论与图论课件310-21
水文地质学基础 习题答案07-03
小学生一年级冬天的雪作文[汇编]06-13
房屋登记官试题03-20
12 9.4 新型设备更新经济评价9.5 设备租赁与购置经济评价08-28
爱国主义读书教育活动征文210-28
海南民间社会信仰调查报告12-01
马克思主义哲学原理复习题库02-01
第二章、公司法06-28
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 集合论
- 课件
- 处理医闹有法可医
- 新编实用英语基础教程第1册英语一电子教案
- 高中生物选修1名词解释
- 小学生综合素质评价体系
- 2011年高考在静海县报名的 - 图文
- 传播学概论讲义
- 云南省弥勒一中2016-2017学年高一上学期月考(三)数学试题Word版含答案
- Oracle从头开始
- 森泰南侧矿界附近采空区探测报告 - 图文
- 上海市2018届九年级物理上学期期中试题沪科版
- 马克思主义基本原理题库绪论
- 2015-2016学年天津一中高一(上)期末化学试卷
- 小班对应数学教案反思
- 2013年十月在职联考MBA英语阅读练习题附答案(四) - 学苑教育
- 无人机系统与服务-ok - 图文
- 《甘肃省事业单位聘用合同》填写说明
- 第6章习题答案
- 2010高考语文资料字音、字形汇编大全
- 大体积混凝土温控措施
- 浅谈当前电子证据收集取证中面临的若干问题