Eulerian graphs
Eulerian graphs are graphs that contain a closed walk that includes every edge exactly once. In other words, an Eulerian graph is a graph in which a single path can traverse each edge exactly once and end at the starting point. These graphs are named after the Swiss mathematician Leonhard Euler, who first studied them in the 18th century.
3 Key excerpts on "Eulerian graphs"
eBook - ePub- Gary Chartrand(Author)
- 2012(Publication Date)
- Dover Publications(Publisher)
...▋ As a note to the preceding theorem and proof, we repeat the statement that any theorem claiming the nonexistence of some quantity, or, more generally, having some negative-sounding aspect to it, is commonly proved by a contradiction argument. The Königsberg Bridge Problem was initially solved by the famous Swiss mathematician Leonhard Euler (1707–1783). The type of trail sought in the Königsberg Bridge Problem has given rise, in a very natural way, to a class of graphs (actually multigraphs) bearing the name of Euler. A circuit containing all the vertices and edges of a multigraph M is called an eulerian circuit in M. A graph containing an eulerian circuit is called an eulerian graph, while a multigraph containing an eulerian circuit is an eulerian multigraph. The graph in Figure 3.3 is eulerian; C: u 1, u 2, u 3, u 4, u 5, u 3, u 6, u 7, u 1, u 3, u 7, u 2, u 6, u 1 is one eulerian circuit. Figure 3.3 The following theorem provides a very simple solution to the problem of determining which graphs and multigraphs are eulerian. Theorem 3.2 A multigraph G is eulerian if and only if G is connected. and every vertex of G is even. The proof of Theorem 3.2, although not extremely difficult, is somewhat lengthy. Thus, before giving the proof, we illustrate the procedure used on the eulerian graph G of Figure 3.3. Consider the vertex u 1, say. We begin a trail P at u 1 and continue the trail as long as possible. If we are fortunate, P will be an eulerian circuit; however, it may happen that we obtain the circuit P : u 1, u 2, u 3, u 6, u 7, u 1, u 3, u 7, u 2, u 6, u 1. In this case, P is not an eulerian circuit, since it does not contain all edges and vertices of G. However, u 3 is a vertex of P that is incident with edges not on P. We now begin a trail P 1, at u 3 which contains edges not belonging to P. If we continue P 1 as long as we can, one possible choice of P 1 would be...
eBook - ePub- Edward Beltrami(Author)
- 2013(Publication Date)
- Academic Press(Publisher)
...The problem now is to determine the minimum number of buses (or trucks, as the case may be) that must be employed to complete the assigned routes within a specified time period and subject to capacity constraints. We take a brief look at this in Section 4.4 for the specific situation in which garbage trucks are scheduled for refuse collection while satisfying the daily and weekly demand for garbage pickup. This is based on a study done for New York City several decades ago. 4.2 Euler Tours When Leonhard Euler solved the puzzle of the Konigsberg bridges in 1743, he unwittingly uncovered a class of problems that were to have important applications several centuries later. The town of Konigsberg, as it was then known, was located at the confluence of two branches of the River Pregel in eastern Europe, as shown in Figure 4.1 a. Note that several bridges link the mainland to the opposite banks and to the island, and the puzzle was to determine if a round-trip walking tour of the town could be carried out that passes over each of the seven bridges exactly once. Euler showed this to be impossible. To place the puzzle into a mathematical context, the map in Figure 4.1 a is replaced by a schematic in which each of the four connecting land masses are represented by a node (labeled A, B, C, or D) and the bridges are represented by edges joining the nodes, as in Figure 4.1 b. Any collection of nodes joined by edges is called a graph, and the Konigsberg puzzle can be generalized, as Euler recognized, to ask whether a round-trip tour through any connected graph (that is, without disjoint subsets of nodes) can be found that covers each edge exactly once. Euler showed that such a tour is possible if and only if the number of edges incident to any node is even. His reasoning is discussed in a moment, after a few preliminaries...
eBook - ePub- Angus Fletcher(Author)
- 2016(Publication Date)
- Harvard University Press(Publisher)
...IV Euler Discovers the First Edge Let us ask more questions about the way topology intersects with our lives, minds, and especially language, if language is understood in a Galilean fashion, reaching beyond ordinary speech to include a mathematical symbolism, but still connected to written treatises such as Galileo’s Celestial Messenger or his later Dialogue on the Two World Systems. With the Königsberg Bridges we have seen that vital changes of critical positioning—the sites where we locate points of arrival and departure, and the sequences of stopovers (some more efficacious than others) on any journey—were the subject of the original Leibnizian dream, a mathematics of position. On that view the structure Hermann Weyl mentioned in his book Symmetry is not that of abstracted symmetrical order alone; crossing a bridge is also a “real” motion that defines constraints upon any next crossing and in that way determines the graph—the line drawing, in effect—of a larger assemblage of crossings, let us say their combination into a single Eulerian Path. It is as if Euler asked himself what principle is involved when we move from one point in space to another, or as we say, we try to find our way. This is a matter of thinking more exactly about pathways, about what it means for a bridge to cross a river at an angle, reaching the other side, touching the surface of dry land beyond its ends. We speak of the edge of the river, but only before we attempt to cross it. Somehow every bridge is also an edge, but is an edge that starts from another edge, the bank of our theoretical river. So we must understand edges. Amazingly, no mathematician before Euler had ever defined the shape-making role of the cutting edges, which are basic to the Königsberg pathways...
