图论题目 简单连通图G 满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路
作者&投稿:攸别 (若有异议请与网页底部的电邮联系)
反证法:
假设图G不连通
那么必然可以在G中取一对节点u和v且这两个节点不连通
设u和v所在连通块的节点数量分别为n1和n2
显然n1+n2<=n
u的度数>[n/2]-1,那么u所在的连通块就至少包含u和所有与u相连的节点,那么n1>[n/2]-1+1=[n/2],即n1>=[n/2]+1
同理n2>=[n/2]+1
两个连通块的节点总数n1+n2>=2*[n/2]+2>2*[n/2]+1
n为奇数时,[n/2]=(n-1)/2,2*[n/2]+1=n,那么n1+n2>n
n为偶数时,[n/2]=n/2,2*[n/2]+1=n+1,那么n1+n2>n
无论n为奇数还是偶数,都有n1+n2>n,与n1+n2<=n矛盾
因此图G是个连通图
这是由一道数学竞赛题改编过来的。
第一种情况:存在三人相互不认识,很显然结论是成立的。
第二种情况:任意三人中至少有两人认识。(这种情况就是原题)
抽象成点,全部连接,若认识边染成红色,否则染成蓝色。
由假设,这个图中没有蓝色三角形。
分两种情况。1,若某个顶点发出的蓝边至少有四条(以四条为例),那么分析就可知道存在存在红色的完全图K4;
2,若任一顶点发出的蓝线至多三条,那么存在某个顶点A的发出了(至少)六条边,然后在考察这六个顶点,在运用拉姆塞定理(二染色的K6中存在同色三角形),知道这六个顶点中存在红色的三角形。这三点再加A就是完全认识的人了。
以上就是问题解答的核心部分,细枝末节你就自己添加吧。
1、设F是图G的一个子图,对于F中的任意顶点u和v,只要uv是G中的边,则uv一定是F中的边,此时称F为G的一个诱导子图。
2、若S是图G的一个非空顶点集合,则由S诱导的G的子图就是以S为顶点集的诱导子图。
3、除第一个和最后一个顶点外,没有顶点重复的回路(circuit)称为圈(cycle)。k圈是一个长度为k的圈,记作Ck其中k是下标(k≥3)。
4、一个含图G的每个顶点的圈称为是G的一个Hamilton圈。一个含有Hamilton圈的图称为是一个Hamilton图(或称此图是Hamilton的)。
要用到下述定理:
Th.设u和v是一个n阶图G的两个不邻接的顶点,并且degu+degv≥n.则G+uv是Hamilton的当且仅当G是Hamilton的.
此定理的证明见Gary.Chartrand的书《图论导引》
下面是对本题的证明。
证明:设P:x0,x1,...,xm是图G中最长的一条路(长为m),记由{x0,...,xm}诱导的G的子图为H。由P是G中最长路知,与x0以及xm相邻的点都在路P上(否则与P是G中最长路矛盾),因此由诱导子图定义知,在H中x0(或xm)的度数与在G中x0(或xm)的度数是一样的,不妨就将其简单记作deg(x0)及deg(xm). 我们采用反证法,假设m<2k.显然n>2k≥2,首先m>0(否则G不连通);若m=1,由G的顶点数n>2知V(G)-{x0,x1}非空,由G连通知,存在一点y∈V(G)-{x0,x1}以及xi∈{x0,x1}使得yxi∈E(G),则y,x0,x1组成长为2的路,与x0x1是G中最长路矛盾,因此m>1。从而x0与xm不相邻。又deg(x0)+deg(xm)≥2k≥m+1(由假设m<2k知),而且H+x0xm包含有圈C(m+1)(m+1是下标):x0,x1,...,xm,x0.故H+x0xm是Hamilton的,由上面的定理知,H是Hamilton的。故H包含一个圈C(m+1)。由于n>2k≥m+1,因此V(G)-{x0,...,xm}非空,由G连通知,存在一点y∈V(G)-{x0,...,xm}以及xi∈{x1,...x(m-1)}使得yxi∈E(G).因此G中包含这样一个图形:一个圈C(m+1)以及圈外一点y与C(m+1)中的点xi相邻接,这样就找到G中一条长为m+1的路(在纸上画画图便知道了),与P:x0,...,xm是G中最长路矛盾。故m≥2k. 证毕。
揣武薯蓣:[答案] 用到这几个概念: 1、设F是图G的一个子图,对于F中的任意顶点u和v,只要uv是G中的边,则uv一定是F中的边,此时称F... 此定理的证明见Gary.Chartrand的书《图论导引》 下面是对本题的证明. 证明:设P:x0,x1,...,xm是图G中最长的一条路(长为m...
平陆县19692376161: 设无向连通图G有n个顶点,证明G至少有(n - 1)条边. - ?
揣武薯蓣: 设连通图G有(n+1)个顶点,若每个顶点连出至少两条边,那么此时至少有n+1条边(任意图上所有顶点度数和等于边数的两倍),结论已经成立.否则,那么至少有一个顶点只连出一条边. 不妨设为A,由于去掉这条边AB后不影响其他点的...
平陆县19692376161: 求一条图论基础题?
揣武薯蓣: 因为p(G)=顶点数-连通分支数,而在连通图中,e=n-1(即连通分支数=顶点数-1)所以,代进去算得 p(G) = 1
平陆县19692376161: 问一道图论题: - ?
揣武薯蓣: 我对图论也不是很熟悉,我试一下吧.提供给你参考. 证明:首先,根据条件得到:边数为:(4*8+6*6+8)/2=38 假设G是平面图 根据欧拉定理知道,面数等于:38+2-15=25 根据假设,面的总长度是:38*2=76 所以,G的面有24个长度为3,1个长...
平陆县19692376161: 图论:设图有10个4度顶点,8个5度顶点,其余为7度顶点,求7度顶点的最大数量,使得G保持可平面性. - ?
揣武薯蓣: 由平面图的点线面公式(Euler 公式):(顶点数)n+(面数)f-(边数)m=2,d(v1)+d(v2)+d(vn)=2m,及2m≥3f,可得:2=n+f-m ≤n+2/3m-m =n-1/3m=n-1/3[40+7/2(n-18)] 化简得:n≤36,所以7度顶点的最大数量是18.
平陆县19692376161: 设G是无向简单图,有6个顶点,7条边,证明G的连通分支个数不超过2 - ?
揣武薯蓣: 用反证法证明: 假设有3个连通分支 那么只能以下三种情况: 1. 两个孤立结点,和4个结点7条边 显然这不是简单图 2. 一个孤立结点,和2结点和3结点的连通分支 2结点的连通分支最多1条边 3结点的连通分支最多3条边 显然不满足条件 3. 3个2结点图,最多只能有3条边 综上,G的连通分支个数不超过2
平陆县19692376161: 图论:证明若G为简单连通图,且G中任意一对不相邻顶点u和v满足:d(u)+d(v)>=n - 1,则G有Hanmilton路. - ?
揣武薯蓣: http://web.nuist.edu.cn/courses/lssx/longtime/part4/chapter15/15_02_03_01.htm 记得采纳啊
平陆县19692376161: 关于离散数学中图论的一个问题题目:具有6个顶点,12条边的连通简单平面图中,每个面都是由()条边围成?? 急需解决... - ?
揣武薯蓣:[答案] 每个面都是三角形,所以都是三条边组成
平陆县19692376161: 图论问题无向图G中恰好只有2个度数为奇数的顶点证明:这两个顶点间必定存在一条路 - ?
揣武薯蓣:[答案] 若不然,则这两个顶点将分别属于两个简单图,也即G中包含两个简单图,每个简单图都只有一个奇顶点,这显然是不可能的.