Proof of paths sharing a common node?

Правка en4, от mohamedeltair, 2019-09-09 01:56:55

In a directed graph, a pair of nodes $$$(a,b)$$$ is good if we have at least:

1) One path $$$x$$$ starting at a node with indegree 0 and ending at $$$a$$$.

2) And one path $$$y$$$ starting at a node with indegree 0 and ending at $$$b$$$.

Where $$$x$$$ and $$$y$$$ don't share any node. It turns out that $$$(a,b)$$$ is not good only if:

1) At least $$$a$$$ or $$$b$$$ is/are not reachable from a node with indegree 0.

2) Or all paths which start at node with indegree 0 and end at $$$a$$$ or $$$b$$$ share at least one common node.

What is the proof of the $$$2^{nd}$$$ point?

Note: The graph can be cyclic, but no self loops or parallel edges.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский mohamedeltair 2019-09-09 01:56:55 6
en3 Английский mohamedeltair 2019-09-09 00:44:10 82
en2 Английский mohamedeltair 2019-09-09 00:41:58 2 Tiny change: ' is good id we have a' -> ' is good if we have a'
en1 Английский mohamedeltair 2019-09-09 00:40:15 564 Initial revision (published)