Python小白的数学建模课-15.图论的基本概念
- 圖論中所說的圖,不是圖形圖像或地圖,而是指由頂點和邊所構成的圖形結構。
- 圖論不僅與拓撲學、計算機數據結構和算法密切相關,而且正在成為機器學習的關鍵技術。
- 本系列結合數學建模的應用需求,來介紹 NetworkX 圖論與復雜網絡工具包的基本功能和典型算法。
- 『Python小白的數學建模課 @ Youcans』帶你從數模小白成為國賽達人。
1. 圖論
1.1 圖論是什么
圖論〔Graph Theory〕以圖為研究對象,是離散數學的重要內容。圖論不僅與拓撲學、計算機數據結構和算法密切相關,而且正在成為機器學習的關鍵技術。
圖論中所說的圖,不是指圖形圖像(image)或地圖(map),而是指由頂點(vertex)和連接頂點的邊(edge)所構成的關系結構。
圖提供了一種處理關系和交互等抽象概念的更好的方法,它還提供了直觀的視覺方式來思考這些概念。
1.2 NetworkX 工具包
NetworkX 是基于 Python 語言的圖論與復雜網絡工具包,用于創建、操作和研究復雜網絡的結構、動力學和功能。
NetworkX 可以以標準和非標準的數據格式描述圖與網絡,生成圖與網絡,分析網絡結構,構建網絡模型,設計網絡算法,繪制網絡圖形。
NetworkX 提供了圖形的類、對象、圖形生成器、網絡生成器、繪圖工具,內置了常用的圖論和網絡分析算法,可以進行圖和網絡的建模、分析和仿真。
NetworkX 的功能非常強大和龐雜,所涉及內容遠遠、遠遠地超出了數學建模的范圍,甚至于很難進行系統的概括。本系列結合數學建模的應用需求,來介紹 NetworkX 圖論與復雜網絡工具包的基本功能和典型算法。
NetworkX 的官網和文檔
- 官網地址:https://networkx.org/
- 官方文檔:https://networkx.org/documentation/stable/
- pdf 文檔:https://networkx.org/documentation/stable/_downloads/networkx_reference.pdf
歡迎關注 『Python小白的數學建模課 @ Youcans』 系列,持續更新
Python小白的數學建模課-01.新手必讀
Python小白的數學建模課-02.數據導入
Python小白的數學建模課-03.線性規劃
Python小白的數學建模課-04.整數規劃
Python小白的數學建模課-05.0-1規劃
Python小白的數學建模課-06.固定費用問題
Python小白的數學建模課-07.選址問題
Python小白的數學建模課-09.微分方程模型
Python小白的數學建模課-10.微分方程邊值問題
Python小白的數學建模課-12.非線性規劃
Python小白的數學建模課-15.圖論的基本概念
Python小白的數學建模課-16.最短路徑算法
Python小白的數學建模課-17.條件最短路徑算法
2、圖、頂點和邊的創建與基本操作
圖由頂點和連接頂點的邊構成,但與頂點的位置、邊的曲直長短無關。
Networkx 支持創建簡單無向圖、有向圖和多重圖;內置許多標準的圖論算法,節點可為任意數據;支持任意的邊值維度,功能豐富,簡單易用。
2.1 圖的基本概念
- 圖(Graph):圖是由若干頂點和連接頂點的邊所構成關系結構。
- 頂點(Node):圖中的點稱為頂點,也稱節點。
- 邊(Edge):頂點之間的連線,稱為邊。
- 平行邊(Parallel edge):起點相同、終點也相同的兩條邊稱為平行邊。
- 循環(Cycle):起點和終點重合的邊稱為循環。
- 有向圖(Digraph):圖中的每條邊都帶有方向,稱為有向圖。
- 無向圖(Undirected graph):圖中的每條邊都沒有方向,稱為無向圖。
- 賦權圖(Weighted graph):圖中的每條邊都有一個或多個對應的參數,稱為賦權圖。該參數稱為這條邊的權,權可以用來表示兩點間的距離、時間、費用。
- 度(Degree):與頂點相連的邊的數量,稱為該頂點的度。
2.2 圖、頂點和邊的操作
Networkx很容易創建圖、向圖中添加頂點和邊、從圖中刪除頂點和邊,也可以查看、刪除頂點和邊的屬性。
2.2.1 圖的創建
Graph() 類、DiGraph() 類、MultiGraph() 類和 MultiDiGraph() 類分別用來創建:無向圖、有向圖、多圖和有向多圖。定義和例程如下:
class Graph(incoming_graph_data=None, **attr)
import networkx as nx # 導入 NetworkX 工具包# 創建 圖 G1 = nx.Graph() # 創建:空的 無向圖 G2 = nx.DiGraph() #創建:空的 有向圖 G3 = nx.MultiGraph() #創建:空的 多圖 G4 = nx.MultiDiGraph() #創建:空的 有向多圖2.2.2 頂點的添加、刪除和查看
圖的每個頂點都有唯一的標簽屬性(label),可以用整數或字符類型表示,頂點還可以自定義任意屬性。
頂點的常用操作:添加頂點,刪除頂點,定義頂點屬性,查看頂點和頂點屬性。定義和例程如下:
Graph.add_node(node_for_adding, **attr)
Graph.add_nodes_from(nodes_for_adding, **attr)
Graph.remove_node(n)
Graph.remove_nodes_from(nodes)
2.2.3 邊的添加、刪除和查看
邊是兩個頂點之間的連接,在 NetworkX 中 邊是由對應頂點的名字的元組組成 e=(node1,node2)。邊可以設置權重、關系等屬性。
邊的常用操作:添加邊,刪除邊,定義邊的屬性,查看邊和邊的屬性。向圖中添加邊時,如果邊的頂點是圖中不存在的,則自動向圖中添加該頂點。
Graph.add_edge(u_of_edge, v_of_edge, **attr)
Graph.add_edges_from(ebunch_to_add, **attr)
Graph.add_weighted_edges_from(ebunch_to_add, weight=‘weight’, **attr)
2.2.4 查看圖、頂點和邊的信息
# 查看圖、頂點和邊的信息 print(G1.nodes) # 返回所有的頂點 [node1,...] # [2, 3, 0, 6, 10, 12, 1, 5, 7] print(G1.edges) # 返回所有的邊 [(node1,node2),...] # [(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)] print(G1.degree) # 返回各頂點的度 [(node1,degree1),...] # [(2, 1), (3, 1), (0, 1), (6, 2), (10, 2), (12, 1), (1, 1), (5, 1), (7, 0)] print(G1.number_of_nodes()) # 返回頂點的數量 # 9 print(G1.number_of_edges()) # 返回邊的數量 # 5 print(G1[10]) # 返回與指定頂點相鄰的所有頂點的屬性 # {0: {'weight': 2.7}, 5: {}} print(G1.adj[10]) # 返回與指定頂點相鄰的所有頂點的屬性 # {0: {'weight': 2.7}, 5: {}} print(G1[1][2]) # 返回指定邊的屬性 # {'weight': 3.6} print(G1.adj[1][2]) # 返回指定邊的屬性 # {'weight': 3.6} print(G1.degree(10)) # 返回指定頂點的度 # 2print('nx.info:',nx.info(G1)) # 返回圖的基本信息 print('nx.degree:',nx.degree(G1)) # 返回圖中各頂點的度 print('nx.density:',nx.degree_histogram(G1)) # 返回圖中度的分布 print('nx.pagerank:',nx.pagerank(G1)) # 返回圖中各頂點的頻率分布2.3 圖的屬性和方法
圖的方法
| G.has_node(n) | 當圖 G 中包括頂點 n 時返回 True |
| G.has_edge(u, v) | 當圖 G 中包括邊 (u,v) 時返回 True |
| G.number_of_nodes() | 返回 圖 G 中的頂點的數量 |
| G.number_of_edges() | 返回 圖 G 中的邊的數量 |
| G.number_of_selfloops() | 返回 圖 G 中的自循環邊的數量 |
| G.degree([nbunch, weight]) | 返回 圖 G 中的全部頂點或指定頂點的度 |
| G.selfloop_edges([data, default]) | 返回 圖 G 中的全部的自循環邊 |
| G.subgraph([nodes]) | 從圖 G1中抽取頂點[nodes]及對應邊構成的子圖 |
| union(G1,G2) | 合并圖 G1、G2 |
| nx.info(G) | 返回圖的基本信息 |
| nx.degree(G) | 返回圖中各頂點的度 |
| nx.degree_histogram(G) | 返回圖中度的分布 |
| nx.pagerank(G) | 返回圖中各頂點的頻率分布 |
| nx.add_star(G,[nodes],**attr) | 向圖 G 添加星形網絡 |
| nx.add_path(G,[nodes],**attr) | 向圖 G 添加一條路徑 |
| nx.add_cycle(G,[nodes],**attr) | 向圖 G 添加閉合路徑 |
例程:
G1.clear() # 清空圖G1 nx.add_star(G1, [1, 2, 3, 4, 5], weight=1) # 添加星形網絡:以第一個頂點為中心 # [(1, 2), (1, 3), (1, 4), (1, 5)] nx.add_path(G1, [5, 6, 8, 9, 10], weight=2) # 添加路徑:順序連接 n個節點的 n-1條邊 # [(5, 6), (6, 8), (8, 9), (9, 10)] nx.add_cycle(G1, [7, 8, 9, 10, 12], weight=3) # 添加閉合回路:循環連接 n個節點的 n 條邊 # [(7, 8), (7, 12), (8, 9), (9, 10), (10, 12)] print(G1.nodes) # 返回所有的頂點 [node1,...] nx.draw_networkx(G1) plt.show()G2 = G1.subgraph([1, 2, 3, 8, 9, 10]) G3 = G1.subgraph([4, 5, 6, 7]) G = nx.union(G2, G3) print(G.nodes) # 返回所有的頂點 [node1,...] # [1, 2, 3, 8, 9, 10, 4, 5, 6, 7]3、圖的繪制與分析
3.1 圖的繪制
可視化是圖論和網絡問題中很重要的內容。NetworkX 在 Matplotlib、Graphviz 等圖形工具包的基礎上,提供了豐富的繪圖功能。
本系列擬對圖和網絡的可視化作一個專題,在此只簡單介紹基于 Matplotlib 的基本繪圖函數。基本繪圖函數使用字典提供的位置將節點放置在散點圖上,或者使用布局函數計算位置。
| draw(G[,pos,ax]) | 基于 Matplotlib 繪制 圖 G |
| draw_networkx(G[, pos, arrows, with_labels]) | 基于 Matplotlib 繪制 圖 G |
| draw_networkx_nodes(G, pos[, nodelist, . . . ]) | 繪制圖 G 的頂點 |
| draw_networkx_edges(G, pos[, edgelist, . . . ]) | 繪制圖 G 的邊 |
| draw_networkx_labels(G, pos[, labels, . . . ]) | 繪制頂點的標簽 |
| draw_networkx_edge_labels(G, pos[, . . . ]) | 繪制邊的標簽 |
其中,nx.draw() 和 nx.draw_networkx() 是最基本的繪圖函數,并可以通過自定義函數屬性或其它繪圖函數設置不同的繪圖要求。
draw(G, pos=None, ax=None, **kwds)
draw_networkx(G, pos=None, arrows=True, with_labels=True, **kwds)
常用的屬性定義如下:
- ‘node_size’:指定節點的尺寸大小,默認300
- ‘node_color’:指定節點的顏色,默認紅色
- ‘node_shape’:節點的形狀,默認圓形
- '‘alpha’:透明度,默認1.0,不透明
- ‘width’:邊的寬度,默認1.0
- ‘edge_color’:邊的顏色,默認黑色
- ‘style’:邊的樣式,可選 ‘solid’、‘dashed’、‘dotted’、‘dashdot’
- ‘with_labels’:節點是否帶標簽,默認True
- ‘font_size’:節點標簽字體大小,默認12
- ‘font_color’:節點標簽字體顏色,默認黑色
3.2 圖的分析
NetwotkX 提供了圖論函數對圖的結構進行分析:
子圖
- 子圖是指頂點和邊都分別是圖 G 的頂點的子集和邊的子集的圖。
- subgraph()方法,按頂點從圖 G 中抽出子圖。例程如前。
連通子圖
- 如果圖 G 中的任意兩點間相互連通,則 G 是連通圖。
- connected_components()方法,返回連通子圖的集合。
強連通
- 如果有向圖 G 中的任意兩點間相互連通,則稱 G 是強連通圖。
- strongly_connected_components()方法,返回所有強連通子圖的列表。
弱連通
- 如果一個有向圖 G 的基圖是連通圖,則有向圖 G 是弱連通圖。
- weakly_connected_components()方法,返回所有弱連通子圖的列表。
【本節完】
版權聲明:
歡迎關注『Python小白的數學建模課 @ Youcans』 原創作品
原創作品,轉載必須標注原文鏈接:(https://blog.csdn.net/youcans/article/details/118497645)。
Copyright 2021 Youcans, XUPT
Crated:2021-07-05
歡迎關注 『Python小白的數學建模課 @ Youcans』 系列,持續更新
Python小白的數學建模課-01.新手必讀
Python小白的數學建模課-02.數據導入
Python小白的數學建模課-03.線性規劃
Python小白的數學建模課-04.整數規劃
Python小白的數學建模課-05.0-1規劃
Python小白的數學建模課-06.固定費用問題
Python小白的數學建模課-07.選址問題
Python小白的數學建模課-09.微分方程模型
Python小白的數學建模課-10.微分方程邊值問題
Python小白的數學建模課-12.非線性規劃
Python小白的數學建模課-15.圖論的基本概念
Python小白的數學建模課-16.最短路徑算法
Python小白的數學建模課-17.條件最短路徑算法
Python小白的數學建模課-18.最小生成樹問題
Python小白的數學建模課-19.網絡流優化問題
Python小白的數學建模課-20.網絡流優化案例
Python小白的數學建模課-21.關鍵路徑法
Python小白的數學建模課-22.插值方法
Python小白的數學建模課-A1.國賽賽題類型分析
Python小白的數學建模課-A2.2021年數維杯C題探討
Python小白的數學建模課-A3.12個新冠疫情數模競賽賽題及短評
Python小白的數學建模課-B2. 新冠疫情 SI模型
Python小白的數學建模課-B3. 新冠疫情 SIS模型
Python小白的數學建模課-B4. 新冠疫情 SIR模型
Python小白的數學建模課-B5. 新冠疫情 SEIR模型
Python小白的數學建模課-B6. 新冠疫情 SEIR改進模型
總結
以上是生活随笔為你收集整理的Python小白的数学建模课-15.图论的基本概念的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: matlab 多重循环在最外层加断点_循
- 下一篇: 【OpenCV 例程200篇】54. O