Euler rule what makes a network traversable

Note: These are the unique circuits on this graph. All other possible circuits are the reverse of the listed ones or start at a different vertex, but result in the same weights.

The Brute force algorithm is optimal; it will always produce the Hamiltonian circuit with minimum weight. Is it efficient? To answer that question, we need to consider how many Hamiltonian circuits a graph could have. This is called a complete graph. Suppose we had a complete graph with five vertices like the air travel graph above. From Seattle there are four cities we can visit first. From each of those, there are three choices. From each of those cities, there are two possible cities to visit next.

There is then only one choice for the last city before returning home. For N vertices in a complete graph, there will be [latex] n-1! Half of the circuits are duplicates of other circuits but in reverse order, leaving unique routes. But consider what happens as the number of cities increase:. As you can see the number of circuits is growing extremely quickly. If a computer looked at one billion circuits a second, it would still take almost two years to examine all the possible circuits with only 20 cities!

Certainly Brute Force is not an efficient algorithm. Unfortunately, no one has yet found an efficient and optimal algorithm to solve the TSP, and it is very unlikely anyone ever will. Since it is not practical to use brute force to solve the problem, we turn instead to heuristic algorithms ; efficient algorithms that give approximate solutions.

In other words, heuristic algorithms are fast, but may or may not produce the optimal circuit. We ended up finding the worst circuit in the graph! What happened? Unfortunately, while it is very easy to implement, the NNA is a greedy algorithm, meaning it only looks at the immediate decision without considering the consequences in the future.

In this case, following the edge AD forced us to use the very expensive edge BC later. Consider again our salesman. From there:. Going back to our first example, how could we improve the outcome? One option would be to redo the nearest neighbor algorithm with a different starting point to see if the result changed. This is the same circuit we found starting at vertex A.

No better. Notice that this is actually the same circuit we found starting at C, just written with a different starting vertex. The RNNA was able to produce a slightly better circuit with a weight of 25, but still not the optimal circuit in this case. The table below shows the time, in milliseconds, it takes to send a packet of data between computers on a network. If data needed to be sent in sequence to each computer, then notification needed to come back to the original computer, we would be solving the TSP.

The computers are labeled A-F for convenience. The next shortest edge is BD, so we add that edge to the graph. Notice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is ACDBA with weight While the Sorted Edge algorithm overcomes some of the shortcomings of NNA, it is still only a heuristic algorithm, and does not guarantee the optimal circuit.

The driving distances are shown below. Plan an efficient route for your teacher to visit all the cities and return to the starting location. Looking in the row for Portland, the smallest distance is 47, to Salem. Following that idea, our circuit will be:.

Using Sorted Edges, you might find it helpful to draw an empty graph, perhaps by drawing vertices in a circular pattern. Adding edges to the graph as you select them will help you visualize any circuits or vertices with degree 3. The graph after adding these edges is shown to the right. The next shortest edge is from Corvallis to Newport at 52 miles, but adding that edge would give Corvallis degree 3.

Continuing on, we can skip over any edge pair that contains Salem or Corvallis, since they both already have degree 2.

At this point, we can skip over any edge pair that contains Salem, Seaside, Eugene, Portland, or Corvallis since they already have degree 2. Crater Lk to Astoria miles. The final circuit, written to start at Portland, is:. Total trip length: miles. While better than the NNA route, neither algorithm produced the optimal route.

The following route can make the tour in miles:. Watch the example of nearest neighbor algorithm for traveling from city to city using a table worked out in the video below. A company requires reliable internet and phone connectivity between their five offices named A, B, C, D, and E for simplicity in New York, so they decide to lease dedicated lines from the phone company.

The phone company will charge for each link made. The costs, in thousands of dollars per year, are shown in the graph. In other words, we need to be sure there is a path from any vertex to any other vertex.

A spanning tree is a connected graph using all vertices in which there are no circuits. Some examples of spanning trees are shown below. Notice there are no circuits in the trees, and it is fine to have vertices with degree higher than two. Usually we have a starting graph to work from, like in the phone example above. In this case, we form our spanning tree by finding a subgraph — a new graph formed using all the vertices but only some of the edges from the original graph.

We want the minimum cost spanning tree MCST. The power company needs to lay updated distribution lines connecting the ten Oregon cities below to the power grid. How can they minimize the amount of new line to lay? We stop when the graph is connected. Skip to main content. Module 4: Graph Theory. Search for:. Euler Path An Euler path is a path that uses every edge in a graph with no repeats. Example In the graph shown below, there are several Euler paths.

Euler Circuit An Euler circuit is a circuit that uses every edge in a graph with no repeats. Example The graph below has several possible Euler circuits. A graph will contain an Euler circuit if all vertices have even degree. Example In the graph below, vertices A and C have degree 4, since there are 4 edges leading into each vertex.

