Searching graphs to solve Euler’s theorem

Question

Searching graphs to solve Euler’s theorem

Asked 8 years, 3 months ago

Viewed 252 times

3

Hello, I would like a help to do a search on a graph and check if it satisfies the theorem of Euler.

The theorem says: "A connected graph will contain an Euler cycle if, and only if, each vertex has an even number of edges impacting on it."

Then the problem boils down to finding the degree of each of the vertices of my graph, and whether it is connected.

I thought of representing my graph through an adjacency list, because as each vector will have the list of neighbors, just ask for its size minus one and get the degree of the vertex. To find out if it is connected I thought of using a DFS, so I can check as much as possible each of my neighbors in the graph.

How else can I optimize my solution suggestion?

1

What is the graph size in the average case? And in the worst case you are willing to deal with? What programming languages do you or do you not care about?

– Victor Stafusa

2016/08/24 at 16:34
Victor, I don’t have a set size. But if it were for small graphs, up to a thousand vertices for example, is my suggestion good? In what situation will my suggestion be bad? I interested in doing this in C++.

– Filipi Maciel

2016/08/24 at 16:50
For me to find out if my suggestion is good or not, I would have to do an algorithm complexity analysis, correct?

– Filipi Maciel

2016/08/24 at 16:56

1 answer

Browser other questions tagged algorithm graph

You are not signed in. Login or sign up in order to post.

by Victor Stafusa • **63,338** points · Answer 1 · 2016-08-24T17:12:44+00:00

To determine whether the graph is connected, the best approach is probably to search in width or depth. (Reference)

To count the degree of each vertex, you can use adjacency list or adjacency matrix. Both approaches consume memory $O(|v|^2)$ worst-case.

To determine whether two vertices are neighbors, you have to scroll through the adjacencies list of one of them and sequentially search for the other desired vertex there, which is fairly slow. With adjacency matrix, this can be done in constant time.

To compute the degree of a vertex, you either scroll through the entire adjacency list, or count the number of elements on the line. Both approaches have time proportional to $O(|v|)$ for each vertex, so that $O(|v|^2)$ if applied to the whole graph.

For sparse graphs where the number of edges is proportional to the number of vertices (i.e., $|e|\;\le\;k|v|$ , for some $k$ constant and small), which means that there is a fixed limit of edges incident on a vertex, the best approach is the adjacency list, because in this case, these lists will be short. For dense graphs, lists will occupy more memory than the corresponding adjacency matrix, and to find out whether two vertices $a$ and $b$ are neighbors, you will have to go through the list of adjacencies of one of them, element by element, doing a sequential search, which is quite slow.

As you want graphs with up to 1000 vertices, the adjacency matrix will have 1,000,000 entries in the worst case. Whereas you use a char[] in C++ and sizeof char That’s a little less than a pound of memory, which isn’t much. Thus, adjacency matrix seems to be a much better approach than adjacency list.

There is also an important optimization, which depends on how the graph is constructed. Assuming you have somewhere an edge list or edge generator, you should keep somewhere an array containing the degree of each vertex, so that whenever an edge is declared, you increment 1 in both corresponding positions of the array. When finished, you check whether the array contains some odd element or the zero number. If it contains odd, then it is not eulerian. If there is zero, then it is not connected (unless the graph consists of a single isolated vertex). If all elements are even and none are zero, do DFS or BFS. With this approach, it is possible to compute the degree of all vertices in time $O(|v|\;+\;|e|)$ .