首页 > 其他分享 >图与网络——最小树问题精解

图与网络——最小树问题精解

时间:2024-09-10 23:03:52浏览次数:13  
标签:最小 网络 V1 V2 V3 V4 精解 生成 小树

最小生成树(Minimum Spanning Tree, MST)问题是图论中的一个重要问题,其核心思想是:给定一个无向加权图(每条边具有权重值),通过选择若干边构建一棵包含所有顶点的生成树,并确保这些边的权重总和最小。最小生成树不仅保持了生成树的连通性和无圈性,还要求总权重最小化。在实际应用中,最小生成树问题在计算机科学和网络设计领域广泛使用,它常用于优化电路网络、建立通信网络、规划道路交通系统等,可以有效降低基础设施建设成本、提高资源利用效率,这类问题可通过经典的算法如Prim和Kruskal进行求解。

无向图 最小树

一、最小树的界定与描述

什么是树?
树是图论中的一种特殊数据结构,是一个无圈、连通的无向图。树由顶点和边组成,满足以下特征:
无圈性:树中没有任何回路,即任意两个顶点之间有且仅有一条路径。
连通性:树是连通的,任意两个顶点之间都有一条路径相连。

什么是生成树?
生成树是指从一个连通无向图中选择若干条边,构成一个包含图中所有顶点且无圈的子图。生成树满足以下条件:
覆盖所有顶点:生成树中的顶点与原图相同,包含原图的所有顶点。
无圈性:生成树中没有任何环,满足树的定义。
边的数量:生成树的边数是\(n-1\),\(n\)是顶点的数量。
对于一个连通图,可能存在多个不同的生成树,每棵生成树都符合上述定义。

树非生成树 生成树或支撑树

树图具有下面重要性质:
设 \(T=(V, E)\) 是一个 \(|V|\geqslant 3\) 的无向图,则下列关于树的命题是等价的:
\(T\) 连通且无圈;
\(T\) 的任何两个顶点间均必有一条且仅有一条通路相连;
\(T\) 连通且有 \(n-1\) 条边,这里 \(n=|V|\);
\(T\) 有 \(n-1\) 条边且无圈,这里 \(n=|V|\);
\(T\) 无圈,但在 \(T\) 中任意两个不相邻的顶点间添加一条边,就可构成一个圈;
\(T\) 连通,但去掉任意一条边后就不连通,即树 \(T\) 是连通且边数最少的图。

什么是最小生成树(最小树)?
最小生成树是生成树的一种特殊形式,定义为:在一个加权无向图中,所有生成树中边权和最小的那棵生成树。它不仅符合生成树的所有条件,还要求所选边的权重总和最小。若\(G=(V, E, W)\) 是一个连通的赋权图,\(T=(V, S)\) 是 \(G\) 的支撑树,把 \(T\) 中所有边的权之和称作树 \(T\) 的权,记作 \(w(T)\),即:$$w(T) = \sum_{e\in S} w(e)$$,\(G\) 中权最小的支撑树 \(T\) 称为 \(G\) 的最小支撑树,简称最小树。
在现实生活中,比如在城市之间建立输电网络、电话线网或光纤网络时,我们希望找到一种最优的布线方案,使得总长度或总费用最小化。这类问题可以被转化为赋权图的最小树问题。

最小生成树具有特点:
连通性:最小生成树依然是连通的,能够覆盖图的所有顶点。
无圈性:最小生成树没有回路,符合树的基本属性。
最小权重和:最小生成树的边权重总和在所有可能的生成树中最小。
最小生成树在网络优化、路径规划、通信设计等领域具有重要应用,常用于降低成本、提高效率。

二、最小树算法Python

最小生成树的求解方法有多种,最经典的两种算法是Prim算法和Kruskal算法。

2.1 kruscal算法

Kruskal算法同样基于贪心思想,但与Prim算法不同的是,它是基于边的排序进行操作的。Kruskal算法先将图中的所有边按权重从小到大排序,然后依次选择这些边,确保选择的边不会形成环。算法适合处理稀疏图。Kruskal算法步骤:

