《Python数学建模算法与应用课件》06第6章 图论模型（1）.pptx

;;图论是近三十年来发展非常活跃的一个数学分支。大量的最优化问题都可以抽象成网络模型结构来加以解释、描述和求解。它在建模时，具有直观、易理解、适应性强等特点，已广泛应用于管理科学、物理学、化学、计算机科学、信息论、控制论、社会科学（心理学、教育学等）以及军事科学等领域。一些实际网络，如运输网、电话网、电力网、计算机局域网等，都可以用图的理论加以描述和分析，并借助于计算机算法直接求解。这一理论与线性规划、整数规划等优化理论和方法相互渗透，促进了图论方法在实际问题建模中的应用。

;;6.1.1图与网络的基本概念

;1.无向图和有向图;2.简单图、完全图、赋权图;3.顶点的度;4.子图与图的连通性;6.1.2图的矩阵表示;1.关联矩阵;2.邻接矩阵;;1.图的生成;#程序文件ex6_3.py

importnetworkxasnx

importpylabasplt

?

G=nx.cubical_graph()#生成一个3正则图

plt.subplot(121)#激活1号子窗口

nx.draw(G,with_labels=True)

plt.subplot(122)

s=[v+str(i)foriinrange(1,9)]

s=dict(zip(range(8),s))#构造顶点标注的字符字典

nx.draw(G,pos=nx.circular_layout(G),labels=s,

node_color=y,node_shape=s,edge_color=b)

plt.show()

;2.数据存储结构;#程序文件ex6_4.py

importnetworkxasnx

importpylabasplt

?

G=nx.Graph()

G.add_node(1)#添加编号为1的一个顶点

G.add_nodes_from([A,B])#从列表中添加多个顶点

G.add_edge(A,B)#添加顶点A和B之间的一条边

G.add_edge(1,2,weight=0.5)#添加顶点1和2之间权重为0.5的一条边

e=[(A,B,0.3),(B,C,0.9),(A,C,0.5),(C,D,1.2)]

G.add_weighted_edges_from(e)#从列表中添加多条赋权边

print(G.adj)#显示图的邻接表的字典数据

print(list(G.adjacency()))#显示图的邻接表的列表数据

;#程序文件ex6_5.py

importnetworkxasnx

importpylabasplt

?

G=nx.DiGraph()

List=[(1,2),(1,3),(2,3),(3,2),(3,5),(4,2),(4,6),

(5,2),(5,4),(6,5)]

G.add_nodes_from(range(1,7))

G.add_edges_from(List)

plt.rc(font,size=16)

pos=nx.shell_layout(G)

nx.draw(G,pos,with_labels=True,font_weight=bold,node_color=y)

W=nx.to_numpy_matrix(G)#从图G导出邻接矩阵

print(W);plt.show();3.图数据的导出;#程序文件ex6_6.py

importnetworkxasnx

importpylabasplt

importnumpyasnp

?

G=nx.Graph()

List=[(1,3,10),(1,4,60),(2,3,5),

(2,4,20),(3,4,1)]

G.add_nodes_from(range(1,5))

G.add_weighted_edges_from(List)

W1=nx.to_numpy_matrix(G)#从图G导出权重邻接矩阵

W2=nx.get_edge_attributes(G,weight)#导出赋权边的字典数据

pos=nx.spring_layout(G)

nx.draw(G,pos,with_labels=True,font_weight=bold)

nx.draw_networkx_edge_labels(G,pos,font_size=13,edge_labels=W2)

print(邻接矩阵为：\n,W1);print(邻接表字典为：\n,G.adj)

print(邻接表列表为：\n,li