Mathematics
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.
Written by Perlego with AI-assistance
Related key terms
1 of 5
12 Key excerpts on "Eulerian graphs"
eBook - PDF- John Clark, Derek Allan Holton;;;(Authors)
- 1991(Publication Date)
- WSPC(Publisher)
Chapter 3 Euler Tours and Hamiltonian Cycles 3.1 Euler Tours Recall, from Section 1.6, that a trail in a graph G is a walk in G in which the edges are distinct, i.e., no edge of G appears in the trail more than once. A trail in G is called an Euler trail if it includes every edge of G. Thus a trail is Euler if each edge of G is in the trail exactly once. A tour of G is a closed walk of G which includes every edge of G at least once. An Euler tour of G is a tour which includes each edge of G exactly once. Thus an Euler tour is just a closed Euler trail. A graph G is called Eulerian or Euler if it has an Euler tour. For example, the graphs G and G
eBook - PDF- Jason I. Brown(Author)
- 2014(Publication Date)
- Chapman and Hall/CRC(Publisher)
By starting your “tour” at the first corner you visualizing with mathematics 129 Figure 3 . 17 : Is this graph traceable? hit along the way, you can end back up at the corner following the same path. So the tracing, if it can be done at all, can always start at a corner. But we can make the figure into a graph by placing a vertex at each corner, so we have just translated the problem into finding a trail in the graph, that starts at a vertex, and travels along the edges, from vertex to vertex, without revisiting an edge (though you can, of course, pass through a vertex more than once). Such a trail is called an Eulerian trail , named after one of the most famous mathematicians of all time, Leonhard Euler. The problem was brought to Euler’s attention by the towns-folk of Königsberg. The city had two islands that were joined to each other and to the rest of the city by seven bridges (see Figure 3 . 19 ). Couples would attempt to traverse each bridge exactly once on their outing, returning to where they started, but many, many years went by to no avail. Euler brilliantly re-alized that one could replace each land mass by a vertex, and each bridge by an edge joining the relevant vertices to form a graph—see Figure 3 . 20 (this is cited by many as one of the first instances of a graph). Then the problem of traversing the bridges of Königsberg was translated into the search for what we now call an Eulerian circuit in the graph, which is an Eulerian trail that starts and ends at the same vertex. A walk in a graph from vertex u to vertex v is a an alternating sequence of edges, starting at u and ending at v , such that each edge in the walk has a vertex in common with the next one. The walk is a trail if no edge is repeated and a path if no vertex is repeated. Figure 3 . 18 : Mathematician Leonard Euler (1707–1783).
eBook - PDF- Richard Aufmann, Joanne Lockwood, Richard Nation, Daniel K. Clegg(Authors)
- 2017(Publication Date)
- Cengage Learning EMEA(Publisher)
229 5.1 Graphs and Euler Circuits 5.2 Weighted Graphs 5.3 Planarity and Euler’s Formula 5.4 Graph Coloring The Mathematics of Graphs In this chapter, you will learn how to analyze and solve a variety of problems, such as how to find the least expensive route of travel on a vacation, how to determine the most efficient order in which to run errands, and how to schedule meetings at a conference so that no one has two required meetings at the same time. The methods we will use to study these problems can be traced back to an old recreational puzzle. In the early eighteenth century, the Pregel River in a city called Königsberg (located in modern-day Russia and now called Kalin- ingrad) surrounded an island before splitting in two. Seven bridges crossed the river and connected four different land areas, similar to the map drawn below. Many citizens of the time attempted to take a stroll that would lead them across each bridge and return them to the starting point without traversing the same bridge twice. None of them could do it, no matter where they chose to start. Try it for yourself with pencil and paper. You will see that it is not easy! In 1736 the Swiss mathematician Leonhard Euler (1707–1783) proved that it is, in fact, impossible to walk such a path. His analysis of the challenge laid the groundwork for a branch of mathematics known as graph theory. We will inves- tigate how Euler approached the problem of the seven bridges of Königsberg in Section 5.1. 5 Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.
eBook - ePub- Gary Chartrand, Ping Zhang, Ping Zhang(Authors)
- 2013(Publication Date)
- Dover Publications(Publisher)
Figure 6.2 is an Eulerian graph.An Eulerian circuit in a connected graph G is therefore a closed trail that contains every edge of G . There will also be occasions when we will be interested in open trails that contain every edge of a graph. For a connected graph G , we refer to an open trail that contains every edge of G as an Eulerian trail . For example, the graph G of Figure 6.3 contains the Eulerian trailFigure 6.3: A graph with an Eulerian trailTo understand why the adjective “Eulerian” is used here, let us go back several years, indeed a few centuries, to 17th and 18th century Switzerland, when thirteen members of the remarkable Bernoulli family became distinguished mathematicians. Among the most prominent were two brothers, Jaques and Jean, the latter also known as John or Johann. Although the accomplishments of Johann and the other Bernoullis were numerous, one of Johann’s major accomplishments may have been to convince the father of a young Leonhard Euler (pronounced OY-ler) to have his son discontinue studying theology and study mathematics instead. Later Johann Bernoulli became the mathematical advisor of Euler. When one individual serves as the academic advisor (usually doctoral advisor) of another, the advisor is referred by some as the academic father (or academic mother ) of the student. This provides a sense of “family” for teacher and student. Hence Johann Bernoulli could be called the academic father of Euler.Euler was born in Basel, Switzerland on April 15, 1707. While in his 20s, he became ill and lost vision in one of his eyes. Later, he developed a cataract in his other eye and spent the last few years of his life totally blind. However, just as the magnificent composer Ludwig van Beethoven did much of his work while totally deaf, Euler did much of his mathematical research while totally blind. During his lifetime, more than 500 research papers and books of his were published. After his death (from a stroke) on September 18, 1783, another 400 were published. At that time and for a good many years afterwards, Euler had more publications than any other mathematician, only to be exceeded in the 20th century by Paul Erd s (pronounced AIR-dish), an academic descendant of Euler. We will visit Paul Erd
eBook - PDF- Karl Smith(Author)
- 2016(Publication Date)
- Cengage Learning EMEA(Publisher)
An edge that starts and ends at the same vertex is called a loop. Euler Circuits and Hamiltonian Cycles 9.1 Copyright 2017 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 430 CHAPTER 9 The Nature of Networks and Graph Theory Czarina Catherine (1729–1796) (Catherine the Great) In 1783 Catherine II of Russia, originally named Sophie van Anhalt-Zerbst, appointed Princess Daschkoff to the directorship of the Imperial Academy of Sciences in St. Petersburg. Since women were seldom so highly honored in those days, the appointment received wide publicity. The Princess decided to begin her directorship with a short address to the assembled members of the Academy. She invited Leonhard Euler, who at the time was elderly and blind. Since Euler was then the most respected scientist in Russia, he was to have the special seat of honor. However, as the Princess sat down, a local professor named Schtelinn maneuvered into Euler’s seat. When Princess Daschkoff saw Schtelinn seating himself next to her, she turned to Euler and said, “Please be seated anywhere, and the chair you choose will naturally be the seat of honor.” This act charmed Euler and all present—except the arrogant Professor Schtelinn. Historical Note Karl Smith Library Example 2 Test traversability List the number of edges and the degree of each vertex shown in Example 1. Find the sum of the degrees of the vertices, and tell whether each network is traversable. Solution Graph Number of Edges Degree of Each Vertex Sum Traversable a. 3 2; 2; 2 6 yes b. 4 3; 2; 3 8 yes c. 5 4; 3; 3 10 yes d.
eBook - PDF- Steven G. Krantz(Author)
- 2009(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 8 Graph Theory 8.1 Introduction We learn even in high school about graphs of functions. The graph of a function is usually a curve drawn in the x -y plane. See Figure 8.1. But the word “graph” has other meanings. In finite or discrete mathematics, a graph is a collection of points and edges or arcs in the plane. Figure 8.2 illustrates a graph as we are now discussing the concept. Leonhard Euler (1707–1783) is considered to have been the father of graph theory. His paper in 1736 on the seven bridges of K¨onigsberg is con-sidered to have been the foundational paper in the subject. It is worthwhile now to review that topic. K¨onigsberg is a town, founded in 1256, that was originally in Prussia. After a stormy history, the town became part of the Soviet Union and was renamed Kaliningrad in 1946. In any event, during Euler’s time the town Figure 8.1: The graph of a function in the plane. 225 226 CHAPTER 8. GRAPH THEORY Figure 8.2: A graph as a combinatorial object. Figure 8.3: The seven bridges of K¨onigsberg. had seven bridges (named Kr¨amer, Schmiede, Holz, Hohe, Honig, K¨ottel, and Gr¨ unespanning) spanning the Pregel River. Figure 8.3 gives a simplified picture of how the bridges were originally configured (two of the bridges were later destroyed during World War II, and two others demolished by the Russians). The question that fascinated people in the eighteenth century was whether it was possible to walk a route that never repeats any part of the path and that crosses each bridge exactly once. Euler in effect invented graph theory and used his ideas to show that it is impossible to devise such a route. We shall, in the subsequent sections, devise a broader version of Euler’s ideas and explain his solution of the K¨onigsberg bridge problem in the process. 8.2. FUNDAMENTAL IDEAS OF GRAPH THEORY 227 a connected graph a disconnected graph Figure 8.4: Connected and disconnected graphs.
eBook - PDFDiscrete Mathematics
Proof Techniques and Mathematical Structures
- R C Penner(Author)
- 1999(Publication Date)
- WSPC(Publisher)
Prove that every tournament contains a directed Hamiltonian path. 104 Planarity 441 2. Prove that a connected digraph contains a directed Eulerian cycle if and only if each vertex has identical indegree and out degree. 3. Below you will find an illustration of the Pregel River in the ancient Prussian city of Konigsberg (now Kaliningrad, Russia) and of its seven bridges. Pregel River CjL M [| ^ Euler characterized graphs containing what we now call Eulerian cycles and was led to this by the puzzle of planning a walk in Konigsberg crossing each bridge once and only once. Solve the puzzle or prove there is no solution. Fleury's algorithm for producing an Eulerian path in a graph G repeatedly extends a partial Eulerian path T from its terminal vertex v by appending to T any edge incident on v which is not separating in G — T and whose removal would not isolate the initial vertex of T before all the edges of G are traversed. Prove that Fleury's algorithm succeeds in producing an Eulerian path provided that G contains an Eulerian path. Given a graph G, define its closure to be the graph obtained from G by adding to its edges additional edges between every pair of nonadjacent vertices te, v where v(u) + u(v) > v(G) (or which become so recursively as the result of adding edges). Prove that a graph admits a Hamiltonian cycle if and only if its closure admits a Hamiltonian cycle. A notoriously difficult problem in optimization theory is the following trav-eling salesman problem: Given a graph G, suppose that c : E(G) —> 1R is a cost function taking positive values. Consider a path or cycle P visiting each node of G traversing edges ei, e2,..., e n , and define the cost of P itself to be c(P) = ]C?=i c ( e *)-^ n e g ener &l problem is to find a cycle on G which visits each node and minimizes the cost. We say that the function c above is Euclidean provided c(u,v) + c(v,w) > c(ujw) for any three u^v^w G V(G).
eBook - PDF- Alan Tucker(Author)
- 2012(Publication Date)
- Wiley(Publisher)
(a) Build this graph. (b) Show how an Euler cycle (which exists for this graph) will correspond to the desired 8-digit circular sequence. (c) Find such an 8-digit circular sequence with this graph model. (d) Repeat the problem for 4-digit binary sequences. 20. Write computer programs for finding an Euler cycle, when one exists, in a multi- graph: (a) Use the method in the proof of the theorem. (b) Repeat part (a) for a directed graph. (c) Use the method in the alternative proof of the theorem. 21. Write a program to implement the algorithm in Exercise 17. 2.2 HAMILTON CIRCUITS In this section we explore Hamilton circuits and paths, circuits and paths that visit each vertex in a graph exactly once. Hamilton circuits arise in operations research problems such as routing a delivery truck that must visit a set of stores. In these 2.2 Hamilton Circuits 57 applications, the most efficient solution will be obtained by finding a minimal-cost Hamilton circuit (this problem is discussed in Section 3.4). The problem of determining whether a graph has an Euler cycle was answered by the Euler cycle theorem, which tells us that a graph has an Euler cycle if and only if all vertices have even degree and the graph is connected. Such a nice, sim- ple answer is very unusual in graph theory (which is probably why the Euler cycle theorem was the first result proved in the field of graph theory). In this sec- tion, we return to graph theory normalcy: There is no simple way to determine whether or not an arbitrary graph has a Hamilton circuit or a Hamilton path. In- deed, finding a Hamilton circuit or path in a graph is an NP-complete problem (see Appendix A.5). Finding Hamilton circuits by inspection, when they exist, is usually not too hard in moderate-sized graphs, but proving that no Hamilton circuit exists in a given graph can be very difficult.
eBook - ePub- Michel Rigo(Author)
- 2016(Publication Date)
- Wiley-ISTE(Publisher)
Homophily is the tendency for people to stay “close” to other people sharing the same characteristics (e.g. gender, ethnicity and cultural tastes), see again [EAS 10] and Schelling’s mathematical model of segregation in sociology [SCH 71, ZHA 04].Concerning Eulerian graphs, when a multigraph is not Eulerian we can try to find a closed walk of minimal length that visits every edge at least once. This problem is known as the Chinese postman problem. The number of Eulerian circuits in a connected Eulerian digraph (the situation is more difficult in the unoriented case) is given by the so-called BEST theorem named after Ehrenfest and de Bruijn [VAN 51], Tutte and Smith [TUT 41]where we recall that for an Eulerian digraph deg + (v) = deg − (v) for all v (see corollary 1.43) and tw (G) denotes the number of arborescences rooted at the vertex w. An arborescence rooted at w is a digraph where, for every vertex v, there is exactly one path from w to v. We will see in section 8.6 (and more precisely, with the concluding corollary 8.44) that tw (G) does not depend on the choice of w. As an example, consider the graph depicted in Figure 1.26 , we can check that it contains three Eulerian circuits. We have also depicted the three arborescences rooted at the bottom left vertex. Applying the above formula yields tw (G).Figure 1.26 . Number of Eulerian circuits and arborescencesDomination (definition 1.23) in graph is an important topic of its own. See, for instance, [HEN 13] for more on the subject. For general graphs, the determination of the total domination number is an NP
No longer available |Learn more- Alfred Basta, Stephan DeLong, Nadine Basta, , Alfred Basta, Stephan DeLong, Nadine Basta(Authors)
- 2013(Publication Date)
- Cengage Learning EMEA(Publisher)
All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 524 Chapter 14 23. A E H J I G F B C D © Cengage Learning 2014 24. A B C F D G H I E © Cengage Learning 2014 14.3 H AMILTONIAN P ATHS AND C IRCUITS Introduction to Hamiltonian Paths The description of a Hamiltonian path is somewhat similar to that of an Euler path, and that of a Hamiltonian circuit likewise is similar to that of an Euler circuit. A Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian circuit is a Hamiltonian path that begins and ends at the same vertex, and graphs possessing such a cycle are referred to as Hamiltonian graphs or sometimes as traceable. At present, there is no known efficient method for determining whether or not a given graph is Hamiltonian. Our first effort in the analysis of Hamiltonian graphs will be to discuss particular properties that such a graph must possess, and our second will be to produce some special graphs that are known to be Hamiltonian. In the latter case, we will see that the demonstration of “Hamiltonianicity” relies on the general concept that a graph having “enough” edges must be Hamiltonian (although, granted, the term “enough” is weak and imprecise). Conditions Necessary for a Graph to Be Hamiltonian A first condition that must hold for an undirected Hamiltonian graph is that it must be connected. That is, every pair of vertices in the graph must be capable of being connected by a path within the graph.
eBook - PDFIntroduction to Graph Theory
Solutions Manual
- Koh Khee Meng, Dong Fengming;Tay Eng Guan;;(Authors)
- 2007(Publication Date)
- WSPC(Publisher)
Chapter 6 Eulerian Multigraphs and Hamiltonian Graphs Theorem 6.1 Let G be a connected multigraph. Then G is Eulerian if and only if every vertex in G is even. Theorem 6.2 Let G be a connected multigraph. Then G is semi-Eulerian if and only if G has exactly two odd vertices. Moreover, if G is semi-Eulerian, then the two odd vertices in G are the initial and terminal vertices of any Euler trail in G . Theorem 6.3 Let G be a graph. If G is Hamiltonian, then for any non-empty proper subset S of V ( G ) , c ( G − S ) ≤ | S | . Theorem 6.4 Let G be a graph of order n ≥ 3 . If d ( v ) ≥ n/ 2 for each vertex v in G , then G is Hamiltonian. Theorem 6.5 Let G be a graph of order n ≥ 3 . If d ( u ) + d ( v ) ≥ n for every pair of non-adjacent vertices u and v in G , then G is Hamilto-nian. 173 174 Introduction to Graph Theory, Solutions Manual Exercise 6.1 Problem 1. Consider the following multigraph G of order 5. (i) Find e ( G ) . (ii) Find in G a circuit with 2 edges; with 3 edges; with 4 edges. (iii) Find in G a circuit with 5 edges that is not a cycle. (iv) Find in G a circuit with 6 edges. (v) If W is an Euler circuit in G , exactly how many edges are contained in W ? (vi) Does G contain an Euler circuit? Show one if there is. Solution . (i) e ( G ) = 8. (ii) Name the vertices as shown below: w u v x y A circuit with 2 edges : xvx . A circuit with 3 edges : uvwu . A circuit with 4 edges : xvwyx . (iii) The circuit xvuwvx is an example. (iv) The circuit uvwxywu is an example. (v) Eight ( = e ( G ) ) edges. (vi) Yes, G contains an Euler circuit, e.g. uvxvwxywu . Exercise 6.1 175 Problem 2. Five multigraphs are depicted below. Show that each of them is Eulerian by exhibiting an Euler circuit. (1) (2) (3) (4) (5) Solution . For each of the five Eulerian multigraphs, an Euler circuit is exhibited by labelling its edges as shown below.
eBook - PDFIntroduction to Graph Theory
H3 Mathematics
- Koh Khee Meng, Dong Fengming;Tay Eng Guan;;(Authors)
- 2007(Publication Date)
- WSPC(Publisher)
Chapter 6 Eulerian Multigraphs and Harniltonian Graphs 6.1 Eulerian multigraphs We introduced the Konigsberg bridge problem at the beginning of this book and, in Section 1.3, we mentioned how Euler generalized it to a much more general problem and promised you to discuss Euler’s solution in this chapter. Let us begin with the following example to recall some relevant concepts. Consider the multigraph G of Figure S.l(a) and the Example 6.1.1. following walk in G, W : xe~we4ye~we3xe7~egyegze~we~x. The ordering of the edges following the walk is shown in Figure 6.l(b). G: M’ X Figure 6.1 (i) Is there any edge repeated in W? No! No edge in W is repeated. Thus, W is a trail. 155 156 Introduction to Gmph Theory (ii) Is W a closed trail? Yes! W begins and terminates at x. Thus, W is a closed trail; that is, W is a circuit. (iii) Does W include all the edges in G? Yes! All the nine edges in G are contained in W . The features of the walk W in Example 6.1.1 remind us of the following problem studied by Euler which was introduced in Section 1.3: Let G be a multigraph. Assume that, starting with an arbitrary vertex in G, we can have a walk which passes through each edge once and only once, and then be able to terminate at the starting vertex. What can be said about G? Let G be a connected multigraph. A circuit W in G is called an Euler circuit if W contains all the edges in G. The multigraph G is called an Eulerian multigraph if G possesses an Euler circuit. Thus, in Example 6.1.1, the walk W is an Euler circuit of G, and so G is an Eulerian multigraph. Remark. In this and the next sections, we shall not confine ourselves to ‘simple graphs’. Question 6.1.1. b y exhibiting an Euler circuit. Show that each of the following multigraphs is Eulerian Is there an odd vertex in each multigraph? Question 6.1.2. odd vertices in each multigraph? Are the following multigraphs Eulerian? Are there any 6.1 Eulerian multigmphs 157
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
