MCM备赛笔记——图论模型

这篇具有很好参考价值的文章主要介绍了MCM备赛笔记——图论模型。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Key Concept

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

图论的基本模型

  1. 无向图

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

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

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

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

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

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

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

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

MCM备赛笔记——图论模型,数学建模,笔记,图论,数学建模

MCM备赛笔记——图论模型,数学建模,笔记,图论,数学建模

图论问题

  1. 最短路径问题:

    • 在加权图中找到两点间的最短路径,如Dijkstra算法或Bellman-Ford算法。MCM备赛笔记——图论模型,数学建模,笔记,图论,数学建模MCM备赛笔记——图论模型,数学建模,笔记,图论,数学建模MCM备赛笔记——图论模型,数学建模,笔记,图论,数学建模MCM备赛笔记——图论模型,数学建模,笔记,图论,数学建模
  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 = None
        min_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] = root1

def 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:
            break

    if len(mst) != len(G.nodes()) - 1:
        print('该图不是连通图')
    return mst


mst=kruskal(G)
mst

 

  1. 网络流问题:

    • 最大流问题

      #网络最大流问题
      #最大流问题是指在一个网络中,从源点到汇点的最大流量是多少
      #1.将所有的边的流量初始化为0
      #2.在残余网络中找到一条增广路径,如果没有增广路径,则结束
      #3.在增广路径上找到最小的残余容量,将这个容量增加到这条路径上
      #4.重复上一步,直到没有增广路径
      #5.最后得到的就是最大流
      import networkx as nx
      import matplotlib.pyplot as plt
      
      G = 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来解决问题MCM备赛笔记——图论模型,数学建模,笔记,图论,数学建模

  2. 最大流最小费用问题MCM备赛笔记——图论模型,数学建模,笔记,图论,数学建模

    #最小费用最大流问题
    #最小费用最大流问题是指在一个网络中,从源点到汇点的最大流量是多少,且最小费用是多少
    #1.将所有的边的流量初始化为0
    #2.在残余网络中找到一条增广路径,如果没有增广路径,则结束
    #3.在增广路径上找到最小的残余容量,将这个容量增加到这条路径上
    #4.重复上一步,直到没有增广路径
    #5.最后得到的就是最大流
    #6.计算最小费用
    #7.重复上述步骤,直到最小费用不再减少
    
    import networkx as nx
    import matplotlib.pyplot as plt
    import numpy as np
    
    L = [('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)] = f
    
    print("最小费用最大流为:\n", flow_dict)
    print("最小费用为:\n", min_cost)
    print("最大流的流量为:\n", sum(A[:, -1]))
    print("最小费用最大流的邻接矩阵\n", A)
    

    MCM备赛笔记——图论模型,数学建模,笔记,图论,数学建模

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

到了这里,关于MCM备赛笔记——图论模型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023 年(MCM/ICM)美国大学生数学建模竞赛参赛规则及注意事项

    2023美赛参赛规则及注意事项正式发布,快跟随我来一起看一看。 注意事项: • COMAP 比赛时间为美国东部时区:除注明当地时间外,本说明中给出的所有时间均以东部标准时间(EST)为准。 1.辅助报名截止时间: 北京时间 2023 年 2 月 17 日 00:00 2.比赛时间:  (北京时间:

    2024年02月15日
    浏览(43)
  • 2022大湾区杯粤港澳金融数学建模备赛

    桥水基金: 做空,说白了就是预先看到别人所看不到的灾难,然后利用这个灾难,赌相关的资产价格下跌。而桥水基金是以做空闻名于世界,也是国际最著名的对冲基金之一。 由于桥水多次准确地判断了市场系统性风险,因此,桥水基金也被行业认为是危机和风险管理的风

    2024年02月06日
    浏览(48)
  • 2023年美国大学生数学建模MCM问题Y:了解二手帆船的价格-解题思路及代码分享

    2023 MCM Problem Y: Understanding Used Sailboat Prices 2023年MCM问题Y:了解二手帆船的价格 和许多奢侈品一样,帆船的价值会随着老化和市场条件的变化而变化。附件中所附的“2023_MCM_Problem_Y_Boats.xlsx”文件包括了2020年12月在欧洲、加勒比海和美国登广告出售的大约3500艘36至56英尺长的帆

    2023年04月15日
    浏览(48)
  • 数学建模笔记(四):初等模型

    研究对象的机理比较简单,一般用静态、线性、确定性模型就能达到建模目的时,我们基本上可以用初等数学的方法来构造和求解模型。 如果对于某个实际问题,采用初等方法和高级方法建立的两个模型的应用效果相差无几时,,初等方法更受欢迎。 (1)热量传播只有传导

    2024年02月08日
    浏览(61)
  • 数学建模笔记(十二):概率模型

    从挂钩考虑 m个挂钩,n位工人 s:一周期内运走的产品数 n:所有工人在周期时间内生产总数 D:传送带效率 p:每只挂钩非空概率 q:每只挂钩为空概率,p+q=1 r:挂钩没有被某位工人触到的概率 D = s n = m p n = m ( 1 − q ) n = m ( 1 − ( r n ) ) n = m ( 1 − ( 1 − 1 m ) n ) n D=frac{s}{n}=

    2024年02月11日
    浏览(39)
  • 数学建模笔记(七):综合评价模型

    代表性,也就是这一指标的区分度,最具代表性就是对观测记录最具区分度 强调通行能力前后的变化 (一)指标一致化处理 (二)指标无量纲化处理 (三)定性指标量化 主观评价要量化,无法避免主观因素 f ( 3 ) f(3) f ( 3 ) 使用了两次,其实有四个式子,才解出了四个量

    2024年02月05日
    浏览(62)
  • 【数学建模】传染病模型笔记

    传染病的基本数学模型,研究传染病的传播速度、空间范围、传播途径、动力学机理等问题,以指导对传染病的有效地预防和控制。常见的传染病模型按照传染病类型分为 SI、SIR、SIRS、SEIR 模型等,按照传播机理又分为基于常微分方程、偏微分方程、网络动力学的不同类型。

    2024年04月10日
    浏览(44)
  • 数学建模学习笔记(14)聚类模型

    聚类问题概述 :把样本划分为由相似的对象组成的多个类的过程。 K均值聚类算法流程 : 指定需要划分的簇的个数K。 随机选择K个数据对象作为初始的聚类中心(不一定是样本点)。 计算其他的各个数据对象到这K个聚类中心的距离,把数据对象划分到距离它最近的它最近的

    2024年02月07日
    浏览(38)
  • 数学建模——图论学习

    一、图论基础 图分为有限图与无限图两类,本课只涉及有限图,即顶点和边都是有限集合 (2)有向图:每一条边都是有向的 无向图:每一条边都是无向的 除外都是混合图  注意:有向图边的描述{1.每一条边都需要描述到   2.始点,终点 (3)邻接点:两个结点之间有一条边

    2024年02月04日
    浏览(46)
  • 数学建模-图论 最短路径

    作图

    2024年02月16日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包