时间戳

首页 > 解决方案 > 他们的这种说法有什么矛盾的吗？

graph-theory - 他们的这种说法有什么矛盾的吗？

问题描述

我说：如果我制作一个有向图 G，每个顶点恰好有一个出度和任意数量的入度，那么

1) 图最多可以有 1 个循环
2) 图 G 是连通的

如果不正确，也请提供一个反例。

如果为真，您能否提出更多可用于消除循环的图 G 属性？（注意：新顶点动态加入和离开）

我正在尝试使用 ESP32 模块为无线网络制作分散的网格形成算法。
每个有向出边都是一个连接 AP（接入点）的 STA（站）
每个顶点都是一个节点

标签： graph-theorytheorem-provingtheorem

解决方案

是的，它是真实的。但是你的意思是弱连接，没有连接。这是一个证明：

  1. 设G=(V,E)是一个有向图，假设G是弱连通的，并且至少有两个环；
  2. 令A⊂<code>V 是一个循环中的顶点集，B⊂<code>V 是第二个循环中的顶点集。A和中的每个顶点的出度B至少为一，也可能恰好为一；
  3. 为了使任何顶点 fromA到达 中的任何顶点，则需要一条从toB的边。因此，至少一个顶点的出度必须为 2。ABA

推荐阅读