美丽的图论

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

**美丽的图论 **

Prüf 😉

对于 n 个顶点上的树的数量

n^(n-2),这是凯莱公式,用于计算 n 个顶点上的树的数量,被放置在一个由 4 个标记顶点组成的圆圈中。

美丽的图论,信奥算法,算法,图论,数据结构

使用 Figma 制作

在图论中,树只是一个没有环的图。

美丽的图论,信奥算法,算法,图论,数据结构

树在离散数学的许多现实世界应用中都很重要。从大脑中的神经元结构到机器学习中的决策树和计算机科学中的二叉搜索树

更不用说你的亲人为之自豪的传统家谱了!

美丽的图论,信奥算法,算法,图论,数据结构

图论中的树有许多应用:Pixabay |Wikimedia Commons

n 个标记顶点上的树的数量由凯莱公式 n^(n − 2) 给出。

但是为什么会这样呢?

例如,这个公式告诉我们,使用从 1 到 4 标记的顶点,应该有 16 个树。

这实际上是正确的,这 16 个树在页眉图像中显示出来。但为什么树的数量应该是 4 × 4?

如果我们有从 1 到 5 标记的顶点,为什么应该有 5 × 5 × 5 = 125 个树?

如果我们有从 1 到 6 标记的顶点,为什么应该有 6 × 6 × 6 × 6 = 1296 个树?

让我们以 6 个顶点的示例进行调查!🧐

6 × 6 × 6 × 6 是从哪里来的?这意味着我们有 6 个连续选择的选项。这些连续的 4 个选择是什么?为什么有 6 个?

这就是 Prüfer 序列发挥作用的地方。现在你终于可以欣赏标题中的双关语了 🙄🤣

Prüfer 序列是一种巧妙的方法,可以将具有 n 个顶点的任何树编码成长度为 (n − 2) 的序列,其中每个数字可以取 1 到 n 中的任何值。

下面显示了一些 Prüfer 序列及其对应的树的示例。

美丽的图论,信奥算法,算法,图论,数据结构

因为每个数字可以取 1 到 n 中的任何值,长度为 (n − 2) 的 Prüfer 序列的数量显然是 n^(n − 2)。

现在让我们解释为什么每个树都有唯一的 Prüfer 序列,反之亦然。

我们将使用上面显示的第三个示例,Prüfer 序列 {6, 6, 3, 1}。为给定的树创建 Prüfer 序列非常容易。

只需按升序连续删除树的叶子节点。树的叶子是度为 1 的顶点。

稍微正式一点:

美丽的图论,信奥算法,算法,图论,数据结构

因为我们会一直删除顶点,直到 T 的度为 2,所以这个算法必须经过 (n − 2) 次迭代,并输出一个包含 (n − 2) 个数字的列表。

下面的图表显示了从相应树中获取 Prüfer 序列 {6, 6, 3, 1} 需要的 4 个迭代。

美丽的图论,信奥算法,算法,图论,数据结构

从相应树中获取 Prüfer 序列 {6, 6, 3, 1} 需要 4 个迭代。 现在来验证每个树获得的 Prüfer 序列都是唯一的。

如果我们仔细观察这个算法,实际上我们会发现每个步骤都只有一种选择。

在每个步骤中,具有最小标签的度为 1 的顶点是唯一的。而这个顶点的邻居是唯一的,因为这个顶点的度为 1

这种唯一性意味着将树映射到 Prüfer 序列的函数是单射的(没有两个树输出相同的 Prüfer 序列)。

但为了证明 Prüfer 序列的数量等于标记树的数量,我们需要进一步证明该函数是双射的。

也就是说,我们需要证明每个 Prüfer 序列也可以映射到唯一的树。

从序列构建树的算法本质上与我们之前所做的相反,但似乎更复杂,因为我们需要输出一棵树,而不仅仅是一个数字列表。

以下是显示与 Prüfer 序列 {6,6,3,1} 相关联的唯一树所需的五个步骤的图表。

为了好玩,再来一个例子。下面的图表显示了与 Prüfer 序列 {4,3,2,1} 相关联的唯一树所需的五个步骤。

美丽的图论,信奥算法,算法,图论,数据结构

再次,通过观察算法,我们可以看到每个步骤实际上只有一种选择。在每个步骤中,必须有一个唯一的 x,它是 L 中最小的标签,必须有一个唯一的 y,它是 P 中的第一个标签。

美丽的图论,信奥算法,算法,图论,数据结构

