| Line 9: | Line 9: | ||
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) | 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? | ||
Revision as of 14:29, 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?
