• 離散的數學課件.ppt 126頁

    • 0
    • 0
    • 0
    • 約1.92萬字
    • 2020-11-08 發布
    文檔工具:
      1. 1、本文檔共126頁,可閱讀全部內容。
      2. 2、本文檔內容版權歸屬內容提供方,所產生的收益全部歸內容提供方所有。如果您對本文有版權爭議,可選擇認領,認領后既往收益都歸您。
      3. 3、本文檔由用戶上傳,本站不保證質量和數量令人滿意,可能有諸多瑕疵,付費之前,請仔細先通過免費閱讀內容等途徑辨別內容交易風險。如存在嚴重掛羊頭賣狗肉之情形,可聯系本站下載客服投訴處理。
      4. 文檔侵權舉報電話:19940600175。
      記Al=(ailj)n?n(l 為正整數),則 1)當i?j時, 表示從結點vi到vj長度為l的通路的條數。 2)當i=j時, 表示經過結點vi的長度為l的回路的條數。 例題:略 2、連接矩陣 定義:設G=<V,E>為簡單圖,V={v1,v2,…vn},則n階矩陣C=(cij)n?n稱為G的連接矩陣,其中 * 如果vi與vj連通,則cij=1;如果vi與vj不連通,則cij=0 連接矩陣的性質: 1、C是對稱矩陣,且主對角線元素全為1。 2、G是連通圖當且僅當C的元素全為1 3、設A= (aij)n?n是簡單圖G的鄰接矩陣,則C=A0⊕A1⊕… ⊕An-1 其中⊕為布爾加法 例題:略 3、關聯矩陣 定義:設無向圖G=<V,E>,V= {v1,v2,…vn}, * E={e1,e2,…,em},則n?m矩陣M=(mij) n?m稱為圖G的關聯矩陣,其中mij表示vi與ej的關聯次數。 關聯矩陣的性質: 1、關聯矩陣每列之和為2 2、每行之和是該結點的度數。 3、元素全為0的行,對應的點是孤立點。 4、相同的兩列對應一對平行邊。 5、M中所有元素之和等于邊數的2倍。 * 有向圖的矩陣表示 1、鄰接矩陣 定義:設G=<V,E>是有向圖,V={v1,v2,…vn}, n?n矩陣A=(aij) n?n稱為圖G的鄰接矩陣,其中aij表示以為vi起點, vj為終點的邊的條數。 例:略 鄰接矩陣的性質: 1、A的第i行元素之和為結點vi的出度。 2、 A的第i列元素之和為結點vi的入度。 * 定理:設有向圖G的鄰接矩陣為A= (aij)n?n記Al=( )n?n(l 為正整數),則 1)當i?j時, 表示從結點vi到vj長度為l的通路的條數。 2)當i=j時, 表示經過結點vi的長度為l的回路的條數。 例:略 2、可達矩陣 定義:設G=<V,E>是有向圖, V={v1,v2,…vn}, n?n矩陣P=(pij) n?n稱為圖G的可達矩陣,其中 * 如果從vi到vj是可達的pij =1,否則pij =0 從定義我們可以看到,可達矩陣具有以下性質: 1、可達矩陣是一個0,1矩陣,其主對角線元素全為1。 2、有向圖G是強連通的當且僅當其可達矩陣的元素全為1。 定理:設A= (aij)n?n是簡單有向圖G的鄰接矩陣,則P=E⊕A1⊕… ⊕An-1,其中⊕為布爾加法 * 例:略 3、關聯矩陣 定義:設無向圖G=<V,E>,V= {v1,v2,…vn}, E={e1,e2,…,em},則n?m矩陣M=(mij) n?m稱為圖G的關聯矩陣,其中當vi為ej的起點時mij=1;當vi為ej的終點時mij=-1;當vi與ej不關聯時mij=0 關聯矩陣的性質: 1、關聯矩陣是一個以-1,0,1位元素的矩陣 * 2、關聯矩陣每一列元素之和為0;每一行元素中1的個數等于對應結點的出度,每一行元素中-1的個數等于對應結點的入度。 3、相同兩列對應一對平行邊,元素全為0的行對應孤立點。 第四節 歐拉圖與哈密爾頓圖 定義:對給定的無孤立結點的無向圖G,如果存在一條路,它經過圖中每條邊一次且僅一次,則該路稱為歐拉路 * 如果存在一條回路,經過圖中每條邊一次且僅一次,則該回路稱為歐拉回路。 具有歐拉回路的圖稱為歐拉圖。 例:略 歐拉圖的判定: 定理1:一個無向圖G具有歐拉路當且僅當G是連通的,并且具有0個或2個度數為奇數的結點。 定理2:無向圖G具有歐拉回路當且僅當G是連通的,且所有結點的度數都為偶數。 * 推論:無向圖G是歐拉圖當且僅當G是連通的、且沒有度數為奇數的結點。 一筆畫問題: 對于有向圖,有類似的概念 定義:對有向圖D,經過每條邊一次且僅一次的一條單向路(回路),稱為歐拉路(回路) 具有歐拉回路的有向圖稱為歐拉圖 定理3:有向圖G具有單向歐拉路當且僅當D是連通的、且每個結點的入度等于出度。 推論:有向圖G是歐拉圖當且僅當D是連通的、且每個結點的入度等于出度 * 注:①同態具備的性質同構肯定具備。反之則未必 ②自同態與自同構 例:略 兩個同構的代數結構稱之為是代數相等的。 第四節 半群與獨異點 定義:設<S,?>是一代數系統,如果運算?滿足結合律,則稱<S,?>是半群。 例:略 * 定義:一個具有單位元的半群稱為幺半群或獨異點。 例:略 在獨異點中我們可以進一步規定: a2=a?a,…,an+1=an?a,a0=e,a-n=(a-1)n 定義:<S,?>是半群,B?S,如果<B,?>也是半群,則稱<B,?>是<S,?>子半群。 注:驗證方法 定義:<S,?>是獨異點,T?S,如果<T,?>也是半群,且e∈T,則稱<T,?>是<S,?>子獨異點。 * 第五節 群與子群 定義:設<G,?>為一代數系統,如果滿足: 1、G對運算?是封閉的 2、運算?

      文檔評論(0)

      • 內容提供方:懶懶老巢
      • 審核時間:2020-11-08
      • 審核編號:5311203004003022

      相似文檔

      1216彩票