1樓：匿名使用者
證明 將這n個人作為n個結點，如果某兩個人認識，則這兩個人對應的結點之間存在一條邊，這樣就得到一個具有n個結點的無向圖，此時需證明的是，當n>=3時該圖存在一個哈密頓路，n>=4時，該圖存在一個哈密頓迴路，即該圖是哈密頓圖，下面給出證明。
首先證明當n>=3時該圖存在一個哈密頓路。
設u,v是任意兩個結點，由本題題意(任何2個人合起來認識其餘的n-2個人)可知，deg(u)+deg(v)>=n-2，下面需證明deg(u)+deg(v)>=n-1，否則如果deg(u)+deg(v)=n-2，分下面兩種情況討論：
1）如果u,v鄰接，此時deg(u)+deg(v)>=(n-2)+2=n> n-1;
2) 如果u,v不鄰接，則其餘的n-2個結點僅能與u,v中的一個結點相鄰接，設w是這其餘的任一結點（由n>=3可知結點w存在的），由於結點w僅能u,v其中之一鄰接，不妨設w與u鄰接，與v不鄰接，此時結點u和w均不與v鄰接，這與題意矛盾；
故deg(u)+deg(v)>=n-1，則該圖存在一個哈密頓路（參看任意一本離散數學書，如西北工業大學出版社出版劉長安編著《離散數學教程》p267）。
再證明當n>=4時，該圖存在一個哈密頓迴路。
下面需證明對任意兩個結點u,v有deg(u)+deg(v)>=n，仍分下面兩種情況討論：
1）如果u,v鄰接，此時deg(u)+deg(v)>=(n-2)+2=n;
2) 如果u,v不鄰接，如果deg(u)+deg(v)=n-1，此時除u,v外其餘的結點中存在一個結點s與u,v均鄰接，另一個結點w僅與u,v其中之一鄰接，（由n>=4可知結點s與w是存在的），不妨設w與u鄰接，與v不鄰接，此時結點u和w均不與v鄰接，這又與題意矛盾；
故deg(u)+deg(v)>=n，則該圖存在一個哈密頓路（參看任意一本離散數學書，同上書p268）。
2樓：祁航鍾珏
用真值表法看
你命題有多少個變元
那就知道有多少個
極小項極大項
所以例如
你的是永真式
那主析取正規化
就是所有極小項析取
反之不用說了吧
還有定理：任何公式都有與之等價的主析取正規化和主合取正規化我小學沒畢業
不知道說得對或者錯
希望對你有用吧
3樓：狗蛋兒
圖論嘛。。。自己翻書啦
離散數學的小問題？
4樓：琉璃蘿莎
設有一個關係r,集合a,如果a中的任意元素x都滿足：xrx,則關係r是自反的.
就用的例子來說,在整數集中,任意取一個數字x,都滿足：x小於等於x所以：小於等於關係是自反的.
假設有一個集合a= b=
則a包含b,b包含於a
b中所有的元素都能在a中找到
離散數學 樹的問題
5樓：林夢嫣
答案是a
一個k層的完全二叉樹的節點共2的k次方減一個節點。
第k層全是葉節點，一共2的(k-1)方個葉節點。
計算規律：第一層1個，第二層2個，第三層4個，。。。。第k層2的(k-1)方個
離散數學問題，離散數學難題
a b a b a b a c a c a c a b b a c a b b a b c 分配律 a b a b b c 交換律 排序 a b a b b c 結合律 a b c c a b c c a a b c 補項 a b c a b c a b c c a a b c 分配律2 a b c...
離散數學 集合論的問題，離散數學集合論問題
集合a a裡的元素是1,2，可以說1屬於a，2屬於a，屬於a，屬於a。而是包含於a但不屬於a 集合的概念要分清包含，屬於，元素與集合之間是屬於關係，集合與集合之間是包含 包含於的關係 1 集合a的元素一共有4個，是 1 2 1 3 沒有。2 如果集合a 1，2，那麼 a是成立的。離散數學集合論問題 ...
離散數學漢密爾頓道路的問題,離散數學,漢密爾頓圖問題
所謂的漢密爾頓道路是抄指通過所有的端點一次且僅一次的迴路,而對於漢密爾頓圖的判斷沒有相應的充分不要條件,只有少數特殊情況才有充分必要條件,二部圖就是特殊的一種。二部圖中,其兩部分的端點個數相等,就是漢密爾頓圖 如果兩部分端點個數相差1,就是半漢密爾頓圖 如果兩部分端點個數相差2,就是皆不是 所以選a...