TransWikia.com

Proof that "the last vertex in any postordering (in a DFS) of G lies in a source component of G"

Computer Science Asked by user126667 on December 25, 2020

From the book Algorithms (Jeff Erickson), there’s a lemma that states:

The last vertex in any postordering of G lies in a source component
of G

My initial reaction to this was that the proof would look something like this:

A DFS creates an acyclic directed graph.
A postordering of an acyclic directed graph is a reverse topological sort.
Say that the last vertex in a postordering of a graph G, vl, is not in the source component S.
Choose a vertex vs in the source component. Since vs is in a source component, it must be able to reach all vertices in the graph.
If vl is last in the postordering, then it is first in the topological sort of the DFS spanning tree, meaning that there exists a path from vl to any vertex after it, which must include vs. If vl can reach vs and vs can reach vl, then S must be the same component as C.

The proof in the book is not very similar, so I want to know if any part of my proof in wrong.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP