期末復習ppt課件-展示頁
2025-05-08 02:55本頁面
【正文】 1) 歐拉圖與歐拉環(huán)游 (2) 歐拉跡 對于連通圖 G，如果 G中存在經過每條邊的閉跡，則稱 G為歐拉圖，簡稱 G為 E圖。 途徑 (閉途徑 )，跡 (閉跡 ), 路 (圈 ), 最短路，連通圖，連通分支，點連通度與邊連通度。 1 0 x t 0 1 2 ?1 ? 0 1 n 10 (6) 完全 m元樹 對于根樹 T，若每個分支點至多 m個兒子，稱該根樹為 m元根樹；若每個分支點恰有 m個兒子，稱它為完全 m元樹。其中入度為 0的點稱為樹根，出度為 0的點稱為樹葉，入度為 1，出度大于 1的點稱為內點。 注：要求熟練掌握最小生成樹的求法。 (4) 最小生成樹 在連通邊賦權圖 G中求一棵總權值最小的生成樹。 1 0 x t 0 1 2 ?1 ? 0 1 n 9 (3) 生成樹 圖 G的一個生成子圖 T如果是樹，稱它為 G的一棵生成樹；若 T為森林，稱它為 G的一個生成森林。 (1) 樹 不含圈的圖稱為無圈圖，樹是連通的無圈圖。記為 12G G G?? 1 0 x t 0 1 2 ?1 ? 0 1 n 8 (9) 偶圖 所謂具有二分類（ X, Y）的偶圖（或二部圖）是指一個圖，它的點集可以分解為兩個 (非空 )子集 X和 Y，使得每條邊的一個端點在中，另一個端點在 Y中 . 注 : 掌握偶圖的判定。對點集 1 1 1 2 2 2( , ) , ( , ) ,G V E G V E?? 12V V V??的任意兩個點 u=(u1,u2)與 v=(v1,v2),當 (u1=v1和 u2adjv2)或 (u2=v2和u1adjv1)時， 把 u與 v相連。 1 0 x t 0 1 2 ?1 ? 0 1 n 7 (7) 聯(lián)圖 設 G1,G2是兩個不相交的圖，作 G1+G2，并且將 G1中每個頂點和 G2中的每個頂點連接，這樣得到的新圖稱為 G1與 G2的聯(lián)圖。 1 0 x t 0 1 2 ?1 ? 0 1 n 6 (6) 補圖與自補圖 1) 對于一個簡單圖 G =（ V, E），令集合 ? ?1 ,E u v u v u v V? ? ?則圖 H =（ V， E1\E） 稱為 G的補圖，記為 HG?2) 對于一個簡單圖 G =（ V, E），若 ，稱 G為自補圖。稱 G1與 G2同構，記為： ?? ??12GG? 例 1 指出 4個頂點的非同構的所有簡單圖。 (5) 圖的同構： 1 0 x t 0 1 2 ?1 ? 0 1 n 5 設有兩個圖 G1=(V1,E1)和 G2=(V2,E2),若在其頂點集合間存在雙射，使得邊 之間存在如下關系：設 u1?u 2v1?v 2, u1,v1 V1, u2,v2 V2。 (4) 圖的圖序列： 一個非負數(shù)組如果是某簡單圖的度序列，我們稱它為可圖序列，簡 稱圖序列。 1 0 x t 0 1 2 ?1 ? 0 1 n 4 (3) 圖的度序列： 一個圖 G的各個點的度 d1, d2,…, dn構成的非負整數(shù)組 (d1, d2,…, dn)稱為 G的度序列 。用 |E|表示邊數(shù)。 1 0 x t 0 1 2 ?1 ? 0 1 n 1 圖論及其應用 復習課件 數(shù)學科學學院 1 0 x t 0 1 2 ?1 ? 0 1 n 2 本次課主要內容 (二 )、重要結論 期末復習 (一 )、重點概念 (三 )、應用 1 0 x t 0 1 2 ?1 ? 0 1 n 3 (一 )、重點概念 圖、簡單圖、圖的同構與自同構、度序列與圖序列、補圖與自補圖、兩個圖的聯(lián)圖、兩個圖的積圖、偶圖； (1) 圖：一個圖是一個序偶 V,E，記為 G=(V,E),其中： 1) V是一個有限的非空集合，稱為頂點集合 ,其元素稱為頂點或點。用 |V|表示頂點數(shù)； 2) E是由 V中的點組成的無序對構成的集合，稱為邊集，其元素稱為邊，且同一點對在 E中可以重復出現(xiàn)多次。 (2) 簡單圖：無環(huán)無重邊的圖稱為簡單圖。 注：度序列的判定問題是重點。 注：度序列的判定問題是重點。 u1v1 E1,當 且僅當 u2v2 E2,且 u1v1與 u2v2的重數(shù)相同。 分析：四個頂點的簡單圖最少邊數(shù)為 0，最多邊數(shù)為 6，所以 可按邊數(shù)進行枚舉。 GG?注：要求掌握自補圖的性質。記為 ： 12GG?(8) 積圖 設 是兩個圖。如此得到的新圖稱為 G1與 G
教學課件相關推薦
鄂ICP備17016276號-1