圖的基礎(chǔ)理論及networkx簡介

圖的基本概念

1. 無向圖和有向圖
2. 簡單圖和完全圖：重邊、環(huán)、孤立點
3. 賦權(quán)圖/網(wǎng)絡(luò)
4. 頂點的度
5. 子圖與生成子圖
6. 路與回路、跡、path、圈
7. 連通圖與非連通圖

圖的表示及Networkx簡介

圖的表示

考慮簡單圖

1. 關(guān)聯(lián)矩陣表示
   

2. 鄰接矩陣表示
   
   對于賦權(quán)圖而言，鄰接矩陣中的數(shù)值改為對應(yīng)邊的權(quán)值就得到對應(yīng)的無向/有向賦權(quán)圖

NetworkX簡介

python語言
圖論與復(fù)雜網(wǎng)絡(luò)建模工具
內(nèi)置常用圖與復(fù)雜網(wǎng)絡(luò)分析算法

繪圖布局
圖形布局共五種

1. circular_layout：頂點在一個圓環(huán)上均勻分布；
2. random_layout：頂點隨機分布；
3. shell_layout：頂點在同心圓上分布；
4. spring_layout： 用Fruchterman-Reingold算法排列頂點；
5. spectral_layout：根據(jù)圖的拉普拉斯特征向量排列頂點

最短路算法及其Python實現(xiàn)

Dijkstra（迪克斯特拉）標號算法和Floyd（弗洛伊德）算法
Dijkstra標號算法只適用于邊權(quán)是非負的情形
最短路問題也可以歸結(jié)為一個0-1整數(shù)規(guī)劃模型

固定起點到其余各點的最短路算法

Dijkstra（迪克斯特拉）標號算法
賦權(quán)圖$G(V,E,W)$，其中頂點集 V = { v 1 , . . . , v n } V=\{v_1, ..., v_n\} V={v1?,...,vn?}， 邊集$E$，鄰接矩陣$W=(w_{ij}{)}_{nxn}$，且$w_{ij}$滿足

記號確定
$d(u_0,v_0)$ ：頂點$u_0$到頂點$v_0$的最短距離
$l(v)$：起點$u_0$到$v$的當前路長度
$z(v)$：頂點$v$的父頂點標號
$S_i$：具有永久標號的頂點集

每對頂點間的最短路算法

Floyd（弗洛伊德）算法
動態(tài)規(guī)劃算法，遞推產(chǎn)生矩陣序列$A_1,A_2,...,A_k,...,A_n$，矩陣$A_k=(a_k(i,j))nxn$，第$i$行第$j$列元素$a_k(i,j)$表示從頂點$v_i$到頂點$v_j$路徑上頂點數(shù)不大于$k$的最短路徑長度
迭代公式

networkx求所有頂點對之間最短路徑的函數(shù)為
shortest_path(G, source=None, target=None, weight=None, method='dijkstra')，返回值是可迭代類型，其中method可以取值dijkstra，bellman-ford

最短路應(yīng)用

設(shè)備更新問題


轉(zhuǎn)化為最短路問題
賦權(quán)有向圖$D=(V,A,W)$，頂點集 V = { v 1 , v 2 , . . . , v 5 } V=\{v_1, v_2, ..., v_5\} V={v1?,v2?,...,v5?}，$v_i$（$i=1,2,3,4$）表示第$i$年年初，$v_5$表示第4年年末，A為邊集，W為鄰接矩陣，$w_{ij}$為第$i$年年初到第$j$年年初/第$j?1$年年末所支付的費用，計算公式為
$$w_{ij}=p_i+\sum _i^{j?1}{a}_k?r_j$$
說明：$p_i$為第$i$年年初機器的購置費用，$a_k$為第$k$年的機器維護費用，$r_i$為第$i$年末機器的出售價格
根據(jù)這個公式計算得到鄰接矩陣$W$，并且原問題轉(zhuǎn)化為求解$v_1$到$v_5$的費用最短路

結(jié)果

重心問題/選址問題

問題轉(zhuǎn)化：求出各個頂點對之間的最短距離，然后得到某一頂點到其他各個頂點的（最短重量·距離）和最小，這個頂點即為所求

計算結(jié)果展示

最小生成樹算法及其networkx實現(xiàn)

基本概念

1. 樹：連通的五圈圖
2. 樹的判定定理：n個頂點m條邊的圖
3. 生成樹、最小生成樹

最小生成樹算法