这证明了每个 Prüfer 序列也可以映射到唯一的树,因此标记树与 Prüfer 序列之间的映射是双射的。因此,Prüfer 序列的数量等于标记树的数量,即 n^(n − 2)。

美丽的图论,信奥算法,算法,图论,数据结构

现在,Mr. Prüfer (Heinz) 是如何在 1918 年提出这个美丽而巧妙的算法的直觉呢?

Prüfer 序列在图论中具有广泛的应用场景,特别是与标记树相关。以下是一些 Prüfer 序列的应用场景:

  1. 计算树的数量: Prüfer 序列可以用来计算给定顶点数的所有可能的标记树的数量。通过使用凯莱公式(Cayley's formula) n^(n − 2),其中 n 是顶点数,可以确定树的数量。这在组合数学和图论中非常有用。

  2. 网络拓扑分析: 在计算机网络和通信领域,Prüfer 序列可以用于分析网络拓扑结构和寻找最小生成树。它有助于理解网络中的连接方式和通信路径。

  3. 生物学和神经科学: Prüfer 序列被用来分析生物学中的分子结构和神经系统的连接。在生物信息学中,它可以用于描述蛋白质或基因之间的相互作用。

  4. 编码理论: Prüfer 序列的概念与编码理论相关,可以用于设计和分析错误检测和纠正编码。

  5. 排列和组合: Prüfer 序列可用于生成排列和组合的问题,特别是在解决与图论相关的组合问题时。

  6. 数据压缩: 在一些数据压缩算法中,Prüfer 序列可以用来表示树结构,从而减少数据存储需求。

总的来说,Prüfer 序列是一个强大的工具,可用于解决多种与图论、组合数学和网络结构相关的问题。它提供了一种紧凑而有效的方式来表示和分析树形结构,因此在多个领域都有实际应用。

当进行网络拓扑分析时,通常需要使用特定的网络拓扑数据来执行各种操作,例如查找最小生成树、计算网络中的节点关系、查找环路等。下面是一个Python示例,演示如何使用NetworkX库来创建一个简单的网络拓扑图并执行一些基本的分析操作。

首先,确保您已经安装了NetworkX库。您可以使用以下命令来安装它:

pip install networkx

接下来,以下是一个Python示例代码,用于创建一个简单的网络拓扑图,并查找最小生成树以及查找节点之间的最短路径:

import networkx as nx
import matplotlib.pyplot as plt

# 创建一个空的无向图
G = nx.Graph()

# 添加节点
G.add_node("A")
G.add_node("B")
G.add_node("C")
G.add_node("D")
G.add_node("E")

# 添加边(连接节点)
G.add_edge("A", "B", weight=2)
G.add_edge("A", "C", weight=1)
G.add_edge("B", "C", weight=3)
G.add_edge("B", "D", weight=5)
G.add_edge("C", "E", weight=4)
G.add_edge("D", "E", weight=7)

# 绘制图形
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=700, node_color='skyblue', font_size=10, font_color='black')
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)

# 查找最小生成树
minimum_spanning_tree = nx.minimum_spanning_tree(G)
print("Minimum Spanning Tree Edges:")
for edge in minimum_spanning_tree.edges(data=True):
    print(edge)

# 查找节点之间的最短路径
shortest_path = nx.shortest_path(G, source="A", target="D", weight="weight")
print("Shortest Path from A to D:", shortest_path)

# 计算最短路径长度
shortest_path_length = nx.shortest_path_length(G, source="A", target="D", weight="weight")
print("Shortest Path Length from A to D:", shortest_path_length)

# 显示图形
plt.show()

这个示例首先创建了一个简单的无向图,然后添加了节点和边。接下来,它使用NetworkX库来查找最小生成树和节点之间的最短路径。

美丽的图论,信奥算法,算法,图论,数据结构

A 到 D 之间的最小生成树:D: ['A', 'B', 'D']

A 到 D 之间的最短路径是:7

详见输出👇

Minimum Spanning Tree Edges:
('A', 'C', {'weight': 1})
('A', 'B', {'weight': 2})
('B', 'D', {'weight': 5})
('C', 'E', {'weight': 4})
Shortest Path from A to D: ['A', 'B', 'D']
Shortest Path Length from A to D: 7

最后,通过matplotlib库绘制了网络拓扑图,并在图上标记了权重信息。

请注意,这只是一个简单的示例,用于演示如何使用NetworkX进行网络拓扑分析。

在实际应用中,您可能会处理更复杂的网络结构和更多的数据。根据您的具体需求,您可以进一步扩展和自定义此示例。

