Solution to Eulerian and Hamiltonian Graphs, Weighted Graphs A. Define the following: 1. Walk 2. Path, Trail … - Sikademy
Author Image

Archangel Macsika

Eulerian and Hamiltonian Graphs, Weighted Graphs A. Define the following: 1. Walk 2. Path, Trail 3. Cycle, Circuit B. What is Eulerian Graph? C. What is Hamiltonian Graph? D. Describe how to solve the Konigsberg Problem.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

A) 1. A walk is a sequence of vertices and edges of a graph i.e. if we traverse a graph then we get a walk.

2. A path is a trail in which neither vertices nor edges are repeated i.e. if we traverse a graph such that we do not repeat a vertex and nor we repeat an edge. Trail is an open walk in which no edge is repeated.

3. Circuit is traversing a graph such that not an edge is repeated but vertex can be repeated and it is closed also i.e. it is a closed trail. In graph theory, a cycle in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices. 

B) An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph is a cycle that uses each edge exactly once. If such a cycle exists, the graph is called Eulerian or unicursal. The term "Eulerian graph" is also sometimes used in a weaker sense to denote a graph where every vertex has even degree.

C) A Hamiltonian circuit in a graph is a closed path that visits every vertex inthe graph exactly once. Hamiltonian circuit visits each vertex in a graph exactly once but may repeat edges.

D) Leonard Euler's Solution to the Konigsberg Bridge Problem - Example

Using the Konigsberg problem has his first example Euler shows the following:

                   Number of bridges = 7, Number of bridges plus one = 8

                    Region   Bridges           Times Region Must Appear

                        A            5                                    3

                        B           3                                   2

                        C           3                                   2

                        D           3                                   2

However, 3 + 2 + 2 + 2 = 9, which is more than 8, so the journey is impossible.

Since this example is rather basic, Euler decides to design his own situation with two islands, four rivers, and fifteen bridges. The situation Euler created can be seen in Figure 3 [not available]. Euler now attempts to figure out whether there is a path that allows someone to go over each bridge once and only once. Euler follows the same steps as above, naming the five different regions with capital letters, and creates a table to check it if is possible, like the following:

                        Number of bridges = 15, Number of bridges plus one = 16

                                    Region Bridges     Times Region Must Appear

                                    A*          8                         4

                                    B*          4                         2

                                    C*          4                         2

                                    D            3                         2

                                    E            5                         3

                                    F*          6                         3

In addition, 4 + 2 + 2 + 2 + 3 + 3 = 16, which equals the number of bridges, plus one, which means the journey is, in fact, possible. Since the sum equals the number of bridges plus one, the journey must start in either D or E. Now that Euler knows it is possible to make a journey, all he needs to do is state what the path will be. Euler chooses the path EaFbBcFdAeFfCgAhCiDkAmEnApBoElD, where he includes which bridges are crossed between the letters representing the landmasses. While this information is extraneous, as the exact bridge does not matter in knowing that a journey is possible, it is useful when selecting a path. This is a good example that shows the method which Euler would use when solving any problem of this nature. 

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3615-qpid-2314