Kruskal算法和Prim算法
Kruskal算法
貪心，每次選擇權(quán)值最小的邊加入子圖T，并保證不形成環(huán)，直到子圖中包含$n?1$條邊為止
Prim算法
使用兩個集合$P$和$Q$，從任意$p\in P$，$v\in V?P$，選擇最小權(quán)值的邊$pv$，將$v$加入$P$，$pv$加入Q，直到$P=V$為止
說明：對比Kruskal算法和Prim算法，Kruskal算法是顯式地說明了不能在生成子圖中出現(xiàn)環(huán)，Prim算法則是通過設(shè)定選定新邊的一個頂點在$P$集合，一個頂點在$V?P$集合這樣隱式保證的

NetworkX提供接口
T=minimum_spanning_tree(G, weight='weight', algorithm='kruskal')
G為輸入圖
algorithm的取值有三種字符串：‘kruskal’，‘prim’，或’boruvka’，缺省值為’kruskal’
返回值T為所求得的最小生成樹的可迭代對象

示例

最小生成樹應(yīng)用

說明：從這個題看出最小生成樹和最短路算法的區(qū)別，最短路在找的是各個節(jié)點到某個節(jié)點的最短，而最小生成樹在找的是一條通過全部節(jié)點的最短路

結(jié)果

匹配問題

問題轉(zhuǎn)化：賦權(quán)圖$G=(V,E,\hat{W})$ ，頂點集 V = { v 1 , v 2 , . . . , v 10 } V=\{v_1, v_2, ..., v_{10}\} V={v1?,v2?,...,v10?}，$v_1,v_2,...,v_5$表示5個人， $v_6,v_7,v_8,v_9,v_{10}$表示5項工作，鄰接矩陣$\hat{W}$滿足

代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-796667.html

import numpy as np
import networkx as nx
from networkx.algorithms.matching import max_weight_matching
a=np.array([[3,5,5,4,1],[2,2,0,2,2],[2,4,4,1,0],
            [0,2,2,1,0],[1,2,1,3,3]])
b=np.zeros((10,10)); b[0:5,5:]=a; G=nx.Graph(b)
#返回值為（人員，工作）的集合
s0=max_weight_matching(G)  
s=[sorted(w) for w in s0]
L1=[x[0] for x in s]; L1=np.array(L1)+1  #人員編號
L2=[x[1] for x in s]; L2=np.array(L2)-4  #工作編號
c=a[L1-1,L2-1]  #提取對應(yīng)的效益
d=c.sum()  #計算總的效益
print("工作分配對應(yīng)關(guān)系為：\n人員編號：",L1)
print("工作編號：", L2); print("總的效益為：",d)

最大流最小費用問題

網(wǎng)絡(luò)流問題——如何安排使流量最大，即最大流問題，如公路系統(tǒng)中有車輛流、物資調(diào)配系統(tǒng)中有物資流、金融系統(tǒng)中有現(xiàn)金流等

基本概念

1. 有向圖$D(V,A)$、源點$v_s$、匯點$v_t$、弧容量$c(v_i,v_j)\ge 0$ 、網(wǎng)絡(luò)流$f(v_i,v_j)$
2. 可行流的條件
3. 增廣路

最大流問題可寫為這樣一個線性規(guī)劃問題

Ford-Fulkerson算法尋求最大流

使用NetworkX求解網(wǎng)絡(luò)最大流

最小費用流問題

標號說明
$f_{ij}$為弧$(v_i,v_j)$上的流量，$b_{ij}$為弧$(v_i,v_j)$上的單位費用，$c_{ij}$為弧$(v_i,v_j)$上的容量，問題轉(zhuǎn)化為下面的線性規(guī)劃問題

當$v=v_{max}$時，問題有解；當$v>v_{max}$時，問題無解

使用NetworkX求解問題

代碼：

import numpy as np
import networkx as nx
L=[(1,2,5,3),(1,3,3,6),(2,4,2,8),(3,2,1,2),(3,5,4,2),
   (4,3,1,1),(4,5,3,4),(4,6,2,10),(5,6,5,2)]
G=nx.DiGraph()
for k in range(len(L)):
    G.add_edge(L[k][0]-1,L[k][1]-1, capacity=L[k][2], weight=L[k][3])
