图论第3章讲义
- 格式:ppt
- 大小:2.17 MB
- 文档页数:54
数学竞赛:图论讲义大连市第二十四中学 邰海峰重要的概念与定理完全图 每两个顶点之间均有边相连的简单图称为完全图,有n 个顶点的完全图(n 阶完全图)记为n K .顶点的度 图G 中与顶点v 相关联的边数(环按2条边计算)称为顶点v 的度(或次数),记为()d v .()G δ与()G ∆分别表示图G 的顶点的最小度与最大度.度为奇数的顶点称为奇顶点,度为偶数的顶点称为偶顶点.树 没有圈的连通图称为树,用T 表示,其中度为1的顶点称为树叶(或悬挂点).n 阶树常表示为n T .k 部图 若图G 的顶点集V 可以分解为k 个两两不相交的非空子集的并,即1,()ki i j i V V V V i j ===∅≠并且同一子集i V (1,2,,)i k =内任何两个顶点没有边相连,则称这样的图为k 部图,记作12(,,,;)k G V V V E =. 2部图又叫做偶图,记为(,;)G X Y E =.完全k 部图 在一个k 部图12(,,,;)k G V V V E =中,i i V m =(1,2,,)i k =,若对任意,,(,,1,2,,)i i j j v V v V i j i j k ∈∈≠=均有边连接i v 和j v ,则称图G 为完全k 部图,记为12,,,k m m m K .欧拉迹 包含图中所有边的迹称为欧拉迹.起点与终点重合的欧拉迹称为闭欧拉迹.欧拉图 包含欧拉迹的图为欧拉图. 欧拉图必是连通图.哈密顿链(圈) 经过图上各顶点一次并且仅仅一次的链(圈)称为哈密顿链(圈).包含哈密顿圈的图称为哈密顿图.平面图 若一个图G 可画在平面上,即可作一个与G 同构的图G ',使G '的顶点与边在同一平面内,且任意两边仅在端点相交,则图G 称为平面图.一个平面图的顶点和边把一个平面分成若干个互相隔开的区域,称为平面图的一个面,在所有边的外面的面称为外部面,其余的称为内部面.竞赛图 有向完全简单图称为竞赛图.有n 个顶点的竞赛图记作n K .有向路 在有向图(,)D V U =中,一个由不同的弧组成的序列12,,,n u u u ,其中i u 的起点为i v ,终点为1(1,2,,)i v i n +=,称这个序列为从1v 到1n v +的有向路(简称路),n 为这个路的长,1v 为路的起点,1n v +为路的终点.若11n v v +=,则称这个路为回路.定理1 设G 是n 阶图,则G 中n 个顶点的度之和为边数的2倍.定理2 对于任意图G ,奇顶点的个数一定是偶数.定理3(Turan 定理) 有n 个顶点且不含三角形的图G 的最大边数为24n ⎡⎤⎢⎥⎣⎦.定理4 图G 为偶图,当且仅当G 中不含长度为奇数的圈.定理5 若树T 的顶点数2,则T 中至少有两个树叶.定理6 若数T 有n 个顶点,则T 的边数1e n =-.定理7 设T 是有n 个顶点、e 条边的图,则下列命题等价:⑴ 图T 是树; ⑵ 图T 无圈,且1e n =-; ⑶ 图T 连通,且1e n =-.定理8 n 阶连通图中以树的边数最少,且n 阶连通图必有一个子图是树.定理9(一笔画定理) 有限图G 是一条链或圈(可以一笔画成)的充要条件是G 是连通的,且奇顶点的个数为0或2. 当且仅当奇顶点个数为0时,连通图G 是一个圈.定理10 在偶图12(,;)G V V E =中,若12V V ≠,则G 一定无哈密顿圈.若1V 与2V 的差大于1,则G 一定无哈密顿链.定理11 设G 是(3)n n 阶简单图,且对每一对顶点,v v '有()()1d v d v n '+-,则图G 有哈密顿链.定理12 设G 是(3)n n 阶简单图,且对每一对不相邻的顶点,v v '有()()d v d v n '+,则图G 有哈密顿圈.定理13 设G 是(3)n n 阶简单图,若每个顶点的度()2n d v ,则图G 有哈密顿圈. 定理14 若图G 有哈密顿圈,从G 中去掉若干个点12,,,k v v v 及与它们关联的边得到图G ',则图G '的连通分支不超过k 个.定理15(欧拉公式) 若一个连通的平面图G 有v 个顶点、e 条边、f 个面,则2v f e +-=. 定理16 一个连通的平面简单图有v 个顶点、e 条边,则36ev -,对于连通的偶图,则有24ev -. 定理17 一个图是平面图当且仅当它不包含同胚于5K 或3,3K 的子图.定理18 设n 阶竞赛图n K 的顶点为12,,,n v v v ,则11(1)()()2n n i i i i n n d v d v +-==-==∑∑,且2211[()][()]n ni i i i dv d v +-===∑∑. 定理19 竞赛图中出度最大的点称为“优点”,“优点”到其余各点都有长度不超过2的链. 定理20 竞赛图n K 中存在一条长为1n -的哈密顿路. 定理21 竞赛图(3)n K n 中有一个回路是三角形的充要条件是有两个顶点,v v '满足()()d v d v ++'=.定理22(Ramsey 定理) 任意2色完全图6K 中必存在同色三角形.例题选讲例1 某天晚上21个人之间通了电话,有人发现这21人共通话102次,且每两人至多通话一次.他还发现,存在m 个人,第1个人与第2个人通了话,第2个人与第3个人通了话,……, 第1m -个人与第m 个人通了话,第m 个人又与第1个人通了话,他不肯透露m 的具体值,只说m 是奇数.求证: 21个人中必存在3人,他们两两通了话.证:用21个点表示21个人,若两人通电话则对应两点连一条边,构成图G .由已知,G 中存在一个长度为m 的奇圈.要证: G 中存在三角形.设图G 中长度最短的奇圈为C ,长度为21k +.若1k =,则C 为三角形.若2k ,设C 为12211k v v v v +,则i v 与j v 之间无边(1,21,1(mod 21)i j k j j k +-≡±+),否则,若i v 与j v 相邻,则圈12211i j k v v v v v v +与圈1i i j i v v v v +长度之和为23k +,故其中必然有一个长度小于21k +的奇圈,与C 最短矛盾.假设除1221,,,k v v v +外的21(21)202k k -+=-个点无三角形,由Turan 定理,它们至多连了22(202)(10)4k k ⎡⎤-=-⎢⎥⎣⎦条边. 又其中任意一点不与C 的相邻两点相邻(否则存在三角形),所以它至多与C 中k 个点相邻.故总边数为221(202)(10)k k k k ++-+-22210021102(1)102(21)101k k k =++-=----=(2k ).与图G 共有102条边矛盾. 故图G 中存在三角形,即存在三个人两两通话.例2 45个校友聚会,在这些人中,任意两个熟人数目相同的校友互不认识.问在参加校友聚会的所有人中,熟人最多的人的数目最多是多少?解: 用45个点表示45个人,若两人认识,则对应两点间连一条边,得图(,)G V E =.设共有m 个人熟人最多,每人有t 个熟人,这些人对应的点构成集合X ,其余的人对应点构成集合Y ,显然X Y V =,X Y =∅.由题意知,X 中任何两点不相邻,且(),(1,2,,)i d v t i m ==,G 中各顶点的度的最大值()G t ∆=.下面证明:22m. 若23m ,则X 中至少有23个点,每点的度为t ,且任意两点不相邻,则从X 中发出的另一端是Y 中点的边共有23t 条,而22Y .所以,Y 中至少有一个点的度大于t ,与()G t ∆=矛盾.当22m =时,构造完全偶图22,23G K =,满足题意. 故熟人最多的人数最多为22人.例3 在17名科学家中,每人都和其它人通信.在他们的通信中只讨论三个题目.而且任意两名科学家通信时,只讨论一个题目.证明,其中至少有三名科学家,他们相互通信时,讨论的是同一个题目.证: 用顶点代表科学家,两人相互通信则连上一条边.若两人在通信中讨论第i (1,2,3)i =个题目,则在此边上染上第i 种颜色. 在这个三色完全图17K 中,任取一个顶点, 从它出发的16条边中,至少有染上某一种颜色(设为第i 种颜色)的边的数目不小于6.从其中取出6条第i 种颜色的边,如果这些边的另一端点所构成的子图6K 中含第i 色边,这就构成第i 色三角形. 否则,6K 就是两色完全图,由Ramsey 定理知,其中必有单色三角形.这就是说,有三位科学家在通信中讨论的是同一题目.证毕.例4 设n 个新生中,任意3个人中有2个人互相认识,任意4个人中有2个人互不认识,求n 的最大值.解: 所求n 最大值为8.8n =时,如右图,其中128,,,A A A 表示8两点相邻当且仅当两人认识.下面设n 个学生满足题设要求,证明8n.为此,先证明如下两种情况 不可能出现.⑴若某人A 至少认识6个人,记为126,,,B B B .由Ramsey 定理知, 这6个人中或存在3个人互不认识(与已知任意3个人中有2个人互相认识 矛盾),或存在3个人互相认识,这时,A 与这3个人共4个人两两互相认识,与已知矛盾.⑵若某人A 至多认识5n -个人,则剩下至少4个人均与A 互不认识,从而,这4个人两两认识,与已知矛盾.当10n 时,⑴与⑵必有一种情况出现,故此时n 不满足要求.当9n =时,要使⑴与⑵都不出现,则此时每个人恰好认识其他5个人,于是,这9个人产生的“朋友对”的数目为952N ⨯∉,矛盾. 由上述讨论知,8n .3 4 A A综上,n 的最大值为8.例5 设(3)n n >是整数, 在一次会议上有n 位数学家,每一对数学家只能用会议规定的n 种办公语言之一进行交流,对于任意3种不同的办公语言,都存在3位数学家用这3种语言互相交流.求所有可能的n ,并证明你的结论.证:当n 位奇数时,结论成立.原命题等价于将完全图n K 的边染以n 种颜色之一,使得对于任意3种颜色,都存在3个顶点,它们相互所连的边为这3种颜色.由于n 种颜色有3n C 种选取方法,而顶点也有3n C 种选取方法,这就意味着每3个顶点相连的边一定被染为确定的3种颜色,不能染为其他情况的颜色,反之亦然.特别地,对于每一个三角形其3条边为3种不同颜色.固定颜色S ,恰好有21n C -个三角形,其有一条边为颜色S ,而颜色为S 的边可以与其他2n -个顶点构成2n -个三角形.于是,有21122n C n n --=-条边被染为颜色S .所以,n 不能为偶数. 当n 为奇数时,将n 个顶点分别记为顶点1,2,,n ,n 种颜色记为12,,,n S S S ,连结顶点,i j 的边染为颜色t S ,其中(mod )t i j n ≡+.则对于任意3种颜色123,,t t t S S S ,有同余方程组123(mod )(mod )(mod )i j t n j k t n k i t n +≡⎧⎪+≡⎨⎪+≡⎩. 利用消元法,可得在{}1,2,,n 内有唯一的解(,,)i j k ,且,,i j k 互不相同. 所以,对于任意3种颜色,存在唯一的三角形,其3条边的颜色为这3种颜色.例6 一个元素都是0或1的方阵称为二进制方阵. 若二进制方阵其主对角线(左上角到右下角的对角线)以上(不包括主对角线)的元素都相同,而且主对角线以下(不包括主对角线)的元素也相同,则称它为一个“好方阵”. 给定正整数m . 证明:存在一个正整数M ,使得对任意正整数n M >和给定的n n ⨯二进制方阵n A ,可选出整数121n m i i i n -<<<,从n A 中删除第12,,,n m i i i -行和第12,,,n m i i i -列后所得到的二进制方阵m B 是“好方阵”.证:记n A 中第i 行,第j 列的元素为,i j a ,n K 表示n 阶完全图. 我们对n K 的边按如下方式染色:对于连接顶点,(1)i j i j n <的边⑴ 若,,0i j j i a a ==,则染红色; ⑵ 若,,0,1i j j i a a ==,则染绿色;⑶ 若,,1,0i j j i a a ==,则染蓝色; ⑷ 若,,1i j j i a a ==,则染白色.按照上面的染色方式,则一个单色完全子图m K 对应于n A 的一个“好子方阵”.事实上,若12,,,,m i i i v v v 是m K 的顶点,我们可以删去指标12{1,2,3,,}\{,,,}m j n i i i ∈的n m -行和n m -列,得到一个“好子方阵”m B .我们只需取M 使得,对任何n M >,四染色的n K 必定包含一个单色子图m K .根据Ramsey 定理,我们可取(,,,)M R m m m m =即可.例7 现有十个互不相同的非零数.现知它们之中任意两个数的和或积是有理数.证明:每个数的平方都是有理数.证:考查其中任意6个数.作一个图,在它的6个顶点上分别放上我们的6个数.如果某两个数的和为有理数,就在相应的两个顶点之间连一条蓝边;如果某两个数的积为有理数,就在相应的两个顶点之间连一条红边.由Ramsey 定理,此图中存在一个同色三角形.⑴ 若存在蓝色三角形,则表明存在三个数,,x y z ,使得,,x y y z z x +++都是有理数.因而()()()x y z x y z +++-+2x =为有理数,亦即x 为有理数.同理可知y 和z 也都是有理数.此时我们再来观察其余的任意一个数t .显然,无论由xt 的有理性(由已知,所有的数均非0),还是由x t +的有理性,都可以推出t 为有理数.所以此时10个数都是有理数.⑵ 若存在红色三角形,则表明存在三个数,,x y z ,使得,,xy yz zx 都是有理数.因而()()xy zx yz2x =为有理数,同理可知2y 和2z 也都是有理数.如果,,x y z 三者中至少有一个为有理数,那么只要按照前一种情况进行讨论,即可得知我们的10个数都是有理数.现在设x =其中a 为有理数,而1m =±.由于xy b ==是有理数,所以y===其中c m ≠为有理数.再观察其余的任意一个数t ,若xt 或yt 为有理数,则经过与上述类似的讨论,可知t =其中d 为有理数,因而2t 为有理数.而若x t +与y t +都是有理数,则()()x t y t +-+是有理数,但()()(x t y t m c +-+=-,矛盾.综上,我们已证或者每个数都是有理数,或者每个数的平方都是有理数.练习1.旅行团一行6人到一个城市观光,此城市开放15个景点,每人可选择若干个景点参观(亦可不选或全选). 求证: 或者必有3人,他们选择的景点各不相同; 或者必有4人,在他们选择的景点中有相同的.2.设一次至少有5人参加的循环赛的结果满足如下条件:若A 胜B,则胜A 而负于B 的人数不少于胜B 而负于A 的人数.证明:对任意两人,x y ,总有另外两人,z w ,使得若x 胜y ,则y 胜z 、z 胜w 、w 胜x .3.在一个足球联赛里有20支球队.第一轮它们分成10对互相比赛,第二轮也分成10对互相比赛(每支球队两轮比赛的对手不一定不同).求证:在第三轮开赛之前,一定可以找到10支球队,它们两两没有比赛过.4.某国际社团共有 1978 名成员,他们来自六个国家,用号码1,2,3,,1978给成员编号.证明至少有一名成员,他的编号是他的某个同胞的 2 倍,或者是两位同胞编号之和.练习题答案1.证:用6个点表示6个人,再用15个点表示15个景点.若某人选择了某个景点,则在相应两点之间连一条边,得一偶图.以i N 表示点i v 在图中的邻域,它表示第i 个人选择的景点的集合(1,2,,6i =).假设结论不真,则⑴任意三个i N 有公共元,且⑵任意四个i N 无公共元.由⑴知,对每个i N ,在{},16j N j i j ≠中每取两个与i N 的交均非空,故可确定i N 的一个元素,用这样的方式可确定2510C =个元素.由⑵知,这些元素各不相同,故每个i N 至少有2510C =个不同的元素.对每个(16)i i 这样做,得到25660C =个元素.又由⑵知,每个元素至多是3个i N 的公共元,故每个元素至多重复计算3次.故其中不同的元素至少有256203C =个,即至少有20个景点,矛盾. 2. 证:由题意知,若A 胜B 且存在胜B 而负于A 的人,则必存在胜A 而负于B 的人.任取两选手,x y 且x 胜y ,分三种情况讨论:⑴若存在w 胜y 且有x 胜y 而负于w ,根据条件,存在z 胜w 而负于y ;⑵若存在z 同时负于,x y ,则y 胜z 而x 同时胜,y z ,同情形⑴;⑶若不存在有同时胜(或同时负于),x y 的人,在其余3人中,胜x 而负于y 的至少有2人,设为,w z ,且z 胜w ,则,,,x y z w 符合题意.3. 证:用20个点表示20个球队,第一轮互相赛过的队之间连红线,第二轮互相赛过的队之间连蓝线,则每个点都连有一红一蓝两条边,从而整个图必由一个或若干个偶圈组成.在每个偶圈中可以选出半数定点,任两个不相邻,共选出10支球队,两两未赛过.4.证: 用顶点表示成员,并加上编号.于是任意两顶点,i j v v 编号差大于 0 而小于 1978.如果这个差是第(16)i i 国成员的编号,则将(,)i j v v 边染上第i 种颜色i C ,这样我们就用六种颜色染了1978K 的所有边. 以下首先证明,六色完全图1978K 中必定含有单色三角形. 取1978K 的任一顶点v ,与它关联的 1977 条边分为 6 种颜色,于是其中必有一种颜色的边至少有197713306⎡⎤+=⎢⎥⎣⎦条. 不妨设12330,,,vu vu vu 是1C 色边.如果1978K 中以12330,,,u u u 为顶点的完全子图330K 中含有1C 色边(,)(1,330)i j u u i j ,则i j vu u 为1C 色三角形,命题得证.如果330K 不含1C 色边,则330K 是五色完全图.从它的顶点1u 引出的 329 条边中至少有3291665⎡⎤+=⎢⎥⎣⎦条边同色(1C 色之外的某色),不妨设1213167,,,u u u u u u 边为2C 色.以2367,,,u u u 为顶点的完全子图66K 中如果有2C 色边(,)(2,67)s t u u s t ,那么在1978K 中就有2C 色三角形1s t u u u ,命题得证.若此66K 中没有2C 色边,则此66K 是4色完全图.由66K 的顶点2u 伸出的65条边,共4种颜色,至少有651174⎡⎤+=⎢⎥⎣⎦条边是除12,C C 外的某种颜色.不妨设2324219(,),(,),,(,)u u u u u u 是3C 色边.66K 中以3419,,,u u u 为顶点的完全子图17K 中若含3C 色边(,)(3,19)p q u u p q ,则2p q u u u 为3C 色三角形.否则17K 为三色完全图.由例3可知必有单色三角形.因此六色完全图1978K 中必有单色三角形.其次,设三角形xyz 是1978K 中的i C 色三角形.其中x y z >>,由染色方法,若a x y =-, b y z =-,c x z =-,则,,a b c 都是第i 国成员的编号.显然c a b =+,如果a b =,那么2c a =.证明完毕.。
课程类型数学
“托兰定理”讲义编号:
托兰定理在求极值的图论问题中具有重要作用,本讲主要介绍该定理及其相关方法。
定理:有n个顶点且不含三角形的简单图G中最多有[n2/4]条边。
证明
1
例1 设n≥2。
平面上已给2n个点,每三点不共线。
在这些点之间连n2+1条线段。
证明至少形成n个以已知
点为顶点的三角形。
【解答】
例2 由n个点和这些点之间的l条连线段组成一个空间四边形,其中n=q2+q+1,l≥1/2q(q+1)2+1,q≥2,q∈N。
已知此图中任四点不共面,每点至少有一条连线段,存在一点至少有q+2条连线段。
证明:图中必存在一个空
间四边形(即由四点A,B,C,D和四条连线段AB,BC,CD,DA组成的图形)
2。
图论图的基本概念和性质 图的连通性及可达性 图的矩阵表示Euler图与Hamilton图 平面图对偶图与着色树与生成树根树及其应用图论简介一、图的基本概念一个图是一个序偶<V,E>,记为G=<V,E>,其中:V={v1,v2,v3,…,v n}是一个有限的非空集合,v i(i=1,2,3,…,n)称为结点,简称点,V 为结点集;E={e1,e2,e3,…,e m}是一个有限的集合,e i(i=1,2,3,…,m)称为边,E为边集,E中的每个元素都有V中的结点对与之对应。
二、图的类型1)若边e与无序结点对(u,v)相对应,则称边e为无向边,记为e=(u,v),这时称u,v是边e的两个端点;2)若边e与有序结点对<u,v>相对应,则称边e为有向边(或弧),记为e=<u,v>,这时称u是边e的始点(或弧尾).v是边e的终点(或弧头),统称为e的端点;图的类型(续)3)在一个图中,关联结点v i和v j的边e,无论是有向的还是无向的,均称边e与结点v i 和v j相关联,而v i和v j称为邻接点,否则称为不邻接的;4)关联于同一个结点的两条边称为邻接边;5)图中关联同一个结点的边称为自回路(或环);图的类型(续)6)图中不与任何结点相邻接的结点称为孤立结点;7)仅由孤立结点组成的图称为零图;8)仅含一个结点的零图称为平凡图;9)含有n个结点、m条边的图称为(n,m)图;10)每条边都是无向边的图称为无向图;11)每条边都是有向边的图称为有向图;图的类型(续)12)有些边是无向边,而另一些是有向边的图称为混合图。
13)在有向图中,两个结点间(包括结点自身间)若有同始点和同终点的几条边,则这几条边称为平行边,在无向图中,两个结点间(包括结点自身间)若有几条边,则这几条边称为平行边,两结点v i,v j间相互平行的边的条数称为边(v i,v j)或<v i,v j>的重数;图的类型(续)14)含有平行边的图称为多重图。
第一篇集合论集合论是德国数学家康托(Contor)在1874年建立的,它是现代数学的基础,当今数学中的每个对象本质上都是集合。
有时我们说:“数学能嵌套在集合论中”其含义就是指数学的一些对象如数、函数、线、面等都可以用集合来定义。
换句话说,数学的各个分支在本质上都是研究这种或那种对象的集合。
例如:几何学是研究点、线、面的集合;数学分析是研究函数的集合;代数学是研究数的集合以及在此集合上有关运算的集合等。
因此,我们把集合论作为现代各种数学的基础是有道理的、合适的。
集合论也是计算机科学的重要工具。
集合论在程序设计、数据结构、形式语言、操作系统等计算机科学中,都有重要应用,成为计算机科学工作者必不可少的基础知识。
计算机科学领域中的大多数基本概念和理论,几乎均采用集合论的术语来描述和论证。
集合论主要有以下几个特点:第一、第一、它所研究的对象十分广泛。
例如数、图形或其它任何客体作为对象。
第二、第二、因为它研究的对象是如此广泛,为了便于研究,就必须寻找对象的共性。
而要做到这一点,就必须进行抽象。
第三、第三、在抽象化的基础上,可以用统一的方法来研究和处理集合论中的各种问题。
总之,集合论的主要特点是研究对象的广泛性,分析思考问题的抽象性和处理问题的统一性。
正是这些特点,使我们便于用它来描述和研究离散对象及其关系。
第一章集合及其运算基本要求1. 1.掌握集合、子集、全集、空集和幂集等概念。
熟悉常用的表示集合的方法以及用文氏图来表示集合的方法。
能够判定元素与集合、集合与集合之间的关系;熟练掌握两个集合相等关系和包含关系的定义和性质,能够利用定义证明两个集合相等。
2. 2.熟练掌握集合之间的各种运算以及集合运算的基本等式,能够利用它们来证明更复杂的集合等式。
3. 3.掌握余集与集合笛卡儿乘积的概念以及De Morgan公式。
4.掌握求解与有穷集合计数相关的实际问题。
1.1 必备知识和考试要点1.1.1基本定义集合是一个不能精确定义的数学概念。