[理工]中山104離散

看板Grad-ProbAsk作者 (馬吉叫我辦的)時間9年前 (2017/01/12 10:06), 編輯推噓3(3推 0噓 14→)
留言17則, 6人參與, 最新討論串1/2 (看更多)
請問第六和七題怎麼寫? http://i.imgur.com/ho1Gpyz.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 182.235.130.102 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484186808.A.A04.html
推
01/12 10:27, , 1F
第六題：用矛盾證法，假設G不為connected,則G中至少存在
01/12 10:27, 1F
→
01/12 10:28, , 2F
兩個components, 假設C1=(V1,E1),C2=(V2,E2)為G中的兩個
01/12 10:28, 2F
→
01/12 10:28, , 3F
components,其中|V1|=n1,|V2|=n2. 則對於所有x屬於V1,
01/12 10:28, 3F
→
01/12 10:29, , 4F
deg(x)<=n1-1,對於所有y屬於V2,deg(y)<=n2-1. 由C1中取
01/12 10:29, 4F
→
01/12 10:29, , 5F
一點x1,和由C2中取一點y1,則deg(x1)+deg(y1)<=(n1-1)+
01/12 10:29, 5F
→
01/12 10:30, , 6F
(n2-1)=(n1+n2)-2=n-2,和題目假設deg(x)+deg(y)>=n-1矛
01/12 10:30, 6F
→
01/12 10:30, , 7F
盾，所以G一定是connected
01/12 10:30, 7F
推
01/12 10:59, , 8F
Transfet大的deg(x)<=n1-1 好像有點怪怪的應該是>=嗎？
01/12 10:59, 8F
→
01/12 11:05, , 9F
loop-free, deg<=n1-1沒錯吧
01/12 11:05, 9F
推
01/12 11:35, , 10F
感謝w181496大 是我搞錯定義了
01/12 11:35, 10F
→
01/12 12:42, , 11F
第七題，小黃課本p9-109
01/12 12:42, 11F
→
01/12 18:39, , 12F
我沒有小黃課本..
01/12 18:39, 12F
→
01/12 18:42, , 13F
1的c要怎麼解釋?沒看過
01/12 18:42, 13F
→
01/12 18:42, , 14F
01/12 18:42, 14F
→
01/12 20:40, , 15F
左陪集 在群環體的章節 其實名詞解釋的東西google就有了
01/12 20:40, 15F
→
01/12 23:34, , 16F
不好意思 再問一下第二題的b c和第三題和第四題的b c
01/12 23:34, 16F
→
01/12 23:34, , 17F
01/12 23:34, 17F
‣ 更多 h9638512 的文章
文章代碼(AID): #1OTkIue4 (Grad-ProbAsk)
‣ 更多 h9638512 的文章
文章代碼(AID): #1OTkIue4 (Grad-ProbAsk)