【数学建模】图论模型

文章目录

  • 图的基础理论及networkx简介
    • 图的基本概念
    • 图的表示及Networkx简介
      • 图的表示
      • NetworkX简介
  • 最短路算法及其Python实现
    • 固定起点到其余各点的最短路算法
    • 每对顶点间的最短路算法
      • 最短路应用
  • 最小生成树算法及其networkx实现
    • 基本概念
    • 最小生成树算法
    • 最小生成树应用
  • 匹配问题
  • 最大流最小费用问题
    • 基本概念
    • 最小费用流问题
  • PageRank算法
  • 复杂网络简介
    • 复杂网络概况

图的基础理论及networkx简介

图的基本概念

  1. 无向图和有向图
  2. 简单图和完全图:重边、环、孤立点
  3. 赋权图/网络
  4. 顶点的度
  5. 子图与生成子图
  6. 路与回路、迹、path、圈
  7. 连通图与非连通图

图的表示及Networkx简介

图的表示

考虑简单图

  1. 关联矩阵表示
    image.png

  2. 邻接矩阵表示
    image.png
    对于赋权图而言,邻接矩阵中的数值改为对应边的权值就得到对应的无向/有向赋权图

NetworkX简介

python语言
图论与复杂网络建模工具
内置常用图与复杂网络分析算法

绘图布局
图形布局共五种

  1. circular_layout:顶点在一个圆环上均匀分布;
  2. random_layout:顶点随机分布;
  3. shell_layout:顶点在同心圆上分布;
  4. spring_layout: 用Fruchterman-Reingold算法排列顶点;
  5. spectral_layout:根据图的拉普拉斯特征向量排列顶点

最短路算法及其Python实现

Dijkstra(迪克斯特拉)标号算法和Floyd(弗洛伊德)算法
Dijkstra标号算法只适用于边权是非负的情形
最短路问题也可以归结为一个0-1整数规划模型

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

Dijkstra(迪克斯特拉)标号算法
赋权图 G ( V , E , W ) G(V,E,W) G(V,E,W),其中顶点集 V = { v 1 , . . . , v n } V=\{v_1, ..., v_n\} V={v1,...,vn}, 边集 E E E,邻接矩阵 W = ( w i j ) n x n W=(w_{ij})_{n x n} W=(wij)nxn,且 w i j w_{ij} wij满足
image.png
记号确定
d ( u 0 , v 0 ) d(u_0, v_0) d(u0,v0) :顶点 u 0 u_0 u0到顶点 v 0 v_0 v0的最短距离
l ( v ) l(v) l(v):起点 u 0 u_0 u0 v v v的当前路长度
z ( v ) z(v) z(v):顶点 v v v的父顶点标号
S i S_i Si:具有永久标号的顶点集

每对顶点间的最短路算法

Floyd(弗洛伊德)算法
动态规划算法,递推产生矩阵序列 A 1 , A 2 , . . . , A k , . . . , A n A_1, A_2, ..., A_k, ..., A_n A1,A2,...,Ak,...,An,矩阵 A k = ( a k ( i , j ) ) n x n A_k=(a_k(i,j))nxn Ak=(ak(i,j))nxn,第 i i i行第 j j j列元素 a k ( i , j ) a_k(i,j) ak(i,j)表示从顶点 v i v_i vi到顶点 v j v_j vj路径上顶点数不大于 k k k的最短路径长度
迭代公式
image.png

networkx求所有顶点对之间最短路径的函数为
shortest_path(G, source=None, target=None, weight=None, method='dijkstra'),返回值是可迭代类型,其中method可以取值dijkstrabellman-ford

最短路应用