mincostFlow=nx.max_flow_min_cost(G,0,5)
print("所求流為：",mincostFlow)
mincost=nx.cost_of_flow(G, mincostFlow)
print("最小費用為：", mincost)
flow_mat=np.zeros((6,6),dtype=int)
for i,adj in mincostFlow.items():
    for j,f in adj.items():
        flow_mat[i,j]=f
print("最小費用最大流的鄰接矩陣為：\n",flow_mat)

PageRank算法

引文分析思想
當網(wǎng)頁甲有一個鏈接指向網(wǎng)頁乙，就認為乙獲得了甲對它貢獻的分值，該值的多少取決于網(wǎng)頁甲本身的重要程度，即網(wǎng)頁甲的重要性越大，網(wǎng)頁乙獲得的貢獻值就越高。
由于網(wǎng)絡(luò)中網(wǎng)頁鏈接的相互指向，pagerank分值計算為一個迭代過程，最終網(wǎng)頁根據(jù)所得分值進行排序

假設(shè)
我們在上網(wǎng)時瀏覽頁面并選擇下一個頁面的過程，與過去瀏覽過哪些頁面無關(guān)，而僅依賴于當前所在的頁面。
這一選擇過程可以認為是一個有限狀態(tài)、離散時間的隨機過程，其狀態(tài)轉(zhuǎn)移規(guī)律用Markov鏈描述

說明：$a_{ij}$表示從頁面$i$轉(zhuǎn)移到頁面$j$的概率，$\frac{1?d}{N}$為隨機跳轉(zhuǎn)時到頁面$j$的概率，$d\frac{b_{ij}}{r_i}$為根據(jù)連接進行跳轉(zhuǎn)到頁面$j$的概率

再根據(jù)正則Markov的平穩(wěn)分布，得到各個網(wǎng)頁被訪問的概率分布，這個概率就被定義為各個網(wǎng)頁的PageRank值

使用NetworkX求解

復(fù)雜網(wǎng)絡(luò)簡介

重點關(guān)注復(fù)雜網(wǎng)絡(luò)的統(tǒng)計性質(zhì)，并使用NetworkX計算

復(fù)雜網(wǎng)絡(luò)概況

復(fù)雜網(wǎng)絡(luò)：具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質(zhì)的網(wǎng)絡(luò)
特征：結(jié)構(gòu)復(fù)雜、網(wǎng)絡(luò)進化、連接多樣性、動力學(xué)復(fù)雜性、節(jié)點多樣性
研究內(nèi)容：網(wǎng)絡(luò)的幾何性質(zhì)，網(wǎng)絡(luò)的形成機制，網(wǎng)絡(luò)演化的統(tǒng)計規(guī)律，網(wǎng)絡(luò)上的模型性質(zhì)，以及網(wǎng)絡(luò)的結(jié)構(gòu)穩(wěn)定性，網(wǎng)絡(luò)的演化動力學(xué)機制等問題
基本測度：度（degree）及其分布特征，度的相關(guān)性，集聚程度及其分布特征，最短距離及其分布特征，介數(shù)(betweenness)及其分布特征，連通集團的規(guī)模分布

1. 節(jié)點的度和度分布：度分布一般用直方圖展示，$A^2$的對角元素$a_{ii}^2$即為節(jié)點$v_i$的度，平均度$<k>=tr(A^2)/N$
2. 平均路徑長度，網(wǎng)絡(luò)直徑
3. 聚類系數(shù)

代碼：

import numpy as np
import networkx as nx
L=[(1,2),(1,3),(2,3),(2,4),(2,5),(3,5),
   (4,5),(4,6)]
G=nx.Graph()   #構(gòu)造無向圖
G.add_nodes_from(range(1,7))  #添加頂點集
G.add_edges_from(L)
D=nx.diameter(G)  #求網(wǎng)絡(luò)直徑
LH=nx.average_shortest_path_length(G) #求平均路徑長度
Ci=nx.clustering(G)   #求各頂點的聚類系數(shù)
C=nx.average_clustering(G)  #求整個網(wǎng)絡(luò)的聚類系數(shù)
print("網(wǎng)絡(luò)直徑為：",D,"\n平均路徑長度為：",LH)
print("各頂點的聚類系數(shù)為：")
for index,value in enumerate(Ci.values()):
    print("(頂點v{:d}: {:.4f})；".format(index+1,value),end=' ')
print("\n整個網(wǎng)絡(luò)的聚類系數(shù)為：{:.4f}".format(C))

到了這里，關(guān)于【數(shù)學(xué)建?！繄D論模型的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！