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)方個
簡單的離散數學問題，離散數學幾條簡單問題
1.s上的有序對有 1,1 1,2 2,1 2,2 4個 偏序關係需要滿足自反，反對稱，傳遞 即 1,1 2,2 都屬於偏序集，1,2 2,1 不能同時屬於偏序集 所以一共有2 2 1 3個偏序關係 因為s上有序對有4個，所以二元關係有2 4 16個2 4個元素集合的滿射，即是4個元素集合的雙射個數...
離散數學怎麼讀，離散數學符號讀法
連續的對應 就是反義詞 就是離散 離散就是不連續。例1 在生活中我們聽到的聲音是連續的，如人的說話聲，鳥叫聲等 而計算機裡儲存聲音的是離散的二進位制位元流，是經過抽樣，然後量化得到的離散資料。例2 我們在生活中，人眼見到的影象 非計算機裡的 是連續的，經過數位相機的拍照 抽樣和量化的過程 變成計算機...
離散數學的題目，離散數學題目的答案？
zzllrr小樂 這麼難的題目，懸賞分數為0，太摳了，步驟就不詳細提供了，提供一下關鍵思路 第1題 1 先把 e寫成合取形式。e a b c d 然後把含量詞公式代進去，求出前束正規化。2 把上面謂詞公式中所有存在量詞消去之後,得到該謂詞公式的skolem標準型 3 推理證明為假即可。第2題rp a...