第8章圖論
例1、下面哪些數的序列,可能是乙個圖的度數序列?如果可能,請試畫出它的圖. 哪些可能不是簡單圖?
a) (1,2,3,4,5) b) (2,2,2,2,2) c) (1,2,3,2,4) d) (1,1,1,1,4) e) (1,2, 2,4,5)
解:a)不是, 因為有三個數字是奇數. b) c) d)是.
e) 不是簡單圖,因為它有5個結點, 有乙個結點度為5, 必然有環或平行邊.
例2、已知無向簡單圖g中,有10條邊,4個3度結點,其餘結點的度均小於或等於2,問g中至少有多少個結點?為什麼?
解:已知邊數|e|=10, ∑deg(v)=2|e|=20其中有4個3度結點, 餘下結點度之和為: 20-3×4=8
因為g是簡單圖, 其餘每個結點度數≤2, 所以至少還有4個結點.所以g中至少有8個結點.
強連通、單側連通和弱連通
在簡單有向圖g中,如果任何兩個結點間相互可達, 則稱g是強連通. 如果任何一對結點間, 至少有乙個結點到另乙個結點可達, 則稱g是單側連通. 如果將g看成無向圖後(即把有向邊看成無向邊)是連通的,則稱g是弱連通.
在簡單有向圖中,具有強連通的最大子圖,稱為強分圖.具有單側連通的最大子圖,稱為單側分圖. 具有弱連通的最大子圖,稱為弱分圖.
注：我每次都會被各種分圖弄糊塗！！考試時要注意啊，千萬不要錯了
利用可達性矩陣求強分圖，注意初等矩陣變換的知識不要忘了！！
令圖g=, 集合siv si』=v-si , 令|v|=n
si=si』=
dijkstra演算法:(求從u0到各點u的最短路長)
第一步. 置初值: d(u0,u0)=0 d(u0,v)=∞ (其中v≠ u0)
i=0s0= s0』=v-s0 ,
第二步.若 i=n-1 則停. 否則轉第三步
第三步. 對每個u』∈si』
計算 d(u0,u』)=min ui ∈si計算 minu』∈si』
並用ui+1記下達到該最小值的那個結點u』
置si+1 =si∪ i=i+1 si』=v-si , 轉第二步.
例3、求最短路
解：例.求右圖中從v1到v6的
最短路1.置初值: u0=v1
d(u0,u0)=0
d(u0,v2)=d(u0,v3)=d(u0,v4)=d(u0,v5)=d(u0,v6)=∞
2.3. i=0 s0= s0』=
d(u0,v2)=min=min=3
d(u0,v3)=min=min=∞
d(u0,v4)=min=min=5
d(u0,v5)=min=min=∞
d(u0,v6)=min=min=∞
min=3
ui+1 =u1=v2實際已求出d(u0,v2)=3, 路是u0v2
i=1 s1=
s1』=
u1=v2
d(u0,u1)=3
d(u0,v3)=min=min=9
d(u0,v4)=min=min=4
d(u0,v5)=min=min=∞
d(u0,v6)=min=min=∞
min=4
ui+1 =u2=v4實際已求出d(u0,v4)=4, 路是u0v2v4
i=2 s2=
s2』=
u2=v4
d(u0,u2)=4
d(u0,v3)=min=min=7
d(u0,v5)=min=min=5
d(u0,v6)=min=min=∞
min=5
ui+1 =u3=v5實際已求出d(u0,v5)=5, 路是u0v2v4 v5
i=3 s3=
s3』=
u3=v5
d(u0,u3)=5
d(u0,v3)=min=min=7
d(u0,v6)=min=min=11
min=7
ui+1 =u4=v3實際已求出d(u0,v3)=7, 路是u0v2v4 v3
i=4 s3= s3』= u4=v3 d(u0,u4)=7
d(u0,v6)=min=min=10
min=10
ui+1 =u5=v6 , 實際已求出d(u0,v6)=10, 路是u0v2v4 v3 v6
i=5 (n-1) 時演算法停止.
例4、求關鍵路徑。
例如, 求右圖的關鍵路徑
(1)求各個結點的最早完成時間:
計算時，從前向後
逐個結點計算。
te(v1)=0
te(v2)=max=1v1 － v2的先驅結點)
te(v3)=max=2 (v1v2 － v3的先驅結點)
te(v4)=max=4 (v1v3 － v4的先驅結點)
te(v5)=max=8 (v2v4 － v5的先驅結點)
te(v6)=max=9 (v3v5 － v6的先驅結點)
te(v7)=max=6 (v2v3 － v7的先驅結點)
te(v8)=max=12 (v6v7 － v8的先驅結點)
(2)求各個結點的最晚完成時間:
計算時，從後向前
逐個結點計算。
tl(v8)=te(v8)=12
tl(v7)=min=6v8)
tl(v6)=min =11v8)
tl(v5)=min =10v6)
tl(v4)=min =6v5)
tl(v3)=min =2 (v4v6v7)
tl(v2)=min =2 (v3v5v7)
tl(v1)=min =0 (v2v3v4)
(3)求各個結點的緩衝時間
ts(vi)=tl(vi)-te(vi)
關鍵路徑為: v1v3v7v8
例5、設g是結點數n≥3的簡單圖，若邊數m≥(1/2)(n-1)(n-2)+2，證明g中存在漢密爾頓迴路。
證明：假設g不存在漢密爾頓迴路(不是h圖)，由h圖充分條件判定定理可知，g中必存在結點u1、u2,使得deg(u1)+deg(u2)≤n-1，即關聯這兩個結點的邊數最多為n-1。
在圖g－中：結點數為n－2, 邊數≤(1/2)(n-2)(n-3)
g中邊數 m≤(1/2)(n-2)(n-3)+(n-1) ＜(1/2)(n-2)(n-3)+n=(1/2)(n2-5n+6)+n
1/2)(n2-5n+6+2n) =(1/2)(n2-3n+6)
1/2)[(n2-3n+2)+4]= (1/2)(n2-3n+2)+2
1/2)(n-1)(n-2)+2
與已知矛盾，所以g中存在漢密爾頓迴路。
例6、平面圖的尤拉公式是d=m-n+2 (r=e-v+2)?簡單平面圖g中至少有乙個結點的度小於幾？
解：由尤拉公式 v-e+r=2，所以r=e-v+2 (d=m-n+2 )成立。簡單平面圖g中至少存在乙個結點的度數小於6。
因為如果圖g的結點數v≤6時，所有結點的度均小於等於5。結論顯然成立。
學習離散數學總結
學習離散數學的心得體會 姓名 學號 1 班級 計算機 離散數學，對絕大多數學生來說應該都會是一門十分困難的課程，當然也包括我在內。通過這一學期的學習，我對這門課程有一些初步的了解，現在的心情和當初也很不相同。在還沒有接觸的時候，看見課本就想退縮，心想 這是什麼課程啊，這叫數學嗎，這些符號都是之前沒有...
離散數學考題總結
第1章主要介紹集合論的基本概念和結論，集合的運算及其性質，以及利用運算性質進行集合表示式的化簡和集合恒等式的證明等內容 考試經常涉及到的題型有以下4個 集合與集合之間的包含 元素與集合之間的屬於關係 冪集的計算 集合之間的運算 利用集合運算性質證明集合恒等式 大家對於集合與集合 元素和集合之間的關係...
離散數學 複習
第1章命題邏輯 本章重點 命題與聯結詞，公式與解釋，真值表，公式的型別及判定,主 析取 合取 正規化，命題邏輯的推理理論.一 重點內容 1.命題 命題表述為具有確定真假意義的陳述句。命題必須具備二個條件 其一，語句是陳述句 其二，語句有唯一確定的真假意義.2.六個聯結詞及真值表 否定聯結詞，p是命題...