python第六章课后习题
点击查看代码
import matplotlib.pyplot as plt
G = nx.Graph()
nodes = ['v1', 'v2', 'v3', 'v4', 'v5', 'v6']
G.add_nodes_from(nodes)
edges = [
('v1', 'v2'), ('v1', 'v3'), ('v1', 'v4'),
('v2', 'v3'), ('v2', 'v6'),
('v3', 'v4'),
('v4', 'v5'),
('v5', 'v6')
]
G.add_edges_from(edges)
pos = nx.circular_layout(G)
center = (0, 0)
pos['v1'] = center
plt.figure(figsize=(8, 8))
nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=700, font_size=15, font_weight='bold')
plt.title("Undirected Graph as Described")
plt.axis('equal')
plt.show()
print("学号：3028")
print("学号：2023310143028")
点击查看代码
import matplotlib.pyplot as plt
G = nx.Graph()
nodes = ['v1', 'v2', 'v3', 'v4', 'v5', 'v6']
G.add_nodes_from(nodes)
edges = [
('v1', 'v2', 7),
('v1', 'v3', 3),
('v1', 'v4', 12),
('v2', 'v3', 1),
('v2', 'v6', 1),
('v3', 'v4', 8),
('v4', 'v5', 9),
('v5', 'v6', 3)
]
G.add_weighted_edges_from(edges)
pos = nx.circular_layout(G)
center = (0, 0)
pos['v1'] = center
def draw_edges_with_weights(G, pos):
edge_labels = {(u, v): d['weight'] for u, v, d in G.edges(data=True)}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.figure(figsize=(10, 10))
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=700, font_size=15, font_weight='bold')
draw_edges_with_weights(G, pos)
plt.title("Undirected Graph with Weights")
plt.axis('equal')
plt.show()
print("学号：3028")
print("学号：2023310143028")
点击查看代码
import matplotlib.pyplot as plt
G = nx.DiGraph()
nodes = ['v1', 'v2', 'v3', 'v4', 'v5', 'v6']
G.add_nodes_from(nodes)
edges = [
('v2', 'v1', 7),
('v1', 'v3', 3),
('v4', 'v1', 12),
('v2', 'v3', 1),
('v6', 'v2', 1),
('v3', 'v4', 8),
('v5', 'v4', 9),
('v5', 'v6', 3)
]
G.add_weighted_edges_from(edges)
pos = nx.circular_layout(G)
def draw_edges_with_weights(G, pos):
edge_labels = {(u, v): d['weight'] for u, v, d in G.edges(data=True)}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color='red')
plt.figure(figsize=(10, 10))
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=700, font_size=15, font_weight='bold', arrows=True)
draw_edges_with_weights(G, pos)
plt.title("Directed Graph with Weights")
plt.axis('equal')
plt.show()
print("学号：3028")
print("学号：2023310143028")
点击查看代码
def prim(graph, start):
num_nodes = len(graph)
visited = [False] * num_nodes
min_heap = [(0, start, -1)]
mst_cost = 0
mst_edges = []
while min_heap:
weight, u, parent = heapq.heappop(min_heap)
if visited[u]:
continue
visited[u] = True
mst_cost += weight
if parent != -1:
mst_edges.append((parent, u, weight))
for v in range(num_nodes):
if not visited[v] and graph[u][v] != 0:
heapq.heappush(min_heap, (graph[u][v], v, u))
return mst_cost, mst_edges
graph = [
[0,20,0,0,15,0],
[20,0,20,60,25,0],
[0,20,0,30,18,0],
[0,60,30,0,35,10],
[0,0,0,10,15,0]
]
mst_cost, mst_edges = prim(graph, 0)
print("Prim's MST Cost:", mst_cost)
print("Prim's MST Edges:", mst_edges)
print("学号：3028")
print("学号：2023310143028")
点击查看代码
import heapq initial_costs = [2.5, 2.6, 2.8, 3.1]
salvage_values = [2.0, 1.6, 1.3, 1.1]
maintenance_costs = [0.3, 0.8, 1.5, 2.0]
dp = [[float('inf')] * 2 for _ in range(4)]
dp[0][1] = initial_costs[0] + maintenance_costs[0]
for i in range(1, 4):
dp[i][1] = min(dp[i-1][1] + maintenance_costs[i],
initial_costs[i] + maintenance_costs[i])
if i > 0:
dp[i][0] = dp[i-1][1] + salvage_values[i-1]
min_cost = min(dp[3][1],
min(dp[i][0] for i in range(3)))
print(f"最优更新策略下的4年内最小总费用为：{min_cost}万元")
print("学号：3028")
print("学号：2023310143028")
runfile('C:/Users/ddrrg/.spyder-py3/PYTHON2/习题6.5.py', wdir='C:/Users/ddrrg/.spyder-py3/PYTHON2')
点击查看代码
distances = np.array([
[0, 2, 7, np.inf, np.inf, np.inf],
[2, 0, 4, 6, 8, np.inf],
[7, 4, 0, 1, 3, np.inf],
[np.inf, 6, 1, 0, 1, 6],
[np.inf, 8, 3, 1, 0, 3],
[np.inf, np.inf, np.inf, 6, 3, 0]
], dtype=float)
students = np.array([50, 40, 60, 20, 70, 90])
hospital_distances_sum = np.sum(distances, axis=1) - np.diag(distances) # 使用diag获取对角线元素（自身到自身的距离）并从总和中减去
hospital_location = np.argmin(hospital_distances_sum)
print(f"医院应该建在村庄 {chr(65 + hospital_location)} 处，使得最远村庄的人到医院看病所走的路最短。")
distances_finite = np.where(np.isinf(distances), np.inf * 1e-5, distances) # 用一个很小的数替换np.inf
weighted_distances_matrix = distances_finite * students
school_total_distances = np.sum(weighted_distances_matrix, axis=0)
school_location = np.argmin(school_total_distances)
print(f"小学应该建在村庄 {chr(65 + school_location)} 处，使得所有学生上学走的总路程最短。")
print("学号：3028")
print("学号：2023310143028")
runfile('C:/Users/ddrrg/.spyder-py3/PYTHON2/习题6.6.py', wdir='C:/Users/ddrrg/.spyder-py3/PYTHON2')
点击查看代码
matches = np.array([
[0, 1, 0, 1, 1, 1],
[0, 0, 0, 1, 1, 1],
[1, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 1],
[0, 0, 1, 0, 0, 1],
[0, 0, 1, 0, 0, 0]
], dtype=int)
n = matches.shape[0]
closure = matches.copy()
for k in range(n):
for i in range(n):
for j in range(n):
closure[i, j] = closure[i, j] or (closure[i, k] and closure[k, j])
strength = closure.sum(axis=1)
ranking = np.argsort(-strength)
for i, rank in enumerate(ranking):
print(f"{chr(65 + rank)}队 排名 {i + 1}")
import numpy as np
from scipy.sparse import csr_matrix
edges = [
(0, 1), (0, 3), (0, 4), (0, 5),
(1, 3), (1, 4), (1, 5),
(2, 0), (2, 1), (2, 3),
(3, 4), (3, 5),
(4, 2), (4, 5),
(5, 2)
]
num_teams = 6
row_ind = []
col_ind = []
data = []
for u, v in edges:
row_ind.append(u)
col_ind.append(v)
data.append(1)
adj_matrix = csr_matrix((data, (row_ind, col_ind)), shape=(num_teams, num_teams))
adj_matrix_T = adj_matrix.T
d = 0.85
out_degree = np.array(adj_matrix_T.sum(axis=1)).flatten()
out_degree[out_degree == 0] = 1
M = adj_matrix_T.multiply(1.0 / out_degree).tocsr()
M = M + (1 - d) / num_teams * csr_matrix(np.ones((num_teams, num_teams)))
R = np.ones(num_teams) / num_teams
num_iterations = 100
for _ in range(num_iterations):
R = R.dot(M.toarray())
pagerank_ranking = np.argsort(-R)
for i, rank in enumerate(pagerank_ranking):
print(f"{chr(65 + rank)}队 PageRank排名 {i + 1}")
print("学号：3028")
print("学号：2023310143028")