这对我来说是一个谜!如果您对其背后的直觉有想法,请随时留下评论。 😊文章来源地址https://www.toymoban.com/news/detail-715524.html

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

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

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

相关文章

  • 图论:一文教你读懂常见的图遍历算法

    深度优先搜索(DFS): 从一个起始节点开始,访问该节点并将其标记为已访问。 递归地访问所有与当前节点直接相连且未被访问过的节点。 重复上述步骤,直到所有节点都被访问过或没有未访问的节点。 广度优先搜索(BFS): 从一个起始节点开始,将其放入队列中,并标

    2024年04月25日
    浏览(35)
  • 【数据结构】实验六:图论

    采用邻接矩阵表示法创建无向图G ,依次输出各顶点的度。 输入格式: 输入第一行中给出2个整数i(0i≤10),j(j≥0),分别为图G的顶点数和边数。 输入第二行为顶点的信息,每个顶点只能用一个字符表示。 依次输入j行,每行输入一条边依附的顶点。 输出格式: 依次输出各顶点的

    2024年02月05日
    浏览(49)
  • NeuDs 数据结构 图论

    在一个有权无向图中,若 b 到 a 的最短路径距离是12,且 c 到 b 之间存在一条权为2的边,则 c 到 a 的最短路径距离一定不小于10。 T 解析: 我们首先来分析b-a有几种可能,首先是b到a有直接的路径,其次b通过其他的结点到达a点。 如果是b通过c点到达a点我们就可以知道,min{

    2024年02月08日
    浏览(44)
  • 【图论算法】最短路径算法(无权最短路径、Dijkstra算法、带负边值的图、无圈图)

    本篇博客将考察各种最短路径问题。     无权最短路径     Dijkstra 算法     具有负边值的图     无圈图     所有顶点对间的最短路径     最短路径的例子–词梯游戏 输入是一个赋权图:与每条边 (v i , v j ) 相联系的是穿越该边的开销(或称为值

    2023年04月12日
    浏览(43)
  • 【图论基础数据结构及其应用】

    本文主要介绍Java中图论基础数据结构的基本原理、实现方式以及使用场景。图论是研究非线性方程组及其解的数学领域,广泛应用于计算机科学中,如网络拓扑、交通网络、地理信息系统等。 图是由节点(Vertex)和边(Edge)组成的数据结构。节点表示图中的对象或实体,而

    2024年02月12日
    浏览(53)
  • 图论-图的基本概念与数据结构

    无向图 边是没有方向的,也就是双向的 结点 V = { v 1 , v 2 , . . . , v 7 } mathcal{V} = { v_1,v_2,...,v_7} V = { v 1 ​ , v 2 ​ , ... , v 7 ​ } 边 ε = { e 1 , 2 , e 1 , 3 , . . . , e 6 , 7 } varepsilon = {e_{1,2},e_{1,3},...,e_{6,7}} ε = { e 1 , 2 ​ , e 1 , 3 ​ , ... , e 6 , 7 ​ } 图 G = { V , ε } mathcal{G} = { math

    2024年02月08日
    浏览(52)
  • 期末复习(3)C语言数据结构_图论基础

    目录 导言:  定义: 一、边和度的概念: 1.1 无向图中的边和度: 1.2 有向图中的边和度: 1.3 度序列和握手定理: 二、弧和度的关系: 2.1 有向图中的弧和度: 2.2 度序列和握手定理在有向图中的应用: 2.3 邻接矩阵和邻接表在有向图中的表示: 2.4 强连通图: 三、完全图:

    2024年02月03日
    浏览(43)
  • 【C++数据结构 | 图速通】10分钟掌握邻接矩阵 & 邻接表 | 快速掌握图论基础 | 快速上手抽象数据类型图

    by.Qin3Yu 请注意:严格来说,图不是一种数据结构,而是一种抽象数据类型。但为了保证知识点之间的相关性,也将其列入数据结构专栏。 本文需要读者掌握顺序表和单链表的操作基础,若需学习,可参阅我的往期文章: 【C++数据结构 | 顺序表速通】使用顺序表完成简单的成

    2024年02月05日
    浏览(45)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(53)
  • 【算法与数据结构】--算法应用--算法和数据结构的案例研究

    一、项目管理中的算法应用 在项目管理中,算法和数据结构的应用涉及项目进度、资源分配、风险管理等方面。以下是一些案例研究,展示了算法在项目管理中的实际应用: 项目进度管理 : 甘特图算法 :甘特图是一种项目进度管理工具,它使用甘特图算法来展示项目任务

    2024年02月08日
    浏览(58)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包