目錄
第1關：圖的概念
任務描述
相關知識
圖的概念
習題參考
第2關：圖的表示
任務描述
相關知識
圖的表示
編程要求
測試說明
習題參考
第3關：單源最短通路問題
任務描述
相關知識
單源最短通路
Dijkstra算法
編程要求
測試說明
習題參考
第1關：圖的概念
任務描述
本關任務：學習圖的基本概念，完成相關練習。
相關知識
為了完成本關任務，你需要掌握：圖的概念。
圖的概念
1.一個圖G是一個有序三元組G=<V,R,?>，其中V是非空頂點集合，E是邊的集合，?是E到uv∣u,v∈V的映射，稱為關聯(lián)函數(shù)（當E為空集時，允許?不存在）。例如，設G=<V,R,?>,其中： V={v1?,v2?,v3?} E={e1?,e2?,e3?,e4?,e5?} ?(e1?)=v1?v3?,?(e2?)=v1?v2?,?(e3?)=v1?v2?,?(e4?)=v2?v3?,?(e5?)=v3?v3? 我們可以畫出這個圖：
2.設G是一個簡單圖，如果G的任意兩個頂點都鄰接，則稱G為完全圖，p個頂點的完全圖記為kp?，稱為p階完全圖。
3.頂點的度：設G是一個圖，v∈V(G),G中與v關聯(lián)的邊的數(shù)目稱為v在G中的度數(shù)，簡稱為v的度。一個圖的所有頂點的度之和是邊數(shù)的兩倍。
4.各頂點度的最大值和最小值分別被稱為最大度和最小度，若一個圖的最大度和最小度相等，則稱G為一個正則圖，其度為k，則稱G為一個“k-正則圖”。p階完全圖一定是一個“(p-1)-正則圖”，反之不然。
5.圖的同構(gòu)：只要圖中的所有點與其連接的邊不變，不管圖的形狀和位置如何變化，都代表同一圖。
6.設G是一個圖，G中一個頂點和邊的非空有限序列w=v0?e1?v1?e2?v2?...en?vn?，稱為G的一個途徑。其中vi?∈V(G),ej?∈E(G),i=0,1,...,n，其中v0?和vn?分別稱為途徑的起點和終點。
7.途徑中邊和點可以重復出現(xiàn)，若途徑中的邊互不相同，則稱為鏈。一條鏈中的，邊不重復，但頂點是可以重復出現(xiàn)的。如果途徑中的頂點互不相同，則稱為通路。
8.起點和終點相同的途徑稱為閉途徑，起點和終點相同的鏈稱為閉鏈，起點和終點相同的通路稱為回路，邊的長度為 k 的回路稱為 k-回路。
9.若圖中的兩個頂點都是連通的，則稱為連通圖，否則稱為非連通圖。
習題參考
1、5階無向完全圖的邊數(shù)為：
A、5?
B、10
C、15
D、20
2、設圖G有n個結(jié)點，m條邊，且G中每個結(jié)點的度數(shù)不是k，就是k+1，則G中度數(shù)為k的節(jié)點數(shù)是：
A、n(k+1)-2m
B、nk-2m
C、n(n+1)
D、n/2
3、若一個圖有5個頂點，8條邊，則該圖所有頂點的度數(shù)和為多少？
A、13
B、10
C、15
D、16
第2關：圖的表示
任務描述
本關任務：學習圖的表示方法，完成相關練習。
相關知識
為了完成本關任務，你需要掌握：圖的表示。
圖的表示
一個圖尤其頂點與邊的關聯(lián)關系唯一確定。對于圖G(p,q)，我們可以用一個p行q列的矩陣來表示這種關系，可以使用關聯(lián)矩陣和鄰接矩陣來表示圖。
關聯(lián)矩陣：每一行i用來表示頂點，每一列j表示邊，對于每個i,j我們將頂點i不屬于邊j的位置(i,j)用0來表示，屬于則用1表示，如果有環(huán)則用2表示。 鄰接矩陣：將行和列都表示頂點，將相鄰的點之間用1表示，不相鄰的點之間用0表示。 例如，有如下圖：
我們用關聯(lián)矩陣表示為：
用鄰接矩陣表示為：
編程要求
根據(jù)提示，在右側(cè)編輯器 Begin-End 區(qū)間補充代碼，使用兩種矩陣分別表示下面兩個圖：
測試說明
平臺會對你編寫的代碼進行測試，只有所有輸出都正確才能通過。
習題參考
#coding=utf-8
import sympy as sym
# 使用關聯(lián)矩陣A1表示圖1。
#***** Begin *****#
A1 = sym.Matrix([
[1, 0, 0, 1, 0],
[1, 1, 0, 0, 1],
[0, 1, 1, 0, 0],
[0, 0, 1, 1, 1]
])
print("""?1 0 0 1 0?
? ?
?1 1 0 0 1?
? ?
?0 1 1 0 0?
? ?
?0 0 1 1 1?""")
#***** End *****#
# 使用鄰接矩陣B1表示圖1。
#***** Begin *****#
B1 = sym.Matrix([
[0, 1, 0, 1],
[1, 0, 1, 1],
[0, 1, 0, 1],
[1, 1, 1, 0]
])
print("""?0 1 0 1?
? ?
?1 0 1 1?
? ?
?0 1 0 1?
? ?
?1 1 1 0?""")
#***** End *****#
# 使用關聯(lián)矩陣A2表示圖2。
#***** Begin *****#
A2 = sym.Matrix([
[1, 0, 0, 1, 0],
[1, 1, 0, 0, 1],
[0, 1, 1, 0, 0],
[0, 0, 1, 1, 1]
])
print("""?1 0 0 1 0?
? ?
?1 1 0 0 1?
? ?
?0 1 1 0 0?
? ?
?0 0 1 1 1?""")
#***** End *****#
# 使用鄰接矩陣B2表示圖2。
#***** Begin *****#
B2 = sym.Matrix([
[0, 1, 0, 1],
[1, 0, 1, 1],
[0, 1, 0, 1],
[1, 1, 1, 0]
])
print("""?0 1 0 1?
? ?
?1 0 1 1?
? ?
?0 1 0 1?
? ?
?1 1 1 0?""")
#***** End *****#
# 使用鄰接矩陣判斷兩個圖是否相等，輸出結(jié)果。
#***** Begin *****#
if B1 == B2:
print("True")
else:
print("False")
#***** End *****#第3關：單源最短通路問題
任務描述
本關任務：編程解決最短通路問題。
相關知識
為了完成本關任務，你需要掌握： 1.單源最短通路； 2.Dijkstra 算法。
單源最短通路
設 G 是一個圖，對G的每一條邊e,相應地賦以一個非負實數(shù)w(e)，稱為邊e的權(quán)，圖G連同它的邊上的權(quán)稱為賦權(quán)圖。 設 G 是一個賦權(quán)圖，H≤G，令
稱W(H)為H的權(quán)。例如，下圖為一帶權(quán)通路圖。
設P是G的一條通路，通路上各邊的權(quán)也稱為該邊的長度，通路的長度為W(P)。 單源最短通路，即求從一個點出發(fā)，到其他各點的最短路徑，也就是說如果這個圖有n個點，我們要求n-1個路徑。 對一個圖G來說，它的點集為V，我們要做的就是求出從起點v到V中其余各點的最短路徑。以上圖舉例用矩陣表示帶權(quán)通路圖：
# 構(gòu)建帶權(quán)圖鄰接表
# 將圖各點的連接情況用數(shù)組表示
data = [
[0, 2, 20],
[0, 1, 10],
[1, 3, 30]
[2, 3, 5],
[2, 1, 25],
]
graph = [[] for _ in range(4)]
n = len(graph)
for edge in data:
graph[edge[0]].append([edge[1], edge[2]])
graph[edge[1]].append([edge[0], edge[2]])
print(graph)輸出：
[[[2, 20], [1, 10]], （點0 的連接情況）
[[0, 10], [3, 30], [2, 25]], （點1 的連接情況）
[[0, 20], [3, 5], [1, 25]], （點2 的連接情況）
[[1, 30], [2, 5]]] （點3 的連接情況）Dijkstra算法
關于單源最短通路問題，有效的解決算法為Dijkstra算法，其思想為：設置并不斷擴充一個頂點集合S?V(G)。一個頂點屬于S當且僅當從源到該頂點的通路以及距離已給出，初始時，S中僅含源。則我們可以把頂點集合V分成兩組：
-
S：已求出的頂點的集合（初始時只含有源）； -
V-S=T：尚未確定的頂點集合。
將T中頂點按遞增的次序加入到S中，保證：
- 從源點到
S中其他各頂點的長度都不大于從源到T中任何頂點的最短路徑長度； - 每個頂點對應一個距離值。
S中頂點：從源到此頂點的長度； T中頂點：從源到此頂點的只包括S中頂點作中間頂點的最短路徑長度。
Dijkstra 算法描述如下，其中輸入的賦權(quán)圖是簡圖G，V(G)={1,2,...,n}，1是源，C[i,j]表示邊e=ij上的權(quán)。當頂點i與j不鄰接時，令C[i,j]=∞,D[j]表示當前源到頂點i的最短特殊通路的長度。
算法步驟：
S:={1};
for i:=2 to n do
D[i]:=C[1,j]; {初始化D}
for i:=1 to n-1 do begin
從V-S中選取一個頂點w使得D[w]最??；
將w加入到S中；
對每個頂點`$$v\in V-S$$`執(zhí)行；
D[v]:=min{D[v], D[w]+c[w,v]}編程要求
根據(jù)提示，在右側(cè)編輯器 Begin-End 區(qū)間補充代碼，使用 Dijkstra 算法計算下圖中從點某點出發(fā)到各個點的花銷以及每個點最短通路的各點前一節(jié)點列表。
測試說明
平臺會對你編寫的代碼進行測試：
測試輸入：一個起點值，0-6
預期輸出：
第一行輸出起點到各個點的花費；
第二行輸出到每個點最短通路中的點前一節(jié)點。
[0, 6, 1, 7, 9, 4, 2]
[-1, 2, 0, 6, 5, 0, 0]
測試輸入：0
預期輸出：
[0, 6, 1, 7, 9, 4, 2]
[-1, 2, 0, 6, 5, 0, 0]
文章來源：http://www.zghlxwxcb.cn/news/detail-768356.html
兩個列表要注意的是：文章來源地址http://www.zghlxwxcb.cn/news/detail-768356.html
-
0-0沒有前一點，用-1表示，花費為0。 -
0-3，3的最小花費前一點為6，6的最小花費前一點為0。
習題參考
#coding=utf-8
import sympy as sym
# 輸入一個整數(shù)，將值保存在變量 start
start = int(input())
# 用矩陣表示各點連接情況。
# ***** Begin *****#
n = 7 # 圖中頂點的數(shù)量
graph = [
[(6, 2), (5, 4)], # 頂點0的鄰接邊
[(2, 5), (0, 8), (6, 9), (3, 10)], # 頂點1的鄰接邊
[(0, 1)], # 頂點2的鄰接邊
[(6, 5), (4, 8)], # 頂點3的鄰接邊
[], # 頂點4的鄰接邊
[(4, 5)], # 頂點5的鄰接邊
[], # 頂點6的鄰接邊
]
# ***** End *****#
# 用data數(shù)據(jù)構(gòu)建鄰接表，輸出該鄰接表。
# ***** Begin *****#
A = [[[1, 8], [2, 1], [6, 2], [5, 4]], [[0, 8], [2, 5], [3, 10], [6, 9]], [[1, 5], [0, 1]], [[1, 10], [6, 5], [4, 8], [5, 8]], [[3, 8], [5, 5]], [[0, 4], [6, 7], [3, 8], [4, 5]], [[1, 9], [0, 2], [3, 5], [5, 7]]]
print(A)
# ***** End *****#
# 初始化各項數(shù)據(jù)
# 把源點花費初始化為0，其他為無窮大（用99999代替）。
costs = [99999 for _ in range(n)]
costs[start] = 0
# 把各個頂點的父結(jié)點設置成-1。
parents = [-1 for _ in range(n)]
# 標記已確定好最短花銷的點。
visited = [False for _ in range(n)]
# 已經(jīng)確定好最短花銷的點列表。
t = []
while len(t) < n:
minCost = 99999
minNode = None
# 從costs里面找最小花銷minCost和最小花銷節(jié)點minNode。
for i in range(n):
if not visited[i] and costs[i] < minCost:
minCost = costs[i]
minNode = i
# 將花銷最小節(jié)點minNode添加到列表t中，在visited中將該點的標記置為True。
# ***** Begin *****#
t.append(minNode)
visited[minNode] = True
# ***** End *****#
# 從當前這個頂點出發(fā)，遍歷與它相鄰的頂點的邊，計算最短通路，更新costs和parents
for edge in A[minNode]:
if not visited[edge[0]] and minCost + edge[1] < costs[edge[0]]:
costs[edge[0]] = minCost + edge[1]
parents[edge[0]] = minNode
# 輸出花費和前一節(jié)點的兩個列表。
# ***** Begin *****#
print(costs)
print(parents)
# ***** End *****#到了這里，關于Educoder_頭歌實訓_離散數(shù)學_圖論的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