设备更新问题
image.png
image.png
转化为最短路问题
赋权有向图 D = ( V , A , W ) D=(V, A, W) D=(V,A,W),顶点集 V = { v 1 , v 2 , . . . , v 5 } V=\{v_1, v_2, ..., v_5\} V={v1,v2,...,v5} v i v_i vi i = 1 , 2 , 3 , 4 i=1, 2, 3, 4 i=1,2,3,4)表示第 i i i年年初, v 5 v_5 v5表示第4年年末,A为边集,W为邻接矩阵, w i j w_{ij} wij为第 i i i年年初到第 j j j年年初/第 j − 1 j-1 j1年年末所支付的费用,计算公式为
w i j = p i + ∑ i j − 1 a k − r j w_{ij} = p_i+\sum_i^{j-1}a_k-r_j wij=pi+ij1akrj
说明: p i p_i pi为第 i i i年年初机器的购置费用, a k a_k ak为第 k k k年的机器维护费用, r i r_i ri为第 i i i年末机器的出售价格
根据这个公式计算得到邻接矩阵 W W W,并且原问题转化为求解 v 1 v_1 v1 v 5 v_5 v5的费用最短路
image.png

结果
image.png

重心问题/选址问题

image.png

image.png

问题转化:求出各个顶点对之间的最短距离,然后得到某一顶点到其他各个顶点的(最短重量·距离)和最小,这个顶点即为所求

计算结果展示
image.png

最小生成树算法及其networkx实现

基本概念

  1. 树:连通的五圈图
  2. 树的判定定理:n个顶点m条边的图
  3. 生成树、最小生成树

最小生成树算法

Kruskal算法和Prim算法
Kruskal算法
贪心,每次选择权值最小的边加入子图T,并保证不形成环,直到子图中包含 n − 1 n-1 n1条边为止
Prim算法
使用两个集合 P P P Q Q Q,从任意 p ∈ P p \in P pP v ∈ V − P v \in V-P vVP,选择最小权值的边 p v pv pv,将 v v v加入 P P P p v pv pv加入Q,直到 P = V P=V P=V为止
说明:对比Kruskal算法和Prim算法,Kruskal算法是显式地说明了不能在生成子图中出现环,Prim算法则是通过设定选定新边的一个顶点在 P P P集合,一个顶点在 V − P V-P VP集合这样隐式保证的

NetworkX提供接口
T=minimum_spanning_tree(G, weight='weight', algorithm='kruskal')
G为输入图
algorithm的取值有三种字符串:‘kruskal’,‘prim’,或’boruvka’,缺省值为’kruskal’
返回值T为所求得的最小生成树的可迭代对象

示例
image.png

最小生成树应用

image.png

说明:从这个题看出最小生成树和最短路算法的区别,最短路在找的是各个节点到某个节点的最短,而最小生成树在找的是一条通过全部节点的最短路

结果
image.png

匹配问题

image.png

问题转化:赋权图 G = ( V , E , W ^ ) G=(V, E, \hat{W}) G=(V,E,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 v_1, v_2, ..., v_5 v1,v2,...,v5表示5个人, v 6 , v 7 , v 8 , v 9 , v 10 v_6, v_7, v_8, v_9, v_{10} v6,v7,v8,v9,v10表示5项工作,邻接矩阵 W ^ \hat{W} W^满足
image.png

代码:

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]  #提取对应的效益
d=c.sum()  #计算总的效益
print("工作分配对应关系为:\n人员编号:",L1)
print("工作编号:", L2); print("总的效益为:",d)

最大流最小费用问题

网络流问题——如何安排使流量最大,即最大流问题,如公路系统中有车辆流、物资调配系统中有物资流、金融系统中有现金流等

基本概念

  1. 有向图 D ( V , A ) D(V, A) D(V,A)、源点 v s v_s vs、汇点 v t v_t vt、弧容量 c ( v i , v j ) ≥ 0 c(v_i, v_j) \geq 0 c(vi,vj)0 、网络流 f ( v i , v j ) f(v_i, v_j) f(vi,vj)
  2. 可行流的条件
  3. 增广路

最大流问题可写为这样一个线性规划问题
image.png

Ford-Fulkerson算法寻求最大流

