離散數學›Ch6 圖論第 2 題/共 34 題
2. 圖論、著色理論、獨立集、尤拉迴路、漢彌爾頓環
#LS-06-002中圖論著色理論獨立集尤拉迴路漢彌爾頓環
For the following graph:
(4 points) Its chromatic number is ___ (the smallest number of colors needed to color the nodes).
(4 points) The size of the maximum independent set is ___.
(1 point) Is it Eulerian ___ (yes/no)?
(1 point) Is it Hamiltonian ___ (yes/no)?

參考答案與解析
邊數:共18條邊。各頂點的鄰居:1:{8,9,4,5,7}、2:{4,6}、3:{5,6,7}、4:{8,2,1,5,7}、5:{9,1,4,7,3,6}、6:{2,3,5,7}、7:{1,4,5,6,3,9}、8:{1,4}、9:{1,5,7},度數依序為5,2,3,5,6,4,6,2,3,總和36,邊數=36/2=18。
Chromatic number = 4。下界:圖中存在4-clique(例如與,兩兩相鄰),故。上界:給出合法4著色——顏色1、顏色2、顏色3、顏色4,逐一檢查同色頂點兩兩皆不相鄰。故。
最大獨立集大小 = 4。下界:兩兩皆不相鄰,故。上界:以4個團(4-clique)、、、覆蓋全部9個頂點,任何獨立集在每個團最多取1點,故。故。
Eulerian:否。頂點1、3、4、9的度數為奇數(5,3,5,3),存在奇度數頂點,不滿足尤拉迴路的充要條件(所有頂點度數為偶)。
Hamiltonian:是。存在走訪全部9個頂點各一次並回到起點的迴圈:(已逐一核對每條邊皆存在於圖中)。
📄 台大113
▤完整推導請見《WH 資工筆記 · 離散數學》Ch6 圖論