证明可以通过将每条边变成拱形来将连通图变成强连通有向图？
Proof that you can turn a connected graph into a strongly connected digraph by turning every edge into an arch?
- 我们考虑连接的给定城市的街道网络 - 从每个路口我们都可以
到达城市中的每个其他路口（每条街道都是双向街道）。
(a) 市政厅希望将每条街道改造为单行道，这样新的街道网络
也已连接（从每个路口我们都可以到达城市中的每个其他路口）。显示
当且仅当在原始街道网络中阻塞任何
street没有断网
这是完整的问题。
任何帮助都是 appreciated:D
证明的一个方向是这样的：如果一条街道的阻塞使网络断开，那么网络就分成了A和B两部分。由于它们之间只有一条街道，所以只有一个方向A-> B 或 B->A 可以实现，但不能同时实现（这意味着如果实现了 A->B，则无法从 B 区的路口到达 A 区的路口）。所以，堵一条街一定不能断网。
证明的另一个方向是基于循环。也就是说，可以轻松地将循环转换为有向图，从而到达其中的每个节点。所以我们基本上要证明每个节点确实是一个循环的一部分。
由于这是一个编程站点，我将提供一个可以很容易地在程序中实现的答案：
简化问题：我们是否有自环或相邻路口之间的多重连接并不重要。
说服自己，图中是否有自环并不重要：它们对到达其他交汇点没有帮助，因此我们可以假设不存在这样的环。
接下来，认识到交叉点 X 和 Y 之间的双重、三重……连接也无关紧要，因为这样我们就可以将 X 和 Y 视为一个网络组件/地区，并用地区而不是陈述原始问题路口。更具体地说，通过删除这些节点 X 和 Y 并创建一个新节点 Z，该问题可以解决为一个更简单的问题，相邻节点之间没有多个连接，该节点连接到 X 和 Y 连接到的所有节点。这可以恢复，直到不存在多个连接。这个问题与原来的问题相同，因为通过指定从 X 到 Y 的至少一个方向和从 Y 到 X 的至少一个方向，以下成立：从 X 我们可以到达 Y，因此从 Y 可以到达的每个节点都可以也可以从 X 到达（反之亦然）。因此，X和Y对原问题没有区别（从每个路口我们都可以到达城市中的每个其他路口）。
现在我们来看一个自循环、无多重连接的图。
在简化的情况下：
每个节点必须至少有两个连接。不能为0，则网络无法连接。它不能有 1，因为这样连接可能会被阻止，从而断开网络连接。
这意味着结点 A 必须连接到至少两个其他结点 B 和 C。这意味着 A、B 和 C 已连接。让我们将其称为连接组 G。B 也必须至少有两个连接，其中一个是到 A 的连接。剩余的连接可以转到 G 之外的另一个连接点。在这种情况下，将新节点添加到G 和 resume 为新添加的节点。所以例如 B->D，则 G={A,B,C,D}，评估 D；使用 C->A、A->B、B->D。最终，由于这个网络中的节点数量是有限的，一个连接必须去到 G 中的另一个节点。这意味着确实至少有一个 "cycle"/"loop"（从节点 A 开始的方式并以节点 A 结束，每个连接最多使用一次）。
现在这个循环要么包含所有节点：在这种情况下，你可以庆祝，只需选择一个方向并通过你的网络，每个节点都可以到达。
或者循环只包含整个网络的一部分。在这种情况下，再次简化：删除循环路径中包含的所有节点（假设这是组 P），然后创建一个新节点 Z，其中包含来自原始组 P 的所有连接，这些连接在 P 之外。
示例：A->B->C->D->E->A 被发现是循环路径。那么P={A,B,C,D,E}。删除所有节点 A、B、C、D、E。新建一个节点Z。在原来的网络中，A<->F和A<->C也是连接。那么Z<->F必须加上，因为F不包含在P中，但是Z<->C一定不能加，因为C包含在P中（被删除了）。
出于与上述类似的原因，其余网络陈述了相同的原始问题：这是真的，因为每个节点 A、B、C、D、E（在 P 中）都可以从每个其他节点 A、B、 C,D,E 所以节点 F（在 P 之外）连接到哪个节点 A,B,C,D,E 并不重要。
由于剩余网络中的节点数因此减少并且是有限的，因此可以执行此过程直到到达每个节点，因此问题得到解决。
- 我们考虑连接的给定城市的街道网络 - 从每个路口我们都可以 到达城市中的每个其他路口（每条街道都是双向街道）。 (a) 市政厅希望将每条街道改造为单行道，这样新的街道网络 也已连接（从每个路口我们都可以到达城市中的每个其他路口）。显示 当且仅当在原始街道网络中阻塞任何 street没有断网
这是完整的问题。 任何帮助都是 appreciated:D
证明的一个方向是这样的：如果一条街道的阻塞使网络断开，那么网络就分成了A和B两部分。由于它们之间只有一条街道，所以只有一个方向A-> B 或 B->A 可以实现，但不能同时实现（这意味着如果实现了 A->B，则无法从 B 区的路口到达 A 区的路口）。所以，堵一条街一定不能断网。
证明的另一个方向是基于循环。也就是说，可以轻松地将循环转换为有向图，从而到达其中的每个节点。所以我们基本上要证明每个节点确实是一个循环的一部分。
由于这是一个编程站点，我将提供一个可以很容易地在程序中实现的答案：
简化问题：我们是否有自环或相邻路口之间的多重连接并不重要。
说服自己，图中是否有自环并不重要：它们对到达其他交汇点没有帮助，因此我们可以假设不存在这样的环。
接下来，认识到交叉点 X 和 Y 之间的双重、三重……连接也无关紧要，因为这样我们就可以将 X 和 Y 视为一个网络组件/地区，并用地区而不是陈述原始问题路口。更具体地说，通过删除这些节点 X 和 Y 并创建一个新节点 Z，该问题可以解决为一个更简单的问题，相邻节点之间没有多个连接，该节点连接到 X 和 Y 连接到的所有节点。这可以恢复，直到不存在多个连接。这个问题与原来的问题相同，因为通过指定从 X 到 Y 的至少一个方向和从 Y 到 X 的至少一个方向，以下成立：从 X 我们可以到达 Y，因此从 Y 可以到达的每个节点都可以也可以从 X 到达（反之亦然）。因此，X和Y对原问题没有区别（从每个路口我们都可以到达城市中的每个其他路口）。
现在我们来看一个自循环、无多重连接的图。
在简化的情况下：
每个节点必须至少有两个连接。不能为0，则网络无法连接。它不能有 1，因为这样连接可能会被阻止，从而断开网络连接。
这意味着结点 A 必须连接到至少两个其他结点 B 和 C。这意味着 A、B 和 C 已连接。让我们将其称为连接组 G。B 也必须至少有两个连接，其中一个是到 A 的连接。剩余的连接可以转到 G 之外的另一个连接点。在这种情况下，将新节点添加到G 和 resume 为新添加的节点。所以例如 B->D，则 G={A,B,C,D}，评估 D；使用 C->A、A->B、B->D。最终，由于这个网络中的节点数量是有限的，一个连接必须去到 G 中的另一个节点。这意味着确实至少有一个 "cycle"/"loop"（从节点 A 开始的方式并以节点 A 结束，每个连接最多使用一次）。
现在这个循环要么包含所有节点：在这种情况下，你可以庆祝，只需选择一个方向并通过你的网络，每个节点都可以到达。
或者循环只包含整个网络的一部分。在这种情况下，再次简化：删除循环路径中包含的所有节点（假设这是组 P），然后创建一个新节点 Z，其中包含来自原始组 P 的所有连接，这些连接在 P 之外。
示例：A->B->C->D->E->A 被发现是循环路径。那么P={A,B,C,D,E}。删除所有节点 A、B、C、D、E。新建一个节点Z。在原来的网络中，A<->F和A<->C也是连接。那么Z<->F必须加上，因为F不包含在P中，但是Z<->C一定不能加，因为C包含在P中（被删除了）。
出于与上述类似的原因，其余网络陈述了相同的原始问题：这是真的，因为每个节点 A、B、C、D、E（在 P 中）都可以从每个其他节点 A、B、 C,D,E 所以节点 F（在 P 之外）连接到哪个节点 A,B,C,D,E 并不重要。
由于剩余网络中的节点数因此减少并且是有限的，因此可以执行此过程直到到达每个节点，因此问题得到解决。