使用NetworkX求解网络最大流
image.png

最小费用流问题

标号说明
f i j f_{ij} fij为弧 ( v i , v j ) (v_i, v_j) (vi,vj)上的流量, b i j b_{ij} bij为弧 ( v i , v j ) (v_i, v_j) (vi,vj)上的单位费用, c i j c_{ij} cij为弧 ( v i , v j ) (v_i, v_j) (vi,vj)上的容量,问题转化为下面的线性规划问题
image.png
v = v m a x v=v_{max} v=vmax时,问题有解;当 v > v m a x v > v_{max} v>vmax时,问题无解

使用NetworkX求解问题
image.png

代码:

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算法

引文分析思想
当网页甲有一个链接指向网页乙,就认为乙获得了甲对它贡献的分值,该值的多少取决于网页甲本身的重要程度,即网页甲的重要性越大,网页乙获得的贡献值就越高。
由于网络中网页链接的相互指向,pagerank分值计算为一个迭代过程,最终网页根据所得分值进行排序

假设
我们在上网时浏览页面并选择下一个页面的过程,与过去浏览过哪些页面无关,而仅依赖于当前所在的页面。
这一选择过程可以认为是一个有限状态、离散时间的随机过程,其状态转移规律用Markov链描述
image.png
说明: a i j a_{ij} aij表示从页面 i i i转移到页面 j j j的概率, 1 − d N \frac{1-d}{N} N1d为随机跳转时到页面 j j j的概率, d b i j r i d \frac{b_{ij}}{r_i} dribij为根据连接进行跳转到页面 j j j的概率

再根据正则Markov的平稳分布,得到各个网页被访问的概率分布,这个概率就被定义为各个网页的PageRank值

image.png

使用NetworkX求解
image.png

复杂网络简介

重点关注复杂网络的统计性质,并使用NetworkX计算

复杂网络概况

复杂网络:具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络
特征:结构复杂、网络进化、连接多样性、动力学复杂性、节点多样性
研究内容:网络的几何性质,网络的形成机制,网络演化的统计规律,网络上的模型性质,以及网络的结构稳定性,网络的演化动力学机制等问题
基本测度:度(degree)及其分布特征,度的相关性,集聚程度及其分布特征,最短距离及其分布特征,介数(betweenness)及其分布特征,连通集团的规模分布

  1. 节点的度和度分布:度分布一般用直方图展示, A 2 A^2 A2的对角元素 a i i 2 a_{ii}^2 aii2即为节点 v i v_i vi的度,平均度 < k > = t r ( A 2 ) / N <k> = tr(A^2)/N <k>=tr(A2)/N
  2. 平均路径长度,网络直径
  3. 聚类系数

image.png

代码:

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.add_nodes_from(range(1,7))  #添加顶点集
G.add_edges_from(L)
D=nx.diameter(G)  #求网络直径
LH=nx.average_shortest_path_length(G) #求平均路径长度
Ci=nx.clustering(G)   #求各顶点的聚类系数
C=nx.average_clustering(G)  #求整个网络的聚类系数
print("网络直径为:",D,"\n平均路径长度为:",LH)
print("各顶点的聚类系数为:")
for index,value in enumerate(Ci.values()):
    print("(顶点v{:d}: {:.4f});".format(index+1,value),end=' ')
print("\n整个网络的聚类系数为:{:.4f}".format(C))

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/340795.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

五、垃圾回收

1. 垃圾回收基础 1.1 什么是垃圾 简单说就是&#xff1a;内存中已经不再被使用到的内存空间就是垃圾。 1.2 如何判定是垃圾 1.2.1 引用计数法 引用计数法&#xff1a;给对象添加一个引用计数器&#xff0c;有访问就 1&#xff0c;引用失效就 -1 引用计数法的优缺点&#…

GIS项目实战10:MySQL数据库的安装与配置教程