将图中的所有边按权重升序排列。
依次选择权重最小的边,判断该边是否会形成环。如果不会形成环,则将该边加入生成树。
重复步骤2,直到生成树包含 \(n-1\)条边为止。

例1:给定无向图\(G(n,m\)表明图G有\(n\)个顶点,\(m\)条边,通过Kruskal算法构造一个最小生成树。

import networkx as nx
import matplotlib.pyplot as plt

# 设置中文字体,确保Matplotlib支持中文
plt.rcParams['font.sans-serif'] = ['SimHei']  # 设置中文字体为黑体
plt.rcParams['axes.unicode_minus'] = False  # 解决负号显示问题

# 创建图
G = nx.Graph()

# 添加节点
nodes = ['V1', 'V2', 'V3', 'V4', 'V5', 'V6']
G.add_nodes_from(nodes)

# 添加边和权重
edges = [
    ('V1', 'V5', 1),
    ('V1', 'V6', 2),
    ('V1', 'V2', 3),
    ('V2', 'V6', 4),
    ('V2', 'V3', 5),
    ('V3', 'V6', 6),
    ('V3', 'V4', 7),
    ('V4', 'V6', 8),
    ('V4', 'V5', 9)
]
G.add_weighted_edges_from(edges)

# Kruskal最小生成树的边
mst_edges = [('V1', 'V5'), ('V1', 'V6'), ('V1', 'V2'), ('V2', 'V3'), ('V3', 'V4')]

# 手动设置每个节点的位置,确保V6在中间,其他顶点围绕它
pos = {
    'V6': (0, 0),       # V6在中间
    'V1': (0, 1),       # V1在上方
    'V2': (1, 0.5),     # V2在右上方
    'V3': (1, -0.5),    # V3在右下方
    'V4': (0, -1),      # V4在下方
    'V5': (-1, 0)       # V5在左侧
}

# 绘制图形
plt.figure(figsize=(8, 6))

# 绘制所有边,调整线条粗细和节点大小,设置节点标签的字体大小为15
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=3000, font_size=45, font_weight='bold', edge_color='gray', width=6)  # 字体和边线粗细增加三倍
nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): f'{d}' for u, v, d in edges}, font_size=30)  # 边权重的字体大小为默认的三倍

# 用红色标出最小生成树的边,线宽设置为原来的三倍
nx.draw_networkx_edges(G, pos, edgelist=mst_edges, width=6, edge_color='red')  # 最小生成树的边线宽度为原来的三倍

# 设置标题,字体大小增大三倍
plt.title("最小生成树", fontsize=60)

# 显示图形
plt.show()

2.2 Prim算法

Prim算法是一种基于贪心思想的算法,适合处理稠密图。算法从一个起始顶点开始,将其加入生成树,然后不断选择与当前生成树相连的权重最小的边,将该边所连接的顶点加入生成树,直到所有顶点都被包括在内为止。Prim算法步骤:

从任意一个顶点出发,初始时将该顶点加入生成树。
查找与已加入生成树的顶点相邻的最小权重边,将该边及其相邻的顶点加入生成树。
重复上述步骤,直到所有顶点都包含在生成树中。

例2:某地的5个城镇需要铺设天然气管道,下图中给出了5个城镇之间可以铺设管道的情况的以及距离,先求一个设计方案,用最短的管道将5个城镇连接起来。

原图 迭代1 迭代5
import networkx as nx
import matplotlib.pyplot as plt
import heapq

# 设置中文字体,确保Matplotlib支持中文
plt.rcParams['font.sans-serif'] = ['SimHei']  # 设置中文字体为黑体
plt.rcParams['axes.unicode_minus'] = False  # 解决负号显示问题

# 创建图
G = nx.Graph()

