圖論的習(xí)題

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

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

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

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