MySQL是一个关系型数据库管理系统&#xff0c;由瑞典 MySQL AB 公司开发&#xff0c;属于 Oracle 旗下产品。MySQL是最流行的关系型数据库管理系统之一&#xff0c;在 WEB 应用方面&#xff0c;MySQL是最好的RDBMS (Relational Database Management System&#xff0c;关系数据…

2024年【黑龙江省安全员C证】免费试题及黑龙江省安全员C证作业考试题库

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年【黑龙江省安全员C证】免费试题及黑龙江省安全员C证作业考试题库&#xff0c;包含黑龙江省安全员C证免费试题答案和解析及黑龙江省安全员C证作业考试题库练习。安全生产模拟考试一点通结合国家黑龙江省安全员C证…

根据音乐合成舞蹈;提升预训练扩散模型分辨率;基于扩散模型的视频超分;LLM推理加速框架;3D控制运动人像合成

本文首发于公众号&#xff1a;机器感知 根据音乐合成舞蹈&#xff1b;提升预训练扩散模型分辨率&#xff1b;基于扩散模型的视频超分&#xff1b;LLM推理加速框架&#xff1b;3D控制运动人像合成 DanceMeld: Unraveling Dance Phrases with Hierarchical Latent Codes for M…

架构篇11:架构设计流程-设计备选方案

文章目录 架构设计第 2 步&#xff1a;设计备选方案设计备选方案实战小结 上一期我讲了架构设计流程第 1 步识别复杂度&#xff0c;确定了系统面临的主要复杂度问题后&#xff0c;方案设计就有了明确的目标&#xff0c;我们就可以开始真正进行架构方案设计了。今天我来讲讲架构…

CVE重要通用漏洞复现java phpCVE-2021-44228

在进行漏洞复现之前我们需要在linux虚拟机上进行docker的安装 我不喜欢win上安因为不知道为什么总是和我的vmware冲突 然后我的kali内核版本太低 我需要重新安装一个新的linux 并且配置网络 我相信这会话费我不少时间 查看版本 uname -a 需要5.5或以上的版本 看错了浪…

理想斯特林循环空调

理想斯特林循环空调 淘汰传统的压缩机、摒弃现有的斯特林制冷机&#xff0c;理想斯特林循环制冷机是未来制冷空调领域的发展方向&#xff01; 采用理想斯特林循环制冷机&#xff0c;是目前全球首创、国际领先、世界唯一、效率最高的斯特林制冷机。 取消了传统压缩机空调的蒸发器…

计算机视觉的应用

计算机视觉&#xff08;Computer Vision&#xff09;是一门研究如何让计算机能够理解和分析数字图像或视频的学科。简单来说&#xff0c;计算机视觉的目标是让计算机能够像人类一样对视觉信息进行处理和理解。为实现这个目标&#xff0c;计算机视觉结合了图像处理、机器学习、模…

接口测试 04 -- Jsonpath断言、接口关联处理

1. JsonPath基本介绍 1.1 JsonPath简介 JsonPath是一种用于在JSON数据中定位和提取特定数据的表达式语言。它类似于XPath用于XML的定位和提取&#xff0c;可以帮助我们灵活地从复杂的JSON结构中获取所需的数据。 1.2 JsonPath的特点 ● JsonPath可处理的报文类型为字典类型 …

【C语言深度剖析——第四节(关键字4)】《C语言深度解剖》+蛋哥分析+个人理解

追求本质&#xff0c;不断进步 本文由睡觉待开机原创&#xff0c;转载请注明出处。 本内容在csdn网站首发 欢迎各位点赞—评论—收藏 如果存在不足之处请评论留言&#xff0c;共同进步&#xff01; 这里写目录标题 一、空间的申请1.变量定义1.1变量定义的概念&#xff1a;1.2变…

cuda二进制文件中到底有些什么