# 添加节点
nodes = ['V1', 'V2', 'V3', 'V4', 'V5', 'V6']
G.add_nodes_from(nodes)

# 添加边和权重
edges = [
    ('V1', 'V2', 1),
    ('V1', 'V4', 7),
    ('V1', 'V3', 3),
    ('V1', 'V5', 9),
    ('V2', 'V3', 6),
    ('V2', 'V4', 4),
    ('V2', 'V5', 3),
    ('V3', 'V4', 5),
    ('V3', 'V6', 10),
    ('V4', 'V5', 8),
    ('V4', 'V6', 3)
]
G.add_weighted_edges_from(edges)

# 修改邻接表,基于edges
graph = {
    'V1': {'V2': 1, 'V3': 3, 'V4': 7, 'V5': 9},
    'V2': {'V1': 1, 'V3': 6, 'V4': 4, 'V5': 3},
    'V3': {'V1': 3, 'V2': 6, 'V4': 5, 'V6': 10},
    'V4': {'V1': 7, 'V2': 4, 'V3': 5, 'V5': 8, 'V6': 3},
    'V5': {'V1': 9, 'V2': 3, 'V4': 8},
    'V6': {'V3': 10, 'V4': 3}
}

# Prim算法实现
def prim_mst(graph, start):
    mst = []  # 存储最小生成树的边
    visited = set([start])  # 记录已经访问过的节点
    edges = [(weight, start, to) for to, weight in graph[start].items()]
    heapq.heapify(edges)  # 将边加入优先队列

    while edges:
        weight, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to))
            for next_to, next_weight in graph[to].items():
                if next_to not in visited:
                    heapq.heappush(edges, (next_weight, to, next_to))
    return mst

# 使用Prim算法求最小生成树
mst_edges = prim_mst(graph, 'V1')

# 定义节点的位置布局,V3在中间
pos = {
    'V3': (0, 0),       # V3在中间
    'V1': (0, 1),       # V1在上方
    'V2': (1, 0.5),     # V2在右上方
    'V4': (0, -1),      # V4在下方
    'V5': (-1, 0),      # V5在左侧
    'V6': (1, -0.5)     # V6在右下方
}

# 调整字体大小和边线粗细
plt.figure(figsize=(8, 6))
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=3000, font_size=36, font_weight='bold', edge_color='gray', width=6)  # 调整font_size和width
nx.draw_networkx_edge_labels(G, pos, edge_labels={(u, v): f'{d}' for u, v, d in edges}, font_size=30)  # 边权重的字体大小调大

# 用红色标出最小生成树的边
nx.draw_networkx_edges(G, pos, edgelist=mst_edges, width=6, edge_color='red')  # 边线粗三倍

# 设置标题
plt.title("Prim算法求解最小生成树", fontsize=36)  # 标题字体调整

# 显示图形
plt.show()

总结

最小生成树问题是图论中重要的优化问题,它要求在给定的无向图中找到一棵边权和最小的生成树。生成树具有连通性和无环性,而最小生成树则在此基础上还要求边的权重和最小。通过Prim算法和Kruskal算法,我们可以高效地解决最小生成树问题。Prim算法适用于稠密图,而Kruskal算法则更适合稀疏图。在实际应用中,最小生成树被广泛用于网络设计、通信系统规划、输电线路布局等领域。在实际工程中,最小生成树的求解不仅能降低系统的成本,还能提高资源的利用效率。通过使用适当的算法和数据结构,我们能够快速且准确地求解最小生成树问题。

参考资料

  1. 算法设计分析(Kruskal构造最小生成树)
  2. 最小生成树(最小支撑树)算法

标签:最小,网络,V1,V2,V3,V4,精解,生成,小树
From: https://www.cnblogs.com/haohai9309/p/18407024

