| (3 intermediate revisions by 2 users not shown) | |||
| Line 8: | Line 8: | ||
---- | ---- | ||
| − | There is no Euler circuit. An Euler circuit must contain every ''edge'' in the graph. Theorem 1 says that there is an Euler circuit if and only if each vertex has an even degree | + | There is no Euler circuit. An Euler circuit must contain every ''edge'' in the graph. Theorem 1 says that there is an Euler circuit if and only if each vertex has an even degree. Actually, this only holds for undirected graphs. But if a directed graph's corresponding undirected graph does not have an Euler circuit, then neither does the directed graph (the converse is not true, see <math>H_1</math> in Figure 4 on page 634). In this graph, vertices b and c both have odd degrees (7 and 5, respectively), so there cannot be an Euler circuit in the corresponding undirected graph. Therefore, the directed graph also does not have an Euler circuit. --[[User:Mkorb|Mkorb]] 19:21, 18 November 2008 (UTC) |
| + | |||
| + | ---- | ||
| + | I agree with Mkorb. There is no Euler circuit. I was a bit confused on how counting the degrees of a directed graph works, though. In the book, it talks about degrees in counting as negative and degrees out counting as positive. Are we looking at the sum of these degrees when we check the degrees of vertices in directed graphs for evenness, or are we counting degrees as we would in an undirected graph? | ||
| + | |||
| + | ---- | ||
| + | I agree that there is no Euler circuit, but there is an Euler path, because there are only/exactly 2 verticies of odd degree (b and c). They will be the end and start points of the path. One such path would be c>b>c>e>b>d>e>a>b>f>a>f>e>f>d>c>b. Note Euler Circuit/Path is about using all the edges, not just all the verticies (you may use the verticies more than once). --[[User:Mnoah|mnoah]] 22:21, 19 November 2008 (UTC) | ||
Latest revision as of 17:21, 19 November 2008
The Euler Circuit should be : a -> b -> d -> c-> e-> f ->a.
But for Euler Path, I am still trying to figure out.
The closest I got was one of the path was not covered between C and B. This graph has 2 vertex with odd degree, it should have an Euler path.
-ngw
I agree with the Euler Circuit from ngw. There are others though, a > b > f > d > c > e > a for instance. --rtabchou
There is no Euler circuit. An Euler circuit must contain every edge in the graph. Theorem 1 says that there is an Euler circuit if and only if each vertex has an even degree. Actually, this only holds for undirected graphs. But if a directed graph's corresponding undirected graph does not have an Euler circuit, then neither does the directed graph (the converse is not true, see $ H_1 $ in Figure 4 on page 634). In this graph, vertices b and c both have odd degrees (7 and 5, respectively), so there cannot be an Euler circuit in the corresponding undirected graph. Therefore, the directed graph also does not have an Euler circuit. --Mkorb 19:21, 18 November 2008 (UTC)
I agree with Mkorb. There is no Euler circuit. I was a bit confused on how counting the degrees of a directed graph works, though. In the book, it talks about degrees in counting as negative and degrees out counting as positive. Are we looking at the sum of these degrees when we check the degrees of vertices in directed graphs for evenness, or are we counting degrees as we would in an undirected graph?
I agree that there is no Euler circuit, but there is an Euler path, because there are only/exactly 2 verticies of odd degree (b and c). They will be the end and start points of the path. One such path would be c>b>c>e>b>d>e>a>b>f>a>f>e>f>d>c>b. Note Euler Circuit/Path is about using all the edges, not just all the verticies (you may use the verticies more than once). --mnoah 22:21, 19 November 2008 (UTC)
