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

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

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

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

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

設G的兩個獨立子圖的點集分別為u和V。由于歐拉圖的所有頂點的度數(shù)都是偶數(shù)，因此deg（U）和deg（V）是偶數(shù)。因為對于二部圖，e（g）=DEG（U）=DEG（V），g的邊數(shù)e（g）是偶數(shù)。

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