大家好。今天我们来讨论一下&#xff0c;相比gcc编译器编译的二进制elf文件&#xff0c;包含有 cuda kernel 的源文件编译出来的 elf 文件有什么不同呢&#xff1f; 之前研究过一点 tvm。从 BYOC 的框架中可以得知&#xff0c;前端将模型 partition 成 host 和 accel(accel 表…

日期处理第四篇(终)- Java日期时间处理大总结

文章目录 日期时间概念通用标准日期字段解析国际化的日期格式 日期的实战第一个问题&#xff1a;日期常用时间操作第二个问题&#xff1a;时区的问题时区概念时区的处理ZoneID的使用 ZoneOffset的使用让人恼火的夏令时 第三个问题&#xff1a;MySQL存储时间用什么类型&#xff…

HCIA——23DNS层次域名空间、域名服务器、域名解析的原理的选择、解答

学习目标&#xff1a; 计算机网络 1.掌握计算机网络的基本概念、基本原理和基本方法。 2.掌握计算机网络的体系结构和典型网络协议&#xff0c;了解典型网络设备的组成和特点&#xff0c;理解典型网络设备的工作原理。 3.能够运用计算机网络的基本概念、基本原理和基本方法进行…

【笔记】Blender4.0建模入门-3物体的基本操作

Blender入门 ——邵发 3.1 物体的移动 演示&#xff1a; 1、选中一个物体 2、选中移动工具 3、移动 - 沿坐标轴移动 - 在坐标平面内移动 - 自由移动&#xff08;不好控制&#xff09; 选中物体&#xff1a;右上的大纲窗口&#xff0c;点击物体名称&#xff0c;物体的轮…

LabVIEW电火花线切割放电点位置

介绍了一个电火花线切割放电点位置分布评价系统&#xff0c;特别是在系统组成、硬件选择和LabVIEW软件应用方面。 本系统由两个主要部分组成&#xff1a;硬件和软件。硬件部分包括电流传感器、高速数据采集卡、开关电源、电阻和导线。软件部分则由LabVIEW编程环境构成&#xf…

2024如何入局云计算?亚麻云助力您成为云专家!一次不过,免费再考

福利派送 2024年伊始&#xff0c;一波又一波的裁员潮又开始啦&#xff01;还在做传统行业&#xff1f;还在做传统程序员&#xff1f;亦或是对未来依旧迷茫&#xff1f;赶紧趁着行业东风&#xff0c;开始了解入门云计算吧&#xff01;亚马逊云科技&#xff0c;认证福利免费送&a…

C++——结构体

1&#xff0c;结构体基本概念 结构体属于用户自定义的数据类型&#xff0c;允许用户存储不同的数据类型。像int&#xff08;整型&#xff09;&#xff0c;浮点型&#xff0c;bool型&#xff0c;字符串型等都是属于系统内置的数据类型。而今天要学习的结构体则是属于我们自定义…

Java前端——HTTP协议中get和post的区别

get 和 post是 HTTP 请求的两种方法 应用场景&#xff1a; 一般 get 请求用于对服务器资源不会产生影响的场景&#xff0c;如请求一个网页的资源 post 请求一般用于对服务器资源会产生影响的情景&#xff0c;如注册用户这一类的操作。 get请求一般用于向服务器请求数据&…

Elastic Stack 8.12:通过对 ES|QL 等的改进增强了向量搜索

作者&#xff1a;来自 Elastic Tyler Perkins, Shani Sagiv, Gilad Gal, Ninoslav Miskovic Elastic Stack 8.12 构建于 Apache Lucene 9.9&#xff08;有史以来最快的 Lucene 版本&#xff09;之上&#xff0c;基于我们对标量量化和搜索并发性的贡献&#xff0c;为文本、向量和…

Bert详解

Bert框架 基本架构Embeddingpre-trainingMLM&#xff08;Mask Language Model&#xff09;NSP&#xff08;Next Sentence Prediction&#xff09; fine-tuning优缺点 基本架构 由Transformer的Encoder层堆叠而来 每个部分组成如下&#xff1a; Embedding Embedding由三种E…