Prove edges travelling algorithm
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Exercise: Let $G$ be a connected graph. Prove that using method shown below, you will traverse all graph's edges, starting from vertex $v$:
do not traverse the same edge twice in the same direction
if found vertex $xneq v$, in which we haven't been before, then mark the edge that was used to get there
use marked edge to leave $x$ only if it's the only option left
Also show that, after traversing all the edges, we return to $v$.
My tries:
I proved the second statement.
Prove: Let's assume that we don't have any possible moves left and we are in $wneq v$ vertex. For us to not be able to do any movements here, there must be $deg(w)$ used in outside direction edges. For it to be possible, we had had to use $deg(w)+1$ edges in inside $w$ direction or $w=v$, both resulting with contradiction.
My thoughts: I fought hard to prove the main statement, but nothing seems working. I am looking for a hint. From many examples it seems like algorithm will always leave the graph with all edges traversed in both directions. I saw a pattern, like if you traverse the edges in some order, then you will be returning in reversed order. There are some exceptions, when you can choose between more options (but anyway you'll be back to the reversed order or similar at least).
graph-theory algorithms
asked Sep 10 at 20:13
Gaha
657
add a comment |Â
up vote
1
down vote
favorite
Exercise: Let $G$ be a connected graph. Prove that using method shown below, you will traverse all graph's edges, starting from vertex $v$:
do not traverse the same edge twice in the same direction
if found vertex $xneq v$, in which we haven't been before, then mark the edge that was used to get there
use marked edge to leave $x$ only if it's the only option left
Also show that, after traversing all the edges, we return to $v$.
My tries:
I proved the second statement.
Prove: Let's assume that we don't have any possible moves left and we are in $wneq v$ vertex. For us to not be able to do any movements here, there must be $deg(w)$ used in outside direction edges. For it to be possible, we had had to use $deg(w)+1$ edges in inside $w$ direction or $w=v$, both resulting with contradiction.
My thoughts: I fought hard to prove the main statement, but nothing seems working. I am looking for a hint. From many examples it seems like algorithm will always leave the graph with all edges traversed in both directions. I saw a pattern, like if you traverse the edges in some order, then you will be returning in reversed order. There are some exceptions, when you can choose between more options (but anyway you'll be back to the reversed order or similar at least).
graph-theory algorithms
asked Sep 10 at 20:13
Gaha
657
Well, I think it is possible. Please take a look on the algorithm, as it is not typical euler's tour, which, as I know, exists only for graphs with even degrees.
– Gaha
Sep 10 at 20:44
Starting from a, you can go: a, b, c, d, b, d, c, a, c, b, a. There are many options to follow the algorithm in this case and all of them traverse all the edges and end in starting node.
– Gaha
Sep 10 at 20:48
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Exercise: Let $G$ be a connected graph. Prove that using method shown below, you will traverse all graph's edges, starting from vertex $v$:
do not traverse the same edge twice in the same direction
if found vertex $xneq v$, in which we haven't been before, then mark the edge that was used to get there
use marked edge to leave $x$ only if it's the only option left
Also show that, after traversing all the edges, we return to $v$.
My tries:
I proved the second statement.
Prove: Let's assume that we don't have any possible moves left and we are in $wneq v$ vertex. For us to not be able to do any movements here, there must be $deg(w)$ used in outside direction edges. For it to be possible, we had had to use $deg(w)+1$ edges in inside $w$ direction or $w=v$, both resulting with contradiction.
My thoughts: I fought hard to prove the main statement, but nothing seems working. I am looking for a hint. From many examples it seems like algorithm will always leave the graph with all edges traversed in both directions. I saw a pattern, like if you traverse the edges in some order, then you will be returning in reversed order. There are some exceptions, when you can choose between more options (but anyway you'll be back to the reversed order or similar at least).
graph-theory algorithms
asked Sep 10 at 20:13
Gaha
657
Exercise: Let $G$ be a connected graph. Prove that using method shown below, you will traverse all graph's edges, starting from vertex $v$:
do not traverse the same edge twice in the same direction
if found vertex $xneq v$, in which we haven't been before, then mark the edge that was used to get there
use marked edge to leave $x$ only if it's the only option left
Also show that, after traversing all the edges, we return to $v$.
My tries:
I proved the second statement.
Prove: Let's assume that we don't have any possible moves left and we are in $wneq v$ vertex. For us to not be able to do any movements here, there must be $deg(w)$ used in outside direction edges. For it to be possible, we had had to use $deg(w)+1$ edges in inside $w$ direction or $w=v$, both resulting with contradiction.
My thoughts: I fought hard to prove the main statement, but nothing seems working. I am looking for a hint. From many examples it seems like algorithm will always leave the graph with all edges traversed in both directions. I saw a pattern, like if you traverse the edges in some order, then you will be returning in reversed order. There are some exceptions, when you can choose between more options (but anyway you'll be back to the reversed order or similar at least).
graph-theory algorithms
graph-theory algorithms
asked Sep 10 at 20:13
Gaha
657
asked Sep 10 at 20:13
Gaha
657
asked Sep 10 at 20:13
Gaha
657
asked Sep 10 at 20:13
Gaha
657
asked Sep 10 at 20:13
Gaha
657
657
Well, I think it is possible. Please take a look on the algorithm, as it is not typical euler's tour, which, as I know, exists only for graphs with even degrees.
– Gaha
Sep 10 at 20:44
Starting from a, you can go: a, b, c, d, b, d, c, a, c, b, a. There are many options to follow the algorithm in this case and all of them traverse all the edges and end in starting node.
– Gaha
Sep 10 at 20:48
add a comment |Â
Well, I think it is possible. Please take a look on the algorithm, as it is not typical euler's tour, which, as I know, exists only for graphs with even degrees.
– Gaha
Sep 10 at 20:44
Starting from a, you can go: a, b, c, d, b, d, c, a, c, b, a. There are many options to follow the algorithm in this case and all of them traverse all the edges and end in starting node.
– Gaha
Sep 10 at 20:48
Well, I think it is possible. Please take a look on the algorithm, as it is not typical euler's tour, which, as I know, exists only for graphs with even degrees.
– Gaha
Sep 10 at 20:44
Well, I think it is possible. Please take a look on the algorithm, as it is not typical euler's tour, which, as I know, exists only for graphs with even degrees.
– Gaha
Sep 10 at 20:44
Starting from a, you can go: a, b, c, d, b, d, c, a, c, b, a. There are many options to follow the algorithm in this case and all of them traverse all the edges and end in starting node.
– Gaha
Sep 10 at 20:48
Starting from a, you can go: a, b, c, d, b, d, c, a, c, b, a. There are many options to follow the algorithm in this case and all of them traverse all the edges and end in starting node.
– Gaha
Sep 10 at 20:48
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2912295%2fprove-edges-travelling-algorithm%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Well, I think it is possible. Please take a look on the algorithm, as it is not typical euler's tour, which, as I know, exists only for graphs with even degrees.
– Gaha
Sep 10 at 20:44
Starting from a, you can go: a, b, c, d, b, d, c, a, c, b, a. There are many options to follow the algorithm in this case and all of them traverse all the edges and end in starting node.
– Gaha
Sep 10 at 20:48