tag:blogger.com,1999:blog-2365002100317196008.post6555826523509625375..comments2023-03-01T12:44:48.103-08:00Comments on Program City @ fbukevin: [離散] Euler Circuit and Hamiltonian Cycle Provefbukevinhttp://www.blogger.com/profile/05532388790974896442noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-2365002100317196008.post-6143483199662962312012-11-01T19:26:14.485-07:002012-11-01T19:26:14.485-07:00第三題中文筆記:
11vertices
53edges
53 * 2 = 106
vertic...第三題中文筆記:<br /><br />11vertices<br />53edges<br /><br />53 * 2 = 106<br /><br />vertices 最多是 C(11,2) = 55<br />當vertices為最大值時,每個點的deg(v) = n - 1 = 11-1 = 10 <br />但是只有 53 個邊 (表示拿掉兩個邊)<br /><br />至少有3個點 deg(v) < 10 <br />這個情況: <br />假設1個點拿掉2邊(deg = 8),另2個點各拿掉與前面那個點相連之邊(deg 各為 9) ,<br />因存在奇數degree的點,則EC不存在 <br />又任意兩個點 x, y, x!=y且不相鄰, deg(x) + deg(y) = sum of two of {8,9,10} > 11,所以存在 HC<br /><br />最多4個點 deg < 10<br />這個情況:<br />假設拿掉的兩個邊各屬不同兩對點{a,b}和{c,d}<br />則 deg(a,b,c,d) 都 = 9<br />因為存在奇數degree的點,所以不存在EC<br />又任意兩個點 x, y, x!=y 且不相鄰, deg(x) + deg(y) = sum of two of {9, 10} > 11 所以存在 HCfbukevinhttps://www.blogger.com/profile/05532388790974896442noreply@blogger.com