圖論習題考研習題與經典習題2004-5圖論習題考研習題與經典習題1一、握手定理的應用二、平面圖、歐拉公式的應用三、圖的基本概念與應用四、歐拉圖和哈密頓圖五、圖的著色一、握手定理的應用2一、握手定理的應用1.已知具有n個度數都為3的結點的簡單圖G有e條邊，（1）若e=3n-6，證明G在同構意義下唯一，并求e，n。（2）若n=6，證明G在同構意義下不唯一。提示：握手定理（北師大2000考研）一、握手定理的應用1.已知具有n個度數都為3的結點的簡單3解：（1）由握手定理，3n=2e;因為e=3n-6，所以n=4，e=6。這樣的圖是完全圖K4，所以在同構的意義下唯一。（2）由握手定理，3*6=2e；e=9。在同構的意義下不唯一。解：42.無向圖G有21條邊，12個結點度數為3，其余結點度數為2，求G的頂點數。提示：握手定理（北大2001考研）2.無向圖G有21條邊，12個結點度數為3，其余結點度數5解：解：63.已知n個結點的簡單圖G有e條邊，各結點度數為3，2n=e+3。試畫出滿足條件的所有不同構的G。提示：握手定理（西南交大2000考研/北京大學1990考研）參考1(2)3.已知n個結點的簡單圖G有e條邊，各結點度數為3，2n7解：由握手定理，e=(3n/2)；由已知，e=2n-2；所以n=6，e=9。在同構意義下G不是唯一的。解：由握手定理，e=(3n/2)；由已知，e=2n-2；所以84.設樹T有17條邊，12片樹葉，4個4度內結點，1個3度內結點，求T的樹根的度數。（提示：握手定理。北大1997考研）4.設樹T有17條邊，12片樹葉，4個4度內結點，1個9解：結點數為17+1=18由握手定理，12*1+4*4+1*3+1*l=34,l=3.解：結點數為17+1=18105.設無向樹T有3個3度，2個2度結點，其余結點都是樹葉，問T有幾片樹葉？握手定理5.設無向樹T有3個3度，2個2度結點，其余結點都是樹葉116.證明：在任何兩個或兩個以上人的組內，存在兩個人在組內有相同個數的朋友。/*等價于：至少有兩個頂點的簡單圖有兩個相同度數的頂點/*中國科學院自動化所1998考研6.證明：在任何兩個或兩個以上人的組內，存在兩個人在組內12二、平面圖、歐拉公式的應用1，關于平面圖的不等式的證明歐拉公式及其推論的運用2，非平面圖的判定應用庫拉托斯基定理二、平面圖、歐拉公式的應用1，關于平面圖的不等式的證明131.設G是n個結點的連通簡單平面圖，若n3，則G中必有一個結點度數不超過5。提示：涉及度數，握手定理；連通平面圖，歐拉公式；簡單平面圖，若n3，歐拉公式的推論（西南交大1999考研）1.設G是n個結點的連通簡單平面圖，若n3，則G中必有14證明：握手定理：dev(vi)=2e;反證：設每個結點的度數超過5，即dev(vi)6，則2e=dev(vi)6n,所以e3n.由歐拉公式的推論，e3n-6。所以矛盾。證明：152.證明彼得森圖是非平面圖。提示：要證明一個圖不是平面圖，首先考慮應用庫拉托斯基定理。即在要判別的圖中，找出一個K5或K3,3的剖分。（西安交通大學1997考研）2.證明彼得森圖是非平面圖。163.證明小于30條邊的簡單平面圖G中，至少有一個度數小于等于4的結點。3.證明小于30條邊的簡單平面圖G中，至少有一個度數小于17證明：不妨設G是連通圖。因為e3n-6，假設所有頂點度數大于等于5；由握手定理，dev(vi)=2e;所以2e5n，則有n2e/5。

代入e3n-6，則e6e/5-6,從而e30。所以矛盾。證明：不妨設G是連通圖。184.證明在簡單平面圖G中，f和n分別表示該圖的面數和結點數，(1)如果n3，則f2n-4。(2)G中結點最小的度(G)=4，則G中至少有6個結點的度數小于等于5。（西安交通大學1996考研）4.證明在簡單平面圖G中，f和n分別表示該圖的面數和19（1）證明：假設圖中的邊數為e。由于簡單圖的每個面至少由3條邊圍成，因此3f2e。由歐拉公式n-e+f=2，得e=n+f-2；代入3f2e得到3f2(n+f-2)，得f2n-4。（1）證明：假設圖中的邊數為e。由于簡單圖的每個面至少由3條20（2）證明：（反證法）假設G中至多有5個結點的度數小于等于5。因為(G)=4，則d(v)54+6(n-5)。因為d(v)=2e，則e3n-5。由(1)，e3n-6。（2）證明：（反證法）215.設G是由n個結點，e條邊，(2)個連通分支的平面圖，G的每個面至少由k（k3）條邊圍成，則

5.設G是由n個結點，e條邊，(2)個連通分支的平22證明：設G的面數為f，各面的度數之和為T，T=2e。因為G的每個面至少由k條邊圍成，所以k*fT=2e。由歐拉公式的推廣，f=+1+e-n,k*(+1+e-n)2e.所以命題成立。證明：設G的面數為f，各面的度數之和為T，T=2e。因為G的23圖論習題課件24三、圖的基本概念與應用1.補圖2.連通性三、圖的基本概念與應用1.補圖25補圖1.證明無向圖G是不連通的，則它的補圖是連通的。提示：分而治之（西南交大1999考研）證明連通的兩種方法：直接證明，反證法補圖1.證明無向圖G是不連通的，則它的補圖是連通的。26證明：設G=(V,E),根據連通分支將V劃分為{V1,V2,……,Vn}，并設Vi={u1,u2,…,ur}，Vj={v1,v2,…,vs}，ij，1i,jn，Ek表示完全圖的邊集。任取V中兩個結點，分兩種情況討論：（1）設uiVi,vjVj.(ui,vj)E,則(ui,vj)Ek–E.所以ui,vj是連通的。即在不同連通分支中的兩個結點在補圖中是連通的。（2）設ui,ujVi,vjVj.由(1)，(ui,vj)Ek–E,(uj,vj)Ek–E.所以ui,uj通過vj連通。即在相同連通分支中的兩個結點在補圖中是連通的。所以，命題成立。證明：設G=(V,E),根據連通分支將V劃分為{V1,272.一個圖如果同構于它的補圖,則該圖稱為自補圖.1)試給出一個5個結點的自補圖;2)證明:一個圖是自補圖,其對應的完全圖的邊數必是偶數;3)是否有3個結點或者6個結點的自補圖.2.一個圖如果同構于它的補圖,則該圖稱為自補圖.282)證明：如果一個圖是自補圖，設該圖的邊數為e，則該圖的自補圖的邊數也為e，所以對應的完全圖的邊數是2e，為偶數。2)證明：如果一個圖是自補圖，設該圖的邊數為e，則該圖的自補293)解：3個結點或者6個結點的完全圖的邊數分別為3和15，是奇數；所以不存在3個結點或者6個結點的自補圖。3)解：3個結點或者6個結點的完全圖的邊數分別為3和15，是30連通性證明連通的兩種方法:直接證明/反證法.證明連通的直接證明方法：任取圖中兩點，尋找這兩點間必定存在路。證明連通的反證法:首先假設圖不連通，則它具有多個連通分支，然后根據題目條件推出矛盾。推矛盾的過程，通常是將具有多個連通分支的圖的邊數放到最大的過程（放縮法），即使每個連通分支都是完全圖，然后推出邊仍然不滿足條件。連通性證明連通的兩種方法:直接證明/反證法.311.n個結點的簡單圖G，n>2且n奇數，G和G補圖中度數為奇數的結點個數是否相等？請證明或給出反例。（西南交大2001考研）1.n個結點的簡單圖G，n>2且n奇數，G和G補圖中度數32解：一定相等。因為n>2且n奇數，則對于奇數個結點的完全圖，每個結點的度數必為偶數。若G中度數為奇數的結點個數是m，則G的補圖中m個結點的度數為（偶數-奇數）=奇數。G中度數為偶數的結點，在G的補圖中這些結點的度數仍為（偶數-偶數）=偶數。所以命題成立。解：一定相等。332.設無向圖G有n個結點，n2。證明：1）當(G)n/2時，G是連通圖；2）當(G)(1/2)(n+k-1)時，G是k-連通圖，其中1kn-1。(北京大學1994年考研)2.設無向圖G有n個結點，n2。證明：343.若G為簡單圖，且，則G是連通的。其中m和n分別為該圖的邊數和頂點數。/*中國科學院自動化所1998考研3.若G為簡單圖，且，則G是連通的。其35證明方法：1）反證法（簡捷）2）數學歸納法：對頂點數進行數學歸納證明方法：36反證法：證明：假設G不是連通的，則G至少存在兩個連通分支。設G有兩個連通分支C1和C2，則G的最大可能的邊數m=x(x-1)/2+(n-x)(n-x-1)/2，其中1xn-1；所以m的最大所以導致矛盾，則G是連通的。反證法：374.設G=(V,E)是連通簡單圖，但不是完全圖，則存在3個結點u、v和w,使(u,v),(v,w)E，但(u,w)E。/*中國科學院計算所1993考研4.設G=(V,E)是連通簡單圖，但不是完全圖，則存在338證明方法：1）反證法2）數學歸納法證明方法：395.設G為非平凡有向圖，V為G的結點集合，若對V的任一非空子集S，G中起始結點在S中，終止結點在V-S中的有向邊至少有k條，則稱G是k邊連通的。證明：非平凡有向圖是強連通的充要條件為它是一邊連通的。/*中國科學院計算所1999考研5.設G為非平凡有向圖，V為G的結點集合，若對V的任一非空40證明：/*必要性證明*/因為設G為強連通的，假設從S到V-S沒有有向邊，則S中的任一頂點u到V-S中的任一頂點v均沒有有向道路，從而與G為強連通的相矛盾。所以從S到V-S至少有一條有向邊，即G為一邊連通的。證明：41/*充分性證明*/設G為一邊連通的，對任意的u,vV,則{u}到V(G-u)至少有一條邊，設為(u,u1)，而{u,u1}到V-{u,u1}至少有一條有向邊(u,u2)或(u1,u2)。無論哪種情況都有從u到u2的有向道路，因為G中結點數有限，所以通過如上遞歸地求解，一定有從u到v的有向道路。所以G為強連通的。/*充分性證明*/426.設簡單平面圖G中頂點數n=7，邊數e=15，證明G是連通的。提示：反證6.設簡單平面圖G中頂點數n=7，邊數e=15，證明G是437.簡單圖G由圖H和兩個孤立點組成，圖H不含孤立點，?為平面圖，證明H為連通圖。（中國科學院軟件所1994考研）7.簡單圖G由圖H和兩個孤立點組成，圖H不含孤立點，?為平面448.若G為簡單圖,且,則G是連通的.其中m和n分別為該圖的邊數和頂點數.給出一個有n個結點而不連通的簡單圖,其邊數恰好為./*華中科技大學2000考研8.若G為簡單圖,且,則G是連通的.459.能否畫一個簡單無向連通圖，使各結點的度數與下面給出的序列一致？如可能，則畫出符合條件的圖，所畫圖是二分圖？如不能，則說明原因。（1）1，2，3，2，1，1（2）1，1，2，3，2，2（3）1，2，3，4，5，5（4）2，2，2，3，3，4（西南交大1995考研）9.能否畫一個簡單無向連通圖，使各結點的度數與下面給出的46(1)V1={a,c,e},V2={b,d,f}.(2)不可能畫出圖。(頂點度數之和為偶數)(3)不可能畫出圖和二分圖。由于有兩個結點的度數為5，則該兩個結點的度數必與其余5個結點有邊相連（因為是簡單圖），所以其余4個結點度數至少為2，但有一個結點的度數為1。(4)(1,6,4,5,6,1)，回路長度為奇數，所以不是二分圖。(1)V1={a,c,e},V2={b,d,f4710設圖G有n個結點，r個連通分支，則圖G的路徑矩陣的秩為n-r。10設圖G有n個結點，r個連通分支，則圖G的路徑矩陣的48證明：設圖G的r個連通分支為G1,G2,…,Gr。得分塊路徑矩陣如下：證明：設圖G的r個連通分支為G1,G2,…,Gr。得分49因為Gi是連通圖，Gi的秩是連通分支Gi的結點個數-1，所以rank(G)=rank(Gi)=n-r。因為Gi是連通圖，Gi的秩是連通分支Gi的結點個數-1，所以50本題背景：1線性相關/線性無關

如果對m個向量1,2,….,mFm，有m個不全為零的數k1,k2,….,kmF，使k11+k22+…….+kmm=0n成立，則稱1,2,….,m線性相關；否則，稱1,2,….,m線性無關。

本題背景：512向量組的秩如果向量組1,2,….,s中存在r個線性無關的向量，且其中任一個向量可由這r個線性無關的向量線性表示，則數r稱為向量組的秩，記作{1,2,….,s}=r。

2向量組的秩529.若圖G=(V,E)是連通圖，且eE，證明：(1)e屬于每一棵生成樹的充要條件是{e}為G的割集；(2)e不屬于G的任何一棵生成樹的充要條件是e為G中的環(huán)。提示：反證9.若圖G=(V,E)是連通圖，且eE，證明：53分析：(1)e屬于每一棵生成樹,要證G刪去e后必不連通，否則矛盾。(2)分析：54證明：（1）：e屬于每一棵生成樹,若{e}不是G的割集，G-e連通，則G-e中必存在生成樹T，因為T也是G的生成樹，但T不包含e，導致矛盾。：設{e}不是G的割集，若有G的生成樹T，則T+e包含回路。則刪去e后連通，則與{e}是G的割集的假設矛盾。證明：（1）55圖論習題課件5615.具有(2)棵樹的森林，恰巧加多少新邊能使森林變樹？15.具有(2)棵樹的森林，恰巧加多少新邊能使森林57n個結點，(2)棵樹，n-條邊n個結點的樹，n-1條邊（n-1）-（n-）=-1n個結點，(2)棵樹，n-條邊5816.已知n個結點（n2）的簡單無向圖G具有n-1條邊，G是樹嗎？提示：定義7.1定理7.116.已知n個結點（n2）的簡單無向圖G具有n-1條邊59四、歐拉圖和哈密頓圖1證明：在無有向回路的競賽圖G=(V,E)中，對任意的u,vV,d+(u)d+(v)。/*中國科學院軟件所*//*反證*/四、歐拉圖和哈密頓圖1證明：在無有向回路的競賽圖G=(V60證明：假設G中存在兩個頂點u,v，d+(u)=d+(v)。因為G是競賽圖，所以設(u,v)E,在G中存在頂點w，使得(v,w)E,(u,w)E。所以，根據競賽圖的性質，(w,u)E。則構成有向回路u,v,w,u。導致矛盾。所以命題成立。證明：假設G中存在兩個頂點u,v，d+(u)=d+(v61證明歐拉圖：按照充要條件證明歐拉圖：按照充要條件62證明哈密頓圖：抽象圖，充分條件或必要條件；具體圖，比較困難證明哈密頓圖：抽象圖，充分條件或必要條件；具體圖，比較困難63圖論習題課件64五、圖的著色四色猜想和五色定理相對平面圖而言上海交通大學4次考到五色定理的證明頂點著色五、圖的著色四色猜想和五色定理相對平面圖而言651圖G(V,E)稱為k色臨界圖是指，對任意vV，均有(G-v)<(G)=k。證明：在k色臨界圖中，(G)k-1，其中(G)=min{d(v)|vV}。中國科學院軟件所19951圖G(V,E)稱為k色臨界圖是指，對任意vV，均有66證明：/*反證法*/若在圖G中存在v0V，d(v0)k-2。因為G是k色臨界圖，所以對G-v0可作k-1正常著色。又因為在G中與v0鄰接的結點個數k-2，所以在G-v0中對這些鄰接點至多用k-2種顏色，即至少還有k-1種顏色中的一種未使用。在G中用這種顏色對v0著色，其他結點著色與G-v0相同，所以得到G的k-1正常著色，與(G)=k矛盾。證明：/*反證法*/672對于圖G，(G)=k，則G中至少有k(k-1)/2條邊。中國科學院計算所19982對于圖G，(G)=k，則G中至少有k(k-1)/2條68圖論習題課件69圖論習題課件70圖論習題考研習題與經典習題2004-5圖論習題考研習題與經典習題71一、握手定理的應用二、平面圖、歐拉公式的應用三、圖的基本概念與應用四、歐拉圖和哈密頓圖五、圖的著色一、握手定理的應用72一、握手定理的應用1.已知具有n個度數都為3的結點的簡單圖G有e條邊，（1）若e=3n-6，證明G在同構意義下唯一，并求e，n。（2）若n=6，證明G在同構意義下不唯一。提示：握手定理（北師大2000考研）一、握手定理的應用1.已知具有n個度數都為3的結點的簡單73解：（1）由握手定理，3n=2e;因為e=3n-6，所以n=4，e=6。這樣的圖是完全圖K4，所以在同構的意義下唯一。（2）由握手定理，3*6=2e；e=9。在同構的意義下不唯一。解：742.無向圖G有21條邊，12個結點度數為3，其余結點度數為2，求G的頂點數。提示：握手定理（北大2001考研）2.無向圖G有21條邊，12個結點度數為3，其余結點度數75解：解：763.已知n個結點的簡單圖G有e條邊，各結點度數為3，2n=e+3。試畫出滿足條件的所有不同構的G。提示：握手定理（西南交大2000考研/北京大學1990考研）參考1(2)3.已知n個結點的簡單圖G有e條邊，各結點度數為3，2n77解：由握手定理，e=(3n/2)；由已知，e=2n-2；所以n=6，e=9。在同構意義下G不是唯一的。解：由握手定理，e=(3n/2)；由已知，e=2n-2；所以784.設樹T有17條邊，12片樹葉，4個4度內結點，1個3度內結點，求T的樹根的度數。（提示：握手定理。北大1997考研）4.設樹T有17條邊，12片樹葉，4個4度內結點，1個79解：結點數為17+1=18由握手定理，12*1+4*4+1*3+1*l=34,l=3.解：結點數為17+1=18805.設無向樹T有3個3度，2個2度結點，其余結點都是樹葉，問T有幾片樹葉？握手定理5.設無向樹T有3個3度，2個2度結點，其余結點都是樹葉816.證明：在任何兩個或兩個以上人的組內，存在兩個人在組內有相同個數的朋友。/*等價于：至少有兩個頂點的簡單圖有兩個相同度數的頂點/*中國科學院自動化所1998考研6.證明：在任何兩個或兩個以上人的組內，存在兩個人在組內82二、平面圖、歐拉公式的應用1，關于平面圖的不等式的證明歐拉公式及其推論的運用2，非平面圖的判定應用庫拉托斯基定理二、平面圖、歐拉公式的應用1，關于平面圖的不等式的證明831.設G是n個結點的連通簡單平面圖，若n3，則G中必有一個結點度數不超過5。提示：涉及度數，握手定理；連通平面圖，歐拉公式；簡單平面圖，若n3，歐拉公式的推論（西南交大1999考研）1.設G是n個結點的連通簡單平面圖，若n3，則G中必有84證明：握手定理：dev(vi)=2e;反證：設每個結點的度數超過5，即dev(vi)6，則2e=dev(vi)6n,所以e3n.由歐拉公式的推論，e3n-6。所以矛盾。證明：852.證明彼得森圖是非平面圖。提示：要證明一個圖不是平面圖，首先考慮應用庫拉托斯基定理。即在要判別的圖中，找出一個K5或K3,3的剖分。（西安交通大學1997考研）2.證明彼得森圖是非平面圖。863.證明小于30條邊的簡單平面圖G中，至少有一個度數小于等于4的結點。3.證明小于30條邊的簡單平面圖G中，至少有一個度數小于87證明：不妨設G是連通圖。因為e3n-6，假設所有頂點度數大于等于5；由握手定理，dev(vi)=2e;所以2e5n，則有n2e/5。

代入e3n-6，則e6e/5-6,從而e30。所以矛盾。證明：不妨設G是連通圖。884.證明在簡單平面圖G中，f和n分別表示該圖的面數和結點數，(1)如果n3，則f2n-4。(2)G中結點最小的度(G)=4，則G中至少有6個結點的度數小于等于5。（西安交通大學1996考研）4.證明在簡單平面圖G中，f和n分別表示該圖的面數和89（1）證明：假設圖中的邊數為e。由于簡單圖的每個面至少由3條邊圍成，因此3f2e。由歐拉公式n-e+f=2，得e=n+f-2；代入3f2e得到3f2(n+f-2)，得f2n-4。（1）證明：假設圖中的邊數為e。由于簡單圖的每個面至少由3條90（2）證明：（反證法）假設G中至多有5個結點的度數小于等于5。因為(G)=4，則d(v)54+6(n-5)。因為d(v)=2e，則e3n-5。由(1)，e3n-6。（2）證明：（反證法）915.設G是由n個結點，e條邊，(2)個連通分支的平面圖，G的每個面至少由k（k3）條邊圍成，則

5.設G是由n個結點，e條邊，(2)個連通分支的平92證明：設G的面數為f，各面的度數之和為T，T=2e。因為G的每個面至少由k條邊圍成，所以k*fT=2e。由歐拉公式的推廣，f=+1+e-n,k*(+1+e-n)2e.所以命題成立。證明：設G的面數為f，各面的度數之和為T，T=2e。因為G的93圖論習題課件94三、圖的基本概念與應用1.補圖2.連通性三、圖的基本概念與應用1.補圖95補圖1.證明無向圖G是不連通的，則它的補圖是連通的。提示：分而治之（西南交大1999考研）證明連通的兩種方法：直接證明，反證法補圖1.證明無向圖G是不連通的，則它的補圖是連通的。96證明：設G=(V,E),根據連通分支將V劃分為{V1,V2,……,Vn}，并設Vi={u1,u2,…,ur}，Vj={v1,v2,…,vs}，ij，1i,jn，Ek表示完全圖的邊集。任取V中兩個結點，分兩種情況討論：（1）設uiVi,vjVj.(ui,vj)E,則(ui,vj)Ek–E.所以ui,vj是連通的。即在不同連通分支中的兩個結點在補圖中是連通的。（2）設ui,ujVi,vjVj.由(1)，(ui,vj)Ek–E,(uj,vj)Ek–E.所以ui,uj通過vj連通。即在相同連通分支中的兩個結點在補圖中是連通的。所以，命題成立。證明：設G=(V,E),根據連通分支將V劃分為{V1,972.一個圖如果同構于它的補圖,則該圖稱為自補圖.1)試給出一個5個結點的自補圖;2)證明:一個圖是自補圖,其對應的完全圖的邊數必是偶數;3)是否有3個結點或者6個結點的自補圖.2.一個圖如果同構于它的補圖,則該圖稱為自補圖.982)證明：如果一個圖是自補圖，設該圖的邊數為e，則該圖的自補圖的邊數也為e，所以對應的完全圖的邊數是2e，為偶數。2)證明：如果一個圖是自補圖，設該圖的邊數為e，則該圖的自補993)解：3個結點或者6個結點的完全圖的邊數分別為3和15，是奇數；所以不存在3個結點或者6個結點的自補圖。3)解：3個結點或者6個結點的完全圖的邊數分別為3和15，是100連通性證明連通的兩種方法:直接證明/反證法.證明連通的直接證明方法：任取圖中兩點，尋找這兩點間必定存在路。證明連通的反證法:首先假設圖不連通，則它具有多個連通分支，然后根據題目條件推出矛盾。推矛盾的過程，通常是將具有多個連通分支的圖的邊數放到最大的過程（放縮法），即使每個連通分支都是完全圖，然后推出邊仍然不滿足條件。連通性證明連通的兩種方法:直接證明/反證法.1011.n個結點的簡單圖G，n>2且n奇數，G和G補圖中度數為奇數的結點個數是否相等？請證明或給出反例。（西南交大2001考研）1.n個結點的簡單圖G，n>2且n奇數，G和G補圖中度數102解：一定相等。因為n>2且n奇數，則對于奇數個結點的完全圖，每個結點的度數必為偶數。若G中度數為奇數的結點個數是m，則G的補圖中m個結點的度數為（偶數-奇數）=奇數。G中度數為偶數的結點，在G的補圖中這些結點的度數仍為（偶數-偶數）=偶數。所以命題成立。解：一定相等。1032.設無向圖G有n個結點，n2。證明：1）當(G)n/2時，G是連通圖；2）當(G)(1/2)(n+k-1)時，G是k-連通圖，其中1kn-1。(北京大學1994年考研)2.設無向圖G有n個結點，n2。證明：1043.若G為簡單圖，且，則G是連通的。其中m和n分別為該圖的邊數和頂點數。/*中國科學院自動化所1998考研3.若G為簡單圖，且，則G是連通的。其105證明方法：1）反證法（簡捷）2）數學歸納法：對頂點數進行數學歸納證明方法：106反證法：證明：假設G不是連通的，則G至少存在兩個連通分支。設G有兩個連通分支C1和C2，則G的最大可能的邊數m=x(x-1)/2+(n-x)(n-x-1)/2，其中1xn-1；所以m的最大所以導致矛盾，則G是連通的。反證法：1074.設G=(V,E)是連通簡單圖，但不是完全圖，則存在3個結點u、v和w,使(u,v),(v,w)E，但(u,w)E。/*中國科學院計算所1993考研4.設G=(V,E)是連通簡單圖，但不是完全圖，則存在3108證明方法：1）反證法2）數學歸納法證明方法：1095.設G為非平凡有向圖，V為G的結點集合，若對V的任一非空子集S，G中起始結點在S中，終止結點在V-S中的有向邊至少有k條，則稱G是k邊連通的。證明：非平凡有向圖是強連通的充要條件為它是一邊連通的。/*中國科學院計算所1999考研5.設G為非平凡有向圖，V為G的結點集合，若對V的任一非空110證明：/*必要性證明*/因為設G為強連通的，假設從S到V-S沒有有向邊，則S中的任一頂點u到V-S中的任一頂點v均沒有有向道路，從而與G為強連通的相矛盾。所以從S到V-S至少有一條有向邊，即G為一邊連通的。證明：111/*充分性證明*/設G為一邊連通的，對任意的u,vV,則{u}到V(G-u)至少有一條邊，設為(u,u1)，而{u,u1}到V-{u,u1}至少有一條有向邊(u,u2)或(u1,u2)。無論哪種情況都有從u到u2的有向道路，因為G中結點數有限，所以通過如上遞歸地求解，一定有從u到v的有向道路。所以G為強連通的。/*充分性證明*/1126.設簡單平面圖G中頂點數n=7，邊數e=15，證明G是連通的。提示：反證6.設簡單平面圖G中頂點數n=7，邊數e=15，證明G是1137.簡單圖G由圖H和兩個孤立點組成，圖H不含孤立點，?為平面圖，證明H為連通圖。（中國科學院軟件所1994考研）7.簡單圖G由圖H和兩個孤立點組成，圖H不含孤立點，?為平面1148.若G為簡單圖,且,則G是連通的.其中m和n分別為該圖的邊數和頂點數.給出一個有n個結點而不連通的簡單圖,其邊數恰好為./*華中科技大學2000考研8.若G為簡單圖,且,則G是連通的.1159.能否畫一個簡單無向連通圖，使各結點的度數與下面給出的序列一致？如可能，則畫出符合條件的圖，所畫圖是二分圖？如不能，則說明原因。（1）1，2，3，2，1，1（2）1，1，2，3，2，2（3）1，2，3，4，5，5（4）2，2，2，3，3，4（西南交大1995考研）9.能否畫一個簡單無向連通圖，使各結點的度數與下面給出的116(1)V1={a,c,e},V2={b,d,f}.(2)不可能畫出圖。(頂點度數之和為偶數)(3)不可能畫出圖和二分圖。由于有兩個結點的度數為5，則該兩個結點的度數必與其余5個結點有邊相連（因為是簡單圖），所以其余4個結點度數至少為2，但有一個結點的度數為1。(4)(1,6,4,5,6,1)，回路長度為奇數，所以不是二分圖。(1)V1={a,c,e},V2={b,d,f11710設圖G有n個結點，r個連通分支，則圖G的路徑矩陣的秩為n-r。10設圖G有n個結點，r個連通分支，則圖G的路徑矩陣的118證明：設圖G的r個連通分支為G1,G2,…,Gr。得分塊路徑矩陣如下：證明：設圖G的r個連通分支為G1,G2,…,Gr。得分119因為Gi是連通圖，Gi的秩是連通分支Gi的結點個數-1，所以rank(G)=rank(Gi)=n-r。因為Gi是連通圖，Gi的秩是連通分支Gi的結點個數-1，所以120本題背景：1線性相關/線性無關

如果對m個向量1,2,….,mFm，有m個不全為零的數k1,k2,….,kmF，使k11+k22+…….+kmm=0n成立，則稱1,2,….,m線性相關；否則，稱1,2,….,m線性無關。

本題背景：1212向量組的秩如果向量組1,2,….,s中存在r個線性無關的向量，且其中任一個向量可由這r個線性無關的向量線性表示，則數r稱為向量組的秩，記作{1,2,….,s}=r。

2