Educator头歌:离散数学 - 图论
第1关：图的概念
任务描述
本关任务：学习图的基本概念，完成相关练习。
相关知识
为了完成本关任务，你需要掌握：图的概念。
图的概念
1.一个图G是一个有序三元组G=<V,R,ϕ>，其中V是非空顶点集合，E是边的集合，ϕ是E到uv∣u,v∈V的映射，称为关联函数（当E为空集时，允许ϕ不存在）。例如，设G=<V,R,ϕ>,其中：
解释
V={v1,v2,v3}
解释
E={e1,e2,e3,e4,e5}
解释
ϕ(e1)=v1v3,
解释
ϕ(e2)=v1v2,
解释
ϕ(e3)=v1v2,
解释
ϕ(e4)=v2v3,
解释
ϕ(e5)=v3v3
第一关答案: B,C,D
第2关：图的表示
任务描述
本关任务：学习图的表示方法，完成相关练习。
相关知识
为了完成本关任务，你需要掌握：图的表示。
图的表示
一个图尤其顶点与边的关联关系唯一确定。对于图G(p,q)，我们可以用一个p行q列的矩阵来表示这种关系，可以使用关联矩阵和邻接矩阵来表示图。
关联矩阵：每一行i用来表示顶点，每一列j表示边，对于每个i,j我们将顶点i不属于边j的位置(i,j)用0来表示，属于则用1表示，如果有环则用2表示。 邻接矩阵：将行和列都表示顶点，将相邻的点之间用1表示，不相邻的点之间用0表示。
#coding=utf-8
import sympy as sym
# 使用关联矩阵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 *****#
# 使用关联矩阵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 *****#
# 使用邻接矩阵判断两个图是否相等，输出结果。
#***** Begin *****#
if B1 == B2:
print("True")
else:
print("False")
#***** End *****#第3关：单源最短通路问题
任务描述
本关任务：编程解决最短通路问题。
相关知识
为了完成本关任务，你需要掌握： 1.单源最短通路； 2.Dijkstra 算法。
单源最短通路
设 G 是一个图，对G的每一条边e,相应地赋以一个非负实数w(e)，称为边e的权，图G连同它的边上的权称为赋权图。 设 G 是一个赋权图，H≤G，令
设P是G的一条通路，通路上各边的权也称为该边的长度，通路的长度为W(P)。
单源最短通路，即求从一个点出发，到其他各点的最短路径，也就是说如果这个图有n个点，我们要求n-1个路径。
对一个图G来说，它的点集为V，我们要做的就是求出从起点v到V中其余各点的最短路径。以上图举例用矩阵表示带权通路图：
Dijkstra算法
关于单源最短通路问题，有效的解决算法为Dijkstra算法，其思想为：设置并不断扩充一个顶点集合S⊆V(G)。一个顶点属于S当且仅当从源到该顶点的通路以及距离已给出，初始时，S中仅含源。则我们可以把顶点集合V分成两组：
S：已求出的顶点的集合（初始时只含有源）；
V-S=T：尚未确定的顶点集合。
将T中顶点按递增的次序加入到S中，保证：
从源点到S中其他各顶点的长度都不大于从源到T中任何顶点的最短路径长度；
每个顶点对应一个距离值。
S中顶点：从源到此顶点的长度；
T中顶点：从源到此顶点的只包括S中顶点作中间顶点的最短路径长度。
Dijkstra 算法描述如下，其中输入的赋权图是简图G，V(G)={1,2,...,n}，1是源，C[i,j]表示边e=ij上的权。当顶点i与j不邻接时，令C[i,j]=∞,D[j]表示当前源到顶点i的最短特殊通路的长度。
第三关答案:
#coding=utf-8
import sympy as sym
# 输入一个整数，将值保存在变量 start
start = int(input())
# 用矩阵表示各点连接情况。
# ***** Begin *****#
n = 7 # 图中顶点的数量
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数据构建邻接表，输出该邻接表。
# ***** 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 *****#
# 初始化各项数据
# 把源点花费初始化为0，其他为无穷大（用99999代替）。
costs = [99999 for _ in range(n)]
costs[start] = 0
# 把各个顶点的父结点设置成-1。
parents = [-1 for _ in range(n)]
# 标记已确定好最短花销的点。
visited = [False for _ in range(n)]
# 已经确定好最短花销的点列表。
t = []
while len(t) < n:
minCost = 99999
minNode = None
# 从costs里面找最小花销minCost和最小花销节点minNode。
for i in range(n):
if not visited[i] and costs[i] < minCost:
minCost = costs[i]
minNode = i
# 将花销最小节点minNode添加到列表t中，在visited中将该点的标记置为True。
# ***** Begin *****#
t.append(minNode)
visited[minNode] = True
# ***** End *****#
# 从当前这个顶点出发，遍历与它相邻的顶点的边，计算最短通路，更新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
# 输出花费和前一节点的两个列表。
# ***** Begin *****#
print(costs)
print(parents)
# ***** End *****#