Educator头歌:离散数学

第1关：图的概念

任务描述

本关任务：学习图的基本概念，完成相关练习。

第2关：图的表示

任务描述

本关任务：学习图的表示方法，完成相关练习。

相关知识

为了完成本关任务，你需要掌握：图的表示。

图的表示

一个图尤其顶点与边的关联关系唯一确定。对于图G(p,q)，我们可以用一个p行q列的矩阵来表示这种关系，可以使用关联矩阵和邻接矩阵来表示图。

关联矩阵：每一行i用来表示顶点，每一列j表示边，对于每个i,j我们将顶点i不属于边j的位置(i,j)用0来表示，属于则用1表示，如果有环则用2表示。邻接矩阵：将行和列都表示顶点，将相邻的点之间用1表示，不相邻的点之间用0表示。

#coding=utf-8import 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-8import 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 = 99999minNode = 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和parentsfor 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 *****#