6.1（1）
import networkx as nx
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='white', node_size=800, font_size=20, font_weight='black')
plt.title("Undirected Graph as Described")
plt.axis('equal')
plt.show()
print("3023")
结果
6.1（2）
import networkx as nx
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)
]
pos = nx.circular_layout(G)
center = (0, 0)
pos['v1'] = center
G.add_weighted_edges_from(edges)
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=(8, 8))
nx.draw(G, pos, with_labels=True, node_color='white', node_size=800, font_size=20, font_weight='black')
draw_edges_with_weights(G,pos)
plt.title("Undirected Graph with weights")
plt.axis('equal')
plt.show()
print("3023")
结果
6.1（3）
import networkx as nx
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)
]
pos = nx.circular_layout(G)
center = (0, 0)
pos['v1'] = center
G.add_weighted_edges_from(edges)
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=(8, 8))
nx.draw(G, pos, with_labels=True, node_color='white', node_size=800, font_size=20, font_weight='black')
draw_edges_with_weights(G,pos)
plt.title("directed Graph with weights")
plt.axis('equal')
plt.show()
print("3023")
结果
6.3
import heapq
def prim(graph, start):
num_nodes = len(graph)
visited = [False] * num_nodes
min_heap = [(0, start, -1)]
total_mst_cost = 0
mst_edges = []
while min_heap:
weight, u, parent = heapq.heappop(min_heap)
if visited[u]:
continue
visited[u] = True
total_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 total_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, 25, 18, 35, 0, 0],
]
mst_cost, mst_edges = prim(graph[:5], 0)
print("Prim's MST Cost:", mst_cost)
print("Prim's MST Edges:")
for edge in mst_edges:
print(edge)
print("3023")
结果
6.4
initial_costs = [2.5, 2.6, 2.8, 3.1]
salvage_values = [0.0, 2.0, 1.6, 1.3, 1.1]
maintenance_costs = [0.3, 0.8, 1.5, 2.0]
def calculate_cost(strategy):
total_cost = 0
current_year = 0
machine_age = 0
initial_machine_bought = False
for decision in strategy:
if decision == 'new':
if machine_age > 0:
total_cost += salvage_values[machine_age]
total_cost += initial_costs[current_year]
machine_age = 0
initial_machine_bought = True
else:
total_cost += maintenance_costs[machine_age]
machine_age += 1
current_year += 1
if not initial_machine_bought or (machine_age > 0 and current_year == 4):
total_cost += salvage_values[machine_age - 1]
return total_cost
strategies = [
['new', 'new', 'new'],
['new', 'continue', 'new'],
['new', 'continue', 'continue'],
]
min_cost = float('inf')
best_strategy = None
for strategy in strategies:
cost = calculate_cost(strategy)
if cost < min_cost:
min_cost = cost
best_strategy = strategy
print(f"最小总费用为：{min_cost} 万元")
print(f"最优更新策略为：{best_strategy}（其中'new'表示买新机器，'continue'表示继续使用上一年的机器到年末）")
print("3023")
结果
6.5
import numpy as np
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])
max_distances_to_hospital = np.array([np.max(distances[i][distances[i] != np.inf]) for i in range(6)])
hospital_location = np.argmin(max_distances_to_hospital)
print(f"医院应该建在村庄 {chr(65 + hospital_location)} 处，使得最远村庄的人到医院看病所走的路最短。")
school_total_distances = np.sum(distances * students[:, np.newaxis], axis=0)
school_total_distances[np.isinf(school_total_distances)] = np.inf # 将不可达的路径设置为无穷大
school_location = np.argmin(school_total_distances)
print(f"小学应该建在村庄 {chr(65 + school_location)} 处，使得所有学生上学走的总路程最短。")
print("3023")
结果
6.7
import numpy as np
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
a = pd.read_excel(r"ti6_7.xlsx")
b = a.values
s = b[:, 0]
x = b[:, 1]
y = b[:, 2]
num = b[:, 3].astype(float)
ad = b[:, 4:].astype(str)
inl = np.where(num == 1)[0]
in2 = np.where(num == 2)[0]
in3 = np.where(np.isnan(num))[0]
plt.plot(x[inl], y[inl], 'Pk', label='num=1')
for i in inl:
plt.text(x[i] + 10, y[i], s[i])
plt.plot(x[in2], y[in2], '*k', label='num=2')
for i in in2:
plt.text(x[i] + 10, y[i], s[i])
plt.plot(x[in3], y[in3], '.k', label='num=NaN')
for i in in3:
plt.text(x[i] + 10, y[i], s[i])
plt.legend()
plt.show()
G = nx.Graph()
G.add_nodes_from(s)
for i in range(len(s)):
neighbors = [t for t in ad[i] if t != 'nan' and t != '']
for neighbor in neighbors:
try:
j = s.tolist().index(neighbor)
except ValueError:
continue
distance = np.sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) # 计算欧几里得距离
if distance > 0:
G.add_edge(s[i], s[j], weight=distance)
T = nx.minimum_spanning_tree(G, weight='weight')
print('最小生成树的边和权重为:')
for u, v, d in T.edges(data=True):
print(f'{u} - {v}: {d["weight"]}')
pos = dict(zip(s, list(zip(x, y))))
plt.figure()
nx.draw_networkx(T, pos, node_size=180, font_weight='bold', with_labels=True, node_color='w')
plt.show()
if 'L' in G and 'R3' in G:
p = nx.shortest_path(G, 'L', 'R3', weight='weight')
d = nx.shortest_path_length(G, 'L', 'R3', weight='weight')
print('最短路径为:', p)
print('最短距离为:', round(d, 4))
plt.figure()
nx.draw_networkx(G, pos, node_size=180, font_weight='bold', with_labels=True, node_color='w')
path_edges = list(zip(p, p[1:]))
nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', style='dashed', width=4)
plt.show()
else:
print("'L' 或 'R3' 不在图中")
print("3023")
结果
