当前位置: 首页 > news >正文

MCM备赛笔记——图论模型

Key Concept

图论是数学的一个分支,专注于研究图的性质和图之间的关系。在图论中,图是由顶点(或节点)以及连接这些顶点的边(或弧)组成的。图论的模型广泛应用于计算机科学、通信网络、社会网络、生物信息学、城市交通规划等多个领域。

图论的基本模型

  1. 无向图

    • 顶点之间的边没有方向。无向图常用于表示双向关系,如社交网络中的友谊关系。
  2. 有向图

    • 顶点之间的边有方向。有向图适用于表达方向性的关系,如网页间的链接。
  3. 加权图

    • 边或顶点被赋予权重(或成本、容量等)。加权图常用于道路网络,其中权重可以表示距离、时间、费用等。
  4. 多重图

    • 两个顶点之间可以有多条边。多重图适用于存在多种关系的场景,如航线图。
  5. 子图

    • 原图的一部分,包含原图的部分顶点和边。
  6. 完全图

    • 每对顶点之间都恰好有一条边。完全图用于当每个节点都与其他节点直接相连的情况。
    • 无环连通图。树常用于表示层次结构,如家族树或组织结构。
  7. 二分图

    • 顶点可分为两个互不相交的集合,图中的每条边连接的两个顶点分别属于这两个不同的集合。二分图适用于匹配问题,如工作分配或婚姻匹配。

使用python的networkx库函数来绘制图

图论问题

  1. 最短路径问题

    • 在加权图中找到两点间的最短路径,如Dijkstra算法或Bellman-Ford算法。
  2. 最小生成树

最小生成树这里有两种算法krual算法和prime算法

krual算法更适合稀疏图配合并查集来实现

prime算法更适合稠密图,直接对边进行遍历

#prim算法,更加适合稠密图
#1.任选一个顶点作为起始点,然后找到与其相连的最小权重的边,将这条边加入最小生成树中
#2.然后找到与这两个顶点相连的最小权重的边,将这条边加入最小生成树中
#3.重复上一步,直到所有的顶点都在最小生成树中
#4.最后得到的就是最小生成树def prim(G):mst = []nodes = list(G.nodes())visited = set([nodes[0]])  # 使用集合来快速检查是否访问过while len(visited) != len(nodes):min_edge = Nonemin_weight = float('inf')  # 设置一个很大的初始值for u in visited:for v in G.neighbors(u):if v not in visited and G[u][v]['weight'] < min_weight:min_weight = G[u][v]['weight']min_edge = [u, v, {'weight':G[u][v]['weight']}]if min_edge is not None:mst.append(min_edge)visited.add(min_edge[1])  # 添加新顶点到访问过的集合中return mst# 假设G是已经创建好的图
mst = prim(G)
mst
#krual算法,更加适合稀疏图
#1.将所有的边按照权重从小到大排序
#2.从权重最小的边开始,如果这条边的两个顶点不在同一个连通分量中,则将这条边加入最小生成树中,否则不加入
#3.重复上一步,直到所有的顶点都在同一个连通分量中
#4.最后得到的就是最小生成树#这里使用并查集来实现查找连通分量
class UnionFind:def __init__(self, nodes):self.parent = {node: node for node in nodes}#初始化每个节点的父节点都是自己def find(self, node):if self.parent[node] != node:self.parent[node] = self.find(self.parent[node])return self.parent[node]def union(self, node1, node2):root1 = self.find(node1)root2 = self.find(node2)if root1 != root2:self.parent[root2] = root1def kruskal(G):mst = []edges = list(G.edges(data=True))edges.sort(key=lambda x: x[2]['weight'])uf = UnionFind(G.nodes())for edge in edges:u, v = edge[0], edge[1]if uf.find(u) != uf.find(v):  # 如果u和v不在同一个集合中uf.union(u, v)  # 合并集合mst.append(edge)  # 加入最小生成树if len(mst) == len(G.nodes()) - 1:breakif len(mst) != len(G.nodes()) - 1:print('该图不是连通图')return mstmst=kruskal(G)
mst

 

  1. 网络流问题

    • 最大流问题

      #网络最大流问题
      #最大流问题是指在一个网络中,从源点到汇点的最大流量是多少
      #1.将所有的边的流量初始化为0
      #2.在残余网络中找到一条增广路径,如果没有增广路径,则结束
      #3.在增广路径上找到最小的残余容量,将这个容量增加到这条路径上
      #4.重复上一步,直到没有增广路径
      #5.最后得到的就是最大流
      import networkx as nx
      import matplotlib.pyplot as pltG = nx.DiGraph()
      G.add_edge('s', 'a', capacity=3.0)
      G.add_edge('s', 'b', capacity=1.0)
      G.add_edge('a', 'c', capacity=3.0)
      G.add_edge('b', 'c', capacity=5.0)
      G.add_edge('b', 'd', capacity=4.0)
      G.add_edge('d', 'e', capacity=2.0)
      G.add_edge('c', 't', capacity=2.0)
      G.add_edge('e', 't', capacity=3.0)# 绘制图形
      pos = nx.spring_layout(G)  # 定义一个布局,用于节点的位置
      nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray')# 绘制边的权重
      edge_labels = nx.get_edge_attributes(G, 'capacity')
      nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)plt.show()

      这里直接调用networkx来解决问题

  2. 最大流最小费用问题

    #最小费用最大流问题
    #最小费用最大流问题是指在一个网络中,从源点到汇点的最大流量是多少,且最小费用是多少
    #1.将所有的边的流量初始化为0
    #2.在残余网络中找到一条增广路径,如果没有增广路径,则结束
    #3.在增广路径上找到最小的残余容量,将这个容量增加到这条路径上
    #4.重复上一步,直到没有增广路径
    #5.最后得到的就是最大流
    #6.计算最小费用
    #7.重复上述步骤,直到最小费用不再减少import networkx as nx
    import matplotlib.pyplot as plt
    import numpy as npL = [('vs','v2',5,3),('vs','v3',3,6),('v2','v4',2,8),('v3','v2',1,2),('v3','v5',4,2),('v4','v3',1,1),('v4','v5',3,4),('v4','vt',2,10),('v5','vt',5,2)]
    G = nx.DiGraph()
    for i in range(len(L)):G.add_edge(L[i][0], L[i][1], capacity=L[i][2], weight=L[i][3])
    flow_dict = nx.max_flow_min_cost(G, 'vs', 'vt')
    min_cost = nx.cost_of_flow(G, flow_dict)node = list(G.nodes())
    n = len(node)
    A = np.zeros((n,n), dtype=int)
    for i, adj in flow_dict.items():for j, f in adj.items():A[node.index(i), node.index(j)] = fprint("最小费用最大流为:\n", flow_dict)
    print("最小费用为:\n", min_cost)
    print("最大流的流量为:\n", sum(A[:, -1]))
    print("最小费用最大流的邻接矩阵\n", A)
    

