3、图论中的有向图、加权图、二分图及基本定义剖析

随身带U盘

于 2025-10-24 11:34:51 发布

阅读量16

点赞数

CC 4.0 BY-SA版权

分类专栏：复杂网络：连接世界的科学文章标签：有向图加权图二分图

本文链接：https://blog.csdn.net/vscode5coder/article/details/155956564

复杂网络：连接世界的科学专栏收录该内容

56 篇文章 ¥499.90

订阅专栏¥69.90

会员秒杀 ¥9.9 重磅福利

超级会员免费看

图论中的有向图、加权图、二分图及基本定义剖析

1. 有向图、加权图和二分图的概念

在图论中，我们常常会遇到不同类型的图，以适应各种实际场景的描述需求。
- 有向图 ：
- 概念引入 ：在某些情况下，连接两个节点的顺序至关重要。例如，机场航站楼之间的穿梭巴士运行情况。一个大型机场有六个航站楼A、B、C、D、E和F，穿梭巴士按A → B → C → D → E → F → A的循环路径运行，同时A和D作为主要航站楼，还有直接往返的穿梭巴士。在这种情况下，若用普通图来表示该系统，会丢失重要信息。因此，我们引入有向图的概念。
- 定义：有向图G ≡ (N, L)由两个非空集合N和L组成。N中的元素{n1, n2, …, nN}是图G的节点，L中的元素{l1, l2, …, lK}是N中不同元素的有序对，称为有向链接或弧。例如，节点i和节点j之间的弧用有序对(i, j)表示，称该链接进入节点j且从节点i发出。这里要注意，与无向图不同，节点的顺序很重要，(i, j)和(j, i)表示不同的弧。
- 实例：以Elisa幼儿园孩子之间的友谊网络为例，通过采访孩子确定友谊关系，这种关系往往是有方向的，即孩子A可能将B视为朋友，但B不一定认为A是自己的朋友。该网络是一个有向图，有16个节点和57条弧。通过计算图的互惠性r（即网络中双向弧的数量与总弧数的比率），可以量化这种关系的相互性。在这个例子中，r = 34 / 57 ≈ 0.6，意味着只有60%的关系是相互的。
- 加权图 ：
- <