圖論的習題

1、,證明：設G為由n個結點組成的簡單有向圖，而且任何兩個結點之間有且只有一條有向邊相連，證明該圖中所有結點入度的平方和與所有結點出度的平方和一定相等。（西安交大，00年）,關于有向連通圖的可達性,設D是n(n>=2)階有向連通圖，則D的可達性距陣的所有元素之和至少為——（北京大學，00年）,,一個無向圖有4個結點，其中3個的度數(shù)為2，3，3，則第4個結點的度數(shù)不可能是————(北京理工,99年)A.0 B. 1

2、 C. 2 D. 4,握手定理,簡單無向圖有21條邊,3個4度結點,其余均為3度結點,則G有___個結點.(東北大學,02年),,一個簡單圖G=,若G不連通,則它的補圖一定連通.(南京理工,01年),,至少要刪除多少條邊,才能是Kn(n>2)不連通,且其中有一個連通分支恰有k個結點.(復旦,02年),,判斷:設G為無向圖,若G恰有n個結點,n-1條邊,則G必為一棵樹.下面圖中恰有兩棵不同夠的生成樹.(西安交

3、大,97年),,,,,,,,,,,,,證明:若簡單無向圖G中恰有兩個奇結點,則兩個結點一定可達.(國防科大,01年)并請判斷:若簡單無向圖G中恰有兩個奇結點,則G中任意兩個結點u和v之間必存在一條基本路徑.,同構的判斷,,,,,,,,,,,,,,,,,,,,,,,,,,關于歐拉,哈密爾頓圖,二部圖K2，3是（）(北京理工,02年)A.歐拉圖B. 哈密爾頓圖C.非平面圖D.平面圖,,下列命題中( )是正確的.1.歐拉圖的子圖

4、一定是歐拉圖2.哈密頓圖的子圖一定是哈密頓圖3.平面圖的子圖一定是平面圖4.樹的子圖一定是樹.(北京理工,00年),關于彼得森圖,證明:1.不是二部圖2.不是歐拉圖3.不是平面圖(大連理工,01年),平面圖的判定,問:K4，3與 K4，4是否為平面圖？為什么？（南京理工，01年）,,T=〈V，E〉是一個圖，證明：1.若T是一棵樹,則T是一個二部圖;2設(V1,V2)是T的結點的一個二分類,且|V1|> |V2