Key Concept Explanation 图论的模型和问题对于理解和解决现实世界中的复杂关系和网络结构具有重要意义。通过将实际问题抽象为图论问题,我们可以应用数学理论和算法来找到有效的解决方案。图论的应用范围非常广泛,从互联网的数据传输到社交网络的分析,再到交通网络的优化,都可以见到图论模型的影子。

http://www.lryc.cn/news/284237.html

相关文章:

  • 算法笔记(动态规划入门题)
  • 开发实践_阶段三
  • codegeex和通义灵码辅助编程——以及通义灵码无法登陆的bug解决
  • Android14之DefaultKeyedVector实现(一百八十二)
  • 银河麒麟操作系统 v10 中离线安装 Docker
  • 如何系统的学习Python
  • Java并发基础:一文讲清util.concurrent包的作用
  • C++PythonC# 三语言OpenCV从零开发(2):教程选择
  • 【嘉立创EDA-PCB设计指南】3.网络表概念解读+板框绘制
  • nodejs前端项目的CI/CD实现(二)jenkins的容器化部署
  • python爬虫案例分享
  • 【CC++】为什么 scanf 函数在读取字符串时不需要用取地址运算符
  • Linux dirs命令教程:dirs命令详解与实例(附实例详解和注意事项)
  • 掌握虚拟化:PVE平台安装教程与技术解析
  • Godot FileDialog无法访问其它盘符的文件
  • TestNG注释
  • 数据预处理 matlab 数据质量评估
  • 对象存储, 开源MinIO docker-compose.yml 文件
  • 爬虫笔记(一):实战登录古诗文网站
  • 适用于 Windows 11 的 12 个最佳免费 PDF 编辑器
  • 力扣每日一练(24-1-18)
  • MyBatis 使用报错:org.xml.sax.SAXParseException 元素内容必须由格式正确的字符数据或标记组成
  • PDF.js - 免费开源的 JavaScript 读取、显示 PDF 文档的工具库,由 Mozilla 开发并且持续维护
  • UI开发布局-HarmonyOS应用UI开发布局
  • 大数据开发之Hadoop(完整版+练习)
  • Redis与DB数据一致性-个人总结
  • VMware workstation安装debian-12.1.0虚拟机(最小化安装)并配置网络
  • SG-9101CGA(汽车+125°C可编程晶体振荡器)
  • 第十五届蓝桥杯单片机组备赛——独立键盘矩阵键盘
  • HCIA—— 16每日一讲:HTTP和HTTPS、无状态和cookie、持久连接和管线化、(初稿丢了,这是新稿,请宽恕我)