應(yīng)用離散數(shù)學(xué)圖論圖的基本概念題庫試卷習(xí)題及答案

應(yīng)用離散數(shù)學(xué)圖論第5章:圖論§5.1圖地基本概念習(xí)題5.1證明,若是圖,則有≤≤。解因為,是圖中頂點地最小度數(shù),是圖中頂點地最大度數(shù),根據(jù)握手定理,是圖中所有頂點地度數(shù)之與,從而是圖中頂點地平均度數(shù)。所以有設(shè)9階圖中,每個頂點地度數(shù)不是5就是6,證明中至少有5個6度頂點或至少有6個5度頂點。證明:用反證法假設(shè)圖G中小于5個6度頂點且小于6個5度頂點,所有情況見下表5度頂點個數(shù)6度頂點個數(shù)存在情況54不滿足握手定理45不滿足小于5個6度頂點36不滿足小于5個6度頂點27不滿足小于5個6度頂點18不滿足小于5個6度頂點09不滿足小于5個6度頂點4．設(shè)圖有10條邊,3度與4度頂點各2個,其余頂點地度數(shù)均小于3,問中至少有幾個頂點？在最少頂點地情況下,寫出地度數(shù)列,與。解根據(jù)握手定理,圖中所有頂點地度數(shù)之與為20,除掉3度與4度頂點各2個外還剩余6度。因為其余頂點地度數(shù)均小于3,所以最少頂點地情況是還有3個頂點,它們地度數(shù)都是2。因此,中至少有7個頂點,在最少頂點地情況下,地度數(shù)列為（4,4,3,3,2,2,2）,。5.證明在任意具有個點地簡單二部圖中,邊數(shù)≤。證明:在二部圖中,邊數(shù)最多地是完全二部圖,設(shè)一邊有x個頂點,另一邊則有p-x個頂點,則邊q=x(p-x),當(dāng)x=p/2時,q值達(dá)到最大值,從而在任意具有個點地簡單二部圖中,邊數(shù)≤。6．某會議有名代表出席,已知任意四名代表中有一名代表與其余三名相識。證明:任意四名代表中必有一名與其余名代表都認(rèn)識。解設(shè)代表地集合為圖地頂點集合,若兩人相識,則其間連一條邊。這樣得到地圖是代表地相識圖。顯然是一個簡單圖,圖中頂點地度恰好表示該人認(rèn)識地其它代表地個數(shù)個數(shù)。利用圖,原題就抽象為下面地圖論問題:在一個簡單圖種,若任何4階導(dǎo)出子圖地頂點最大度數(shù)都為3,則圖中度數(shù)小于地頂點最多只有3個。下面用反證法來證明這個命題。假設(shè)圖中度數(shù)小于地頂點數(shù)超過3個,不妨設(shè),,,是其中地4個,,,,是分別與,,,不相鄰地頂點,下面分情況進(jìn)行分析:（1）假設(shè),,,中至多有兩個相異點,即至少有三個點重合,比如,則由,,,這4個頂點組成地導(dǎo)出子圖地頂點最大度數(shù)都必小于3,矛盾。（2）假設(shè),,,中至少有三個相異點,且有兩個相異點不是,,,中地點,比如,,則由,,,這4個頂點組成地導(dǎo)出子圖地頂點最大度數(shù)都必小于3,矛盾。（3）假設(shè),,,中至少有三個相異點,且有兩個相異點是,,,中地兩個點,比如,,則顯然,一個是,一個是,這樣由,,,這4個頂點組成地導(dǎo)出子圖地頂點最大度數(shù)都必小于3,矛盾。7．給出圖5.6（a）一個生成子圖與一個有3個點地導(dǎo)出子圖,對圖5.6（b）也一樣做。圖5.6習(xí)題7地圖解:二個圖地生成子圖分別如下所示:dbxvfazuecyw（b）有三個點地導(dǎo)出子圖分別如下所示:fzde