Example Is there an Euler circuit on the housing development lawn inspector graph we created earlier in the chapter? Example When it snows in the same housing development, the snowplow has to plow both sides of every street.

Now we know how to determine if a graph has an Euler circuit, but if it does, how do we find one? Start at any vertex if finding an Euler circuit.

If finding an Euler path, start at one of the two vertices with odd degree. Choose any edge leaving your current vertex, provided deleting that edge will not separate the graph into two disconnected sets of edges. Add that edge to your circuit, and delete it from the graph. Try It Does the graph below have an Euler Circuit?

If so, find one. Example For the rectangular graph shown, three possible eulerizations are shown. Try It now Eulerize the graph shown, then find an Euler circuit on the eulerized graph. Example Looking again at the graph for our lawn inspector from Examples 1 and 8, the vertices with odd degree are shown highlighted.

Example One Hamiltonian circuit is shown on the graph below. Example Does a Hamiltonian path or circuit exist on the graph below? Try It. List all possible Hamiltonian circuits 2. Find the length of each circuit by adding the edge weights 3. Select the circuit with minimal total weight. Example Apply the Brute force algorithm to find the minimum cost Hamiltonian circuit on the graph below. Number of Possible Circuits. The exclamation symbol,! If so, draw one.

If not, explain why not. What about an Euler path? What if every vertex of the graph has degree 2. Is there an Euler path? An Euler circuit?

Draw some graphs. Below is part of a graph. Even though you can only see some of the vertices, can you deduce whether the graph will have an Euler path or circuit? If we start at a vertex and trace along edges to get to other vertices, we create a walk through the graph. More precisely, a walk in a graph is a sequence of vertices such that every vertex in the sequence is adjacent to the vertices before and after it in the sequence.

If the walk travels along every edge exactly once, then the walk is called an Euler path or Euler walk. If, in addition, the starting and ending vertices are the same so you trace along every edge exactly once and end up where you started , then the walk is called an Euler circuit or Euler tour. Of course if a graph is not connected, there is no hope of finding such a path or circuit. For the rest of this section, assume all the graphs discussed are connected.

There will be a route that crosses every bridge exactly once if and only if the graph below has an Euler path:. This graph is small enough that we could actually check every possible walk that does not reuse edges, and in doing so convince ourselves that there is no Euler path let alone an Euler circuit.

On small graphs which do have an Euler path, it is usually not difficult to find one. Our goal is to find a quick way to check whether a graph has an Euler path or circuit, even if the graph is quite large. It is a dead end. That is, unless you start there. But then there is no way to return, so there is no hope of finding an Euler circuit.

There is however an Euler path. You will end at the vertex of degree 3. You run into a similar problem whenever you have a vertex of any odd degree.

If you start at such a vertex, you will not be able to end there after traversing every edge exactly once. After using one edge to leave the starting vertex, you will be left with an even number of edges emanating from the vertex.

Half of these could be used for returning to the vertex, the other half for leaving. So you return, then leave. Return, then leave. The only way to use up all the edges is to use the last one by leaving the vertex. On the other hand, if you have a vertex with odd degree that you do not start a path at, then you will eventually get stuck at that vertex. The path will use pairs of edges incident to the vertex to arrive and leave again.

Eventually all but one of these edges will be used up, leaving only an edge to arrive by, and none to leave again. What all this says is that if a graph has an Euler path and two vertices with odd degree, then the Euler path must start at one of the odd degree vertices and end at the other.

In such a situation, every other vertex must have an even degree since we need an equal number of edges to get to those vertices as to leave them. How could we have an Euler circuit? The graph could not have any odd degree vertex as an Euler path would have to start there or end there, but not both. Thus for a graph to have an Euler circuit, all vertices must have even degree. The converse is also true: if all the vertices of a graph have even degree, then the graph has an Euler circuit, and if there are exactly two vertices with odd degree, the graph has an Euler path.

A graph has an Euler path if and only if there are at most two vertices with odd degree. Thus there is no way for the townspeople to cross every bridge exactly once.

This can be done. In graph theory terms, we are asking whether there is a path which visits every vertex exactly once. Such a path is called a Hamilton path or Hamiltonian path. We could also consider Hamilton cycles , which are Hamliton paths which start and stop at the same vertex.

The graph on the left has a Hamilton path many different ones, actually , as shown here:. The graph on the right does not have a Hamilton path. Note that this graph does not have an Euler path, although there are graphs with Euler paths but no Hamilton paths.

It appears that finding Hamilton paths would be easier because graphs often have more edges than vertices, so there are fewer requirements to be met.