離散數(shù)學(xué)-二部圖，二部圖必須是連通圖嗎，下面這個(gè)是不是二部圖？利用二部圖的充要條件判定無向圖G是二部圖的充要條件當(dāng)且僅當(dāng)G至少有兩個(gè)頂點(diǎn)且其所有環(huán)的長度為偶數(shù)。顯然，在圖（a）中，有四個(gè)、六個(gè)和八個(gè)長

離散數(shù)學(xué)-二部圖，二部圖必須是連通圖嗎，下面這個(gè)是不是二部圖？

利用二部圖的充要條件判定無向圖G是二部圖的充要條件當(dāng)且僅當(dāng)G至少有兩個(gè)頂點(diǎn)且其所有環(huán)的長度為偶數(shù)。顯然，在圖（a）中，有四個(gè)、六個(gè)和八個(gè)長度的回路，它們是偶數(shù)，所以它們是二部圖

如何判斷將無向圖劃分成兩部分，使其兩兩不相鄰？

1.已知二部圖G是歐拉圖，證明g中有偶數(shù)個(gè)邊2.證明奇數(shù)個(gè)定點(diǎn)的二部圖不是哈密頓圖？

設(shè)G的兩個(gè)獨(dú)立子圖的點(diǎn)集分別為u和V。由于歐拉圖的所有頂點(diǎn)的度數(shù)都是偶數(shù)，因此deg（U）和deg（V）是偶數(shù)。因?yàn)閷τ诙繄D，e（g）=DEG（U）=DEG（V），g的邊數(shù)e（g）是偶數(shù)。

假設(shè)有一個(gè)頂點(diǎn)數(shù)為奇數(shù)的二元哈密頓圖G。因?yàn)镚是哈密頓圖，所以G中存在奇數(shù)個(gè)哈密頓環(huán)。因?yàn)镚是哈密頓圖，所以G中所有環(huán)的頂點(diǎn)數(shù)都是偶數(shù)。矛盾！因此，不存在這樣的二元哈密頓圖G。