相关文章

  • 计算机网络
    计算机网络总分100=期中20+期末50+实验20+平时10(期中考前三章,期末考后三章)第一章概述1.1互联网两个重要基本特点:连通性、共享连通性:上网用户交换各种信息共享:指资源共享,可以是信息共享、软件共享、硬件共享1.2网络把许多计算机连接在一起,互连网把许多网络通过......
  • 网络编程day03(网络体系结构、调试命令、TCP/IP对比)
    目录1》网络的体系结构1>OSI模型 2>TCP/IP模型3>常见网络协议4> DNS域名解析协议2》网络调试命令1>ping:测试网络连通性(ICMP)2>netstat  3》Dos(拒绝式服务)攻击? 4》 TCP/IP协议对比1》网络的体系结构网络采用分而治之的方法设计,将网络的功能划分为不......
  • day08(网络编程基础)Linux IO 模型(IO多路复用)
    目录场景假设select特点编程步骤练习练习一:输入鼠标的时候,响应鼠标事件,输入键盘的时候,响应键盘事件(两路IO)练习二:用select创建并发服务器,可以同时连接多个客户端(0,sockfd)(12min)练习三:用select创建并发服务器,可以与多个客户端进行通信(监听键盘、socket、多个accept......
  • day07(网络编程基础)Linux IO模型(阻塞IO、非阻塞IO、信号驱动IO(异步IO))
    目录场景假设一.阻塞式IO:最常见、效率低、不耗费cpuTCP粘包、拆包发生原因:二.非阻塞IO:轮询、耗费CPU,可以处理多路IO设置非阻塞的方式1.通过函数自带参数设置2.通过设置文件描述符的属性。把文件描述符的属性设置为非阻塞三.信号驱动IO/异步IO:异步通知方式,需要底层驱......
  • Python 网络编程
    什么是Socket?socket()函数参数Socket对象(内建)方法简单实例服务端客户端PythonInternet模块Python提供了两个级别访问的网络服务:低级别的网络服务支持基本的Socket,它提供了标准的BSDSocketsAPI,可以访问底层操作系统Socket接口的全部方法。高级别的网络......
  • Linux网络——从《计算机网络》到网络编程
    文章目录从《计算机网络》到网络编程从计算机到计算机网络解决问题网络与计算机系统计算机网络的传输流程IP地址与MAC地址从《计算机网络》到网络编程科班的同学大多学过计算机网络,而非科班的同学也多多少少听说过一些计算机网络体系十分繁杂且精妙,这三四十年来计......
  • Chapter 14 计算机网络基本概述
    欢迎大家订阅【Vue2+Vue3】入门到实践专栏,开启你的Vue学习之旅!文章目录前言一、网络的基本概念二、集线器、交换机和路由器三、互连网与互联网四、网络的类型五、互连网的组成1.边缘部分2.核心部分六、网络协议前言计算机网络是现代信息社会的基础,本章详细......
  • 卷积神经网络多输入和多输出的通道数(李沐老师课程)
    多通道卷积计算特殊的卷积层1*1卷积核代码:"""​多输入多输出的互相关运算"""importtorchfromtorchimportnnfromd2limporttorchasd2l​"""实现多输入通道互相关运算"""​​defcorr2d_multi_in(x,k): returnsum(d2l.corr......
  • Baichuan-13B 大模型的网络带货博客​
    Baichuan-13B是由百川智能继Baichuan-7B之后开发的包含130亿参数的开源可商用的大规模语言模型,在权威的中文和英文benchmark上均取得同尺寸最好的效果。本次发布包含有预训练(Baichuan-13B-Base)和对齐(Baichuan-13B-Chat)两个版本。Baichuan-13B有如下几个特点:更大尺寸......
  • 从学习到的因果网络中估计因果效应
    本文介绍了一种新的因果效应推断方法,它不同于传统的先构建概率表达式再用观测数据评估的方法。该研究提出了一种替代方案,即直接从观测数据中学习因果贝叶斯网络(CBN)及其潜在变量,然后利用学习到的模型来回答因果效应查询。这种方法特别适用于离散的可观测变量。通过实验评估表明,这种......