Python小白的数学建模课-15.图论基本概念

时间:2022-10-17 18:27:17
  • 图论中所说的图,不是图形图像或地图,而是指由顶点和边所构成的图形结构。
  • 图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。
  • 本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。
  • 『Python小白的数学建模课 @ Youcans』带你从数模小白成为国赛达人。

1. 图论

1.1 图论是什么

图论〔Graph Theory〕以图为研究对象,是离散数学的重要内容。图论不仅与拓扑学、计算机数据结构和算法密切相关,而且正在成为机器学习的关键技术。

图论中所说的图,不是指图形图像(image)或地图(map),而是指由顶点(vertex)和连接顶点的边(edge)所构成的关系结构。

图提供了一种处理关系和交互等抽象概念的更好的方法,它还提供了直观的视觉方式来思考这些概念。

1.2 NetworkX 工具包

NetworkX 是基于 Python 语言的图论与复杂网络工具包,用于创建、操作和研究复杂网络的结构、动力学和功能。

NetworkX 可以以标准和非标准的数据格式描述图与网络,生成图与网络,分析网络结构,构建网络模型,设计网络算法,绘制网络图形。

NetworkX 提供了图形的类、对象、图形生成器、网络生成器、绘图工具,内置了常用的图论和网络分析算法,可以进行图和网络的建模、分析和仿真。

NetworkX 的功能非常强大和庞杂,所涉及内容远远、远远地超出了数学建模的范围,甚至于很难进行系统的概括。本系列结合数学建模的应用需求,来介绍 NetworkX 图论与复杂网络工具包的基本功能和典型算法。

Python小白的数学建模课-15.图论基本概念

NetworkX 的官网和文档


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)

# 顶点(node)的操作
# 向图中添加顶点
G1.add_node(1) # 向 G1 添加顶点 1
G1.add_node(1, name='n1', weight=1.0) # 添加顶点 1,定义 name, weight 属性
G1.add_node(2, date='May-16') # 添加顶点 2,定义 time 属性
G1.add_nodes_from([3, 0, 6], dist=1) # 添加多个顶点,并定义属性
G1.add_nodes_from(range(10, 15)) # 向图 G1 添加顶点 10~14 # 查看顶点和顶点属性
print(G1.nodes()) # 查看顶点列表
# [1, 2, 3, 0, 6, 10, 11, 12, 13, 14]
print(G1._node) # 查看顶点属性
# {1: {'name': 'n1', 'weight': 1.0}, 2: {'date': 'May-16'}, 3: {'dist': 1}, 0: {'dist': 1}, 6: {'dist': 1}, 10: {}, 11: {}, 12: {}, 13: {}, 14: {}} # 从图中删除顶点
G1.remove_node(1) # 删除顶点
G1.remove_nodes_from([1, 11, 13, 14]) # 通过顶点标签的 list 删除多个顶点
print(G1.nodes()) # 查看顶点
# [2, 3, 0, 6, 10, 12] # 顶点列表

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)

# 边(edge)的操作
# 向图中添加边
G1.add_edge(1,5) # 向 G1 添加边,并自动添加图中没有的顶点
G1.add_edge(0,10, weight=2.7) # 向 G1 添加边,并设置边的属性
G1.add_edges_from([(1,2,{'weight':0}), (2,3,{'color':'blue'})]) # 向图中添加边,并设置属性
G1.add_edges_from([(3,6),(1,2),(6,7),(5,10),(0,1)]) # 向图中添加多条边
G1.add_weighted_edges_from([(1,2,3.6),[6,12,0.5]]) # 向图中添加多条赋权边: (node1,node2,weight)
print(G1.nodes()) # 查看顶点
# [2, 3, 0, 6, 10, 12, 1, 5, 7] # 自动添加了图中没有的顶点 # 从图中删除边
G1.remove_edge(0,1) # 从图中删除边 0-1
G1.remove_edges_from([(2,3),(1,5),(6,7)]) # 从图中删除多条边 # 查看 边和边的属性
print(G1.edges) # 查看所有的边
[(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]
print(G1.get_edge_data(1,2)) # 查看指定边的属性
# {'weight': 3.6}
print(G1[1][2]) # 查看指定边的属性
# {'weight': 3.6}
print(G1.edges(data=True)) # 查看所有边的属性
# [(2, 1, {'weight': 3.6}), (3, 6, {}), (0, 10, {'weight': 2.7}), (6, 12, {'weight': 0.5}), (10, 5, {})]

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)) # 返回指定顶点的度
# 2 print('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':节点标签字体颜色,默认黑色

