1
$\begingroup$

Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below:

enter image description here

1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in linear time ? Basically, we don't want any edges that shortcuts our visit as every vertices need to be visited.

Here is something: Such edge removal can be achieved in linear time by scanning trough all the vertices in graph in the topological order, and for every outgoing edge(a, c) of v checking if the b comes after the vertex。

How can I correctly describe that if an algorithm remove (0,1),(3,4),(1,2) edges in this graph?

$\endgroup$
7
  • 2
    $\begingroup$ You can describe it in any way you want as long as it is clear and understandable to your audience. Helping you figure out how to explain ideas clearly might be beyond the scope of this site. $\endgroup$
    – D.W.
    Apr 7, 2019 at 20:47
  • $\begingroup$ Yes, and agree, I can't even convince myself now. would like something better to describe it. $\endgroup$
    – JohnMax
    Apr 7, 2019 at 21:02
  • $\begingroup$ What you should do is to explain the meaning of "we don't want any edges that shortcuts our visit as every vertices need to be visited." What is the expected output? Is it a subset of all edges such that there is at most one path between any two vertices in the given directed graph once edges in that subset have been removed? If so, we can also remove $\{(0, 1),(3,4), (7,2) \}$. We can also remove $\{(0, 3),(3,4), (1,2) \}$. You should also specify what kind of graph is given. There are several incompatible specifications of the expected input and the expected output. $\endgroup$
    – John L.
    Apr 8, 2019 at 0:53
  • $\begingroup$ Hi @Apass.Jack, Let us say that we need to visit every vertices in a directed acyclic graph, but in this case, we don't want to traversal with the shortest paths. Instead, we would like to visit every vertices, which means we need to delete all the edges that creating shortcuts. $\endgroup$
    – JohnMax
    Apr 8, 2019 at 1:53
  • $\begingroup$ @JohnMax I know what you mean, probably more than you know what you mean, which is sort of confusing me. It might not occur to you, but there are several ambiguous places. "We would like to visit every vertex". Do you mean visiting them by following a directed path? (Note that we do not have to.) Can we visit a vertex twice? There might not be a path that goes through all vertices without repetitions. If that happens, what are we supposed to do? $\endgroup$
    – John L.
    Apr 8, 2019 at 2:09

1 Answer 1

1
$\begingroup$

Your operation replaces your graph with one of its directed spanning trees. See for example lectuire notes of Uri Zwick.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.