简单连通图G 满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路

来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/19 19:15:01
简单连通图G满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路简单连通图G满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路简单连通图G满足顶点数n>2k,k是最小度,求证

简单连通图G 满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路
简单连通图G 满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路

简单连通图G 满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路
用到这几个概念：
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. 证毕.

简单连通图G 满足顶点数n>2k,k是最小度,求证G中存在一条长至少为2k的路 证明n个顶点k条边的简单图G,若k>1/2(n-1)(n-2),则图G是连通的. 证明若G是每一个面至少由k(k≥3)条边围成的连通平面图则e≤[k(n-2)]/(k-2).这里e,n分别是图G的边数和顶点证明：若G是每一个面至少由k(k≥3)条边围成的连通平面图，则e≤[k(n-2)]/(k-2).这里e,n分别 有关平面图的问题设G为任意的连通平面图,则有n-m+r=( )；若G是简单连通平面图n>=3,则m<=( )；若G是简单连通平面图n>=3,且G是二部图,则m<=（ ）.其中n表示定点数,m表示边数,r表 已知n阶m条边的无向图G为k(k>=2)个连通分支的森林,证明m=n-k 设G是简单图,有n个顶点,最小度数a>[n/2]-1,证明G是连通的 证明!图论!证明：图G是连通的平面图,其点数为n,边数为e,则n-e+f=2 简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的 简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的 G 是有 n-1 条边的图（n 是 G 的顶点数）.证明：如果 G 中无圈,那么G 是一棵树.分可加. 设G是n(n>=2)阶欧拉图,证明G是2-边连通图 证明:若G=〈V,E〉是简单图,则m≤Cn2 ,其中m为图的边数,n为图的顶点数.我不太懂题目的意思, G是n阶简单无向图,如果图G中任意两点的度数之和大于等于n-1,证明图G是连通图 对于一个具有n各定点和e条边的连通图,其生成树中的顶点数和边数分别是什么数据结构的问题 证明：若n阶简单无向图G的任意两个结点的度数之和大于等于n-1,则G是连通的.我也搜到“假设G有两个连通分支G1和G2,那么取v1是G1中度数最小的顶点,v2是G2中度数最小的顶点,则d(v1)+d(v2)≤n-2（ 设n阶无向简单图G有m条边,已知m>=1/2(n-1)(n-2)+1,证明G必连通 离散数学中环路的概念是什么G是n阶m条边的无向连通图，G中初级或简单回路数m-n+1 证明简单的不等式:x^ky^(2n-k)+x^(2n-k)y^k[x^k]*[y^(2n-k)]+[x^(2n-k)]*[y^k]