Python小白的数学建模课-15.图论基本概念

3.2 图的分析

NetwotkX 提供了图论函数对图的结构进行分析:

子图

  • 子图是指顶点和边都分别是图 G 的顶点的子集和边的子集的图。
  • subgraph()方法,按顶点从图 G 中抽出子图。例程如前。

连通子图

  • 如果图 G 中的任意两点间相互连通,则 G 是连通图。
  • connected_components()方法,返回连通子图的集合。
G = nx.path_graph(4)
nx.add_path(G, [7, 8, 9])
# 连通子图
listCC = [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)]
maxCC = max(nx.connected_components(G), key=len)
print('Connected components:{}'.format(listCC)) # 所有连通子图
# Connected components:[4, 3]
print('Largest connected components:{}'.format(maxCC)) # 最大连通子图
# Largest connected components:{0, 1, 2, 3}

强连通

  • 如果有向图 G 中的任意两点间相互连通,则称 G 是强连通图。
  • strongly_connected_components()方法,返回所有强连通子图的列表。
# 强连通
G = nx.path_graph(4, create_using=nx.DiGraph())
nx.add_path(G, [3, 8, 1])
# 找出所有的强连通子图
con = nx.strongly_connected_components(G)
print(type(con),list(con))
# <class 'generator'> [{8, 1, 2, 3}, {0}]

弱连通

  • 如果一个有向图 G 的基图是连通图,则有向图 G 是弱连通图。
  • weakly_connected_components()方法,返回所有弱连通子图的列表。
# 弱连通
G = nx.path_graph(4, create_using=nx.DiGraph()) #默认生成节点 0,1,2,3 和有向边 0->1,1->2,2->3
nx.add_path(G, [7, 8, 3]) #生成有向边:7->8->3
con = nx.weakly_connected_components(G)
print(type(con),list(con))
# <class 'generator'> [{0, 1, 2, 3, 7, 8}]

【本节完】

版权声明:

欢迎关注『Python小白的数学建模课 @ Youcans』 原创作品

原创作品,转载必须标注原文链接:(https://www.cnblogs.com/youcans/p/15090653.html)。

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小白的数学建模课-B2.新冠疫情 SI模型

Python小白的数学建模课-B3.新冠疫情 SIS模型

Python小白的数学建模课-B4.新冠疫情 SIR模型

Python小白的数学建模课-B5.新冠疫情 SEIR模型

Python小白的数学建模课-B6.改进 SEIR疫情模型

Python小白的数学建模课-15.图论基本概念的更多相关文章

  1. Python小白的数学建模课-16&period;最短路径算法

    最短路径问题是图论研究中的经典算法问题,用于计算图中一个顶点到另一个顶点的最短路径. 在图论中,最短路径长度与最短路径距离却是不同的概念和问题,经常会被混淆. 求最短路径长度的常用算法是 Dijkst ...

  2. Python小白的数学建模课-19&period;网络流优化问题

    流在生活中十分常见,例如交通系统中的人流.车流.物流,供水管网中的水流,金融系统中的现金流,网络中的信息流.网络流优化问题是基本的网络优化问题,应用非常广泛. 网络流优化问题最重要的指标是边的成本和容 ...

  3. Python小白的数学建模课-17&period;条件最短路径

    条件最短路径问题,指带有约束条件.限制条件的最短路径问题.例如: 顶点约束,包括必经点或禁止点的限制: 边的约束,包括必经路段.禁行路段和单向路段:无权路径长度的限制,如要求经过几步或不超过几步到达终 ...

  4. Python小白的数学建模课-18&period;最小生成树问题

    最小生成树(MST)是图论中的基本问题,具有广泛的实际应用,在数学建模中也经常出现. 路线设计.道路规划.官网布局.公交路线.网络设计,都可以转化为最小生成树问题,如要求总线路长度最短.材料最少.成本 ...

  5. Python小白的数学建模课-07 选址问题

    选址问题是要选择设施位置使目标达到最优,是数模竞赛中的常见题型. 小白不一定要掌握所有的选址问题,但要能判断是哪一类问题,用哪个模型. 进一步学习 PuLP工具包中处理复杂问题的字典格式快捷建模方法. ...

  6. Python小白的数学建模课-04&period;整数规划

    整数规划与线性规划的差别只是变量的整数约束. 问题区别一点点,难度相差千万里. 选择简单通用的编程方案,让求解器去处理吧. 『Python小白的数学建模课 @ Youcans』带你从数模小白成为国赛达 ...

  7. Python小白的数学建模课-A1&period;2021年数维杯C题(运动会优化比赛模式探索)探讨

    Python小白的数学建模课 A1-2021年数维杯C题(运动会优化比赛模式探索)探讨. 运动会优化比赛模式问题,是公平分配问题 『Python小白的数学建模课 @ Youcans』带你从数模小白成为 ...

  8. Python小白的数学建模课-03&period;线性规划

    线性规划是很多数模培训讲的第一个算法,算法很简单,思想很深刻. 要通过线性规划问题,理解如何学习数学建模.如何选择编程算法. 『Python小白的数学建模课 @ Youcans』带你从数模小白成为国赛 ...

  9. Python小白的数学建模课-A1&period;国赛赛题类型分析

    分析赛题类型,才能有的放矢. 评论区留下邮箱地址,送你国奖论文分析 『Python小白的数学建模课 @ Youcans』 带你从数模小白成为国赛达人. 1. 数模竞赛国赛 A题类型分析 年份 题目 要 ...

随机推荐

  1. Mybatis - 动态sql

    learn from:http://www.mybatis.org/mybatis-3/dynamic-sql.html mybatis支持动态拼接sql语句.主要有: if choose (when ...

  2. 如何安装、配置Apache

    Apache的安装流程网上版本很多,但很多版本有错误,或者缺漏,如果初学者按照那样安装的话会遇到各种各样的问题.我整理了自己安装.配置Apache的过程,亲测有效,分享给大家. 基本过程如下: Dow ...

  3. 2016 Al-Baath University Training Camp Contest-1 E

    Description ACM-SCPC-2017 is approaching every university is trying to do its best in order to be th ...

  4. HDU 1496 Train Problem I 火车问题1(桟,水)

    题意: 给出两个串,串中的数字i 代表编号为i的火车进入车站的顺序,车站如桟一样,先进后出.第二个串是火车出站的顺序,问若按照第一个串那样进站,是否有可能如第二个串一样的出站顺序?火车顶多9辆,即1- ...

  5. JAVA GUI学习 - 窗体背景图片设置方法:重写paintComponent&lpar;Graphics g&rpar;方法

    public class BackgroundImage extends JFrame { public BackgroundImage() { this.setTitle("窗体背景图片设 ...

  6. browser-sync &plus; http-proxy-middleware 配置代理跨域

    写代理js文件下面是文件内容 /** * Module dependencies. */ var browserSync = require('browser-sync').create() var ...

  7. 《Java开发学习大纲文档》V7&period;0

    <Java开发学习大纲文档>V7.0简介: 本文档是根据企业开发所需要掌握的知识点大纲进行总结汇编,是Java开发工程师必备知识体系,系统化学习针对性非常强,逻辑分析能力非常清晰;技术方面 ...

  8. Swift5 语言指南&lpar;十&rpar; 枚举

    一个枚举定义了一个通用型的一组相关的值,使你在你的代码中的一个类型安全的方式这些值来工作. 如果您熟悉C,您将知道C枚举将相关名称分配给一组整数值.Swift中的枚举更灵活,并且不必为枚举的每个案例提 ...

  9. spring boot 打jar包

    想必大家经常会出现以下报错信息 java.util.concurrent.ExecutionException: org.apache.catalina.LifecycleException: Fai ...

  10. git Alias 设置

    git Alias 设置 Git 使用比較多的话能够设置一些命令的 Alias ,简单的说就是用简写取代整个完整的命令. 如co 代表 checkout. Mac下,到根文件夹 cd ~ 然后 vi ...