Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 0: Q26E (page 11)

Question: An Eulerian tourin an undirected graph is a cycle that is allowed to pass through each vertex multiple times, but must use each edge exactly once.

This simple concept was used by Euler in to solve the famous Konigsberg bridge problem, which launched the field of graph theory. The city of Konigsberg (now called Kaliningrad, in western Russia) is the meeting point of two rivers with a small island in the middle. There are seven bridges across the rivers, and a popular recreational question of the time was to determine whether it is possible to perform a tour in which each bridge is crossed exactly once. Euler formulated the relevant information as a graph with four nodes (denoting land masses) and seven edges (denoting bridges), as shown here.

Notice an unusual feature of this problem: multiple edges between certain pairs of nodes.

(a) Show that an undirected graph has an Eulerian tour if and only if all its vertices have even degree. Conclude that there is no Eulerian tour of the Konigsberg bridges.

(b) An Eulerian pathis a path which uses each edge exactly once. Can you give a similar if-and-only-if characterization of which undirected graphs have Eulerian paths?

(c) Can you give an analog of part (a) for directedgraphs?

Short Answer

Expert verified

Answer

  1. An undirected graph has a Eulerian tour if and only if all its vertices have an even degree. It is proved that there is no Eulerian tour in the Konigsberg bridges.
  2. Yes, An undirected graph with an even number of edges between every vertex has a Eurelian path.
  3. Yes. A directed graph has a Eulerian tour if two conditions are met.

Step by step solution

01

Eulerian Tour  

In an undirected graph, a Eurelian tour is a path in which all vertices are visited more than once and all edges are visited only one time.

Consider the following graph:

The Euler tour of the graph is 1,2,4,3,1

02

Proof of (a)

(a)

For an undirected graph to have a Eurelian tour, all the vertices should have an even degree. The statement can be proved as follows:

A path in a graph that contains its vertices and edges is called a walk. Generally, a graph G has verticesv0∈V ande0∈E edges . Consider the following graph:

The graph contains a Euler tour 1, 2, 3, 4, 5, 1. The degree of vertices is 2 each. Also, consider a walk from node 1 to node 5. The walk enters the vertex 1 and traverses all other vertices and edges. So, both edges of all vertices are traversed. Hence, degree of all vertices is and the graph contains a Euler tour. Similarly, every graph with Euler tour will have even degree. Hence, a graph has even degree if it contains a Eulerian tour.

Consider the given Konigsberg bridge. If there is a Eurelian tour in the bridge then every vertex has an even degree. Let a be Northern Bank, b be Big Island, c be Southern Bank and d be Small Island. The degree of each vertex is computed:

degreea=3degreeb=5degreec=3degreed=3

It is seen that no vertex has an even degree.

Hence, it is concluded that there is no Eurelian tour of the Konigsberg bridges.

03

Condition for an undirected graph to have a Eurelian path

(b)

Consider the following graphs:

  • An undirected graph with four vertices and one edge between every vertex.

Every vertex of the graph has degree which is an odd number. Therefore, it does not have a Eurelian path.

  • An undirected graph with four vertices and two edges between every vertex

Every vertex in the graph has degree which is an even number. Therefore, it has a Eurelian path.

Hence, an undirected graph with an even number of edges between every vertex has a Eurelian path.

04

Analog for directed graph

(c)

A directed graph has a Eurelian tour if it satisfies following conditions:

  • Maximum one vertex has outdegree one more than the indegreeand maximum one vertex has indegree one more than the outdegree. All the other vertices have the same outdegree and indegree.
  • Vertices with degree greater than or equal to one belong to only one connected component of the respective undirected graph.

Consider the graph:

Vertex 3 has indegree 2 and outdegree 1. Vertex 1 has indegree 1 and outdegree 2. All other vertices have indegree and outdegree equal to 1. The graph has a Euler tour 1, 2, 3, 4, 1, 3.

Therefore, a directed graph also has Eurelian tour.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Mean and median. One of the most basic tasks in statistics is to summarize a set of observations x1,x2,…,xn⊆R by a single number. Two popular choices for this summary statistic are:

• The median, which we’ll callμ1

• The mean, which we’ll callμ2

(a) Show that the median is the value of μthat minimizes the function

∑i|xi-μ|

You can assume for simplicity that is odd. (Hint: Show that for any , the function decreases if you move either slightly to the left or slightly to the right.)

(b) Show that the mean is the value of μ that minimizes the function

∑i(xi-μ)2

One way to do this is by calculus. Another method is to prove that for any μ∈R,

∑i(xi-μ)2=∑i(xi-μ2)2+n(μ-μ2)2

Notice how the function for μ2 penalizes points that are far from much more heavily than the function for μ1 . Thus μ2 tries much harder to be close to all the observations. This might sound like a good thing at some level, but it is statistically undesirable because just a few outliers can severely throw off the estimate of μ2 . It is therefore sometimes said that μ1 is a more robust estimator than μ2 . Worse than either of them, however, is μ∞ , the value of μthat minimizes the function

maxi|xi-μ|

(c) Show that μ∞ can be computed in O(n) time (assuming the numbers are xismall enough that basic arithmetic operations on them take unit time).

Is there a faster way to compute the nth Fibonacci number than by fib2 (page 4)? One idea involves matrices.

We start by writing the equations F1=F1 and F2=F0+F1 in matrix notation:


role="math" localid="1659767046297" (F1F2)=(0111).(F0F1).

Similarly,

F2F3=(0111).(F1F2)=(0111)2.(F0F1)

And in general

(FnFn+1)=(0111)n.(F0F1)

So, in order to compute Fn, it suffices to raise this 2×2 matrix, call it X, to the nth power.

a. Show that two 2×2matrices can be multiplied using 4additions and 8multiplications.

But how many matrix multiplications does it take to compute Xn?

b. Show that O(logn) matrix multiplications suffice for computing Xn. (Hint: Think about computing X8.)

Thus, the number of arithmetic operations needed by our matrix-based algorithm, call it fib3, is just O(logn), as compared to O(n)for fib2. Have we broken another exponential barrier? The catch is that our new algorithm involves multiplication, not just addition; and multiplications of large numbers are slower than additions. We have already seen that, when the complexity of arithmetic operations is taken into account, the running time offib2becomes O(n).

c. Show that all intermediate results of fib3 are O(n) bits long.


d. Let M(n)be the running time of an algorithm for multiplying n-bit numbers, and assume that M(n)=O(n2) (the school method for multiplication, recalled in Chapter 1, achieves this). Prove that the running time of fib3 is O(M(n)logn).


e. Can you prove that the running time of fib3 is O(M(n))? Assume M(n)=Θ(na)for some 1≤a≤2. (Hint: The lengths of the numbers being multiplied get doubled with every squaring.)


In conclusion, whether fib3 is faster than fib2 depends on whether we can multiply n-bit integers faster thanO(n2) . Do you think this is possible? (The answer is in Chapter 2.) Finally, there is a formula for the Fibonacci numbers:

role="math" localid="1659768125292" Fn=15(1+52)n−15(1−52)n.

So, it would appear that we only need to raise a couple of numbers to the nth power in order to computeFn . The problem is that these numbers are irrational, and computing them to sufficient accuracy is nontrivial. In fact, our matrix method fib3 can be seen as a roundabout way of raising these irrational numbers to the nth power. If you know your linear algebra, you should see why. (Hint: What are the eigenvalues of the matrix X?)

Show that, if c is a positive real number, then g(n) = 1 + c + c2 + · · · + cn is:

(a) Θ(1) if c < 1.

(b) Θ(n) if c = 1.

(c) Θ(cn) if c > 1.

The moral: in big-Θ terms, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the series is unchanging.

The tramp steamer problem. You are the owner of a steamship that can apply between a group of port cities V . You make money at each port: a visit to city i earns you a profit of pi dollars. Meanwhile, the transportation cost from port i to port j is cij>0 .You want to find a cyclic route in which the ratio of profit to cost is maximized.

To this end, consider a directed graph G=(V,E) whose nodes are ports, and which has edges between each pair of ports. For any cycle C in this graph, the profit-to-cost ratio is

role="math" localid="1658920675878" r(c)=∑i,jicPij∑i,jicCij

Let r' be the maximum ratio achievable by a simple cycle. One way to determine r' is by binary search: by first guessing some ratio r , and then testing whether it is too large or too small. Consider any positive r>0 . Give each edge (i,j) a weight of wij=rcij-pj .

  1. Show that if there is a cycle of negative weight, then .
  2. Show that if all cycles in the graph have strictly positive weight, then r<r*.
  3. Give an efficient algorithm that takes as input a desired accuracy ∈>0 and returns a simple cycle c for which r(C)3r*-∈ Justify the correctness of your algorithm and analyze its running time in terms of |V|,∈ and R=max(i,j)iE(PJCIJ) .

Here’s a problem that occurs in automatic program analysis. For a set of variablesx1,......,xn, you are given some equality constraints, of the form “ xi=xj” and some disequality constraints, of the form “ xi≠xj.” Is it possible to satisfy all of them?

For instance, the constraints.

x1=x2,x2=x3,x3=x4,x1≠x4

cannot be satisfied. Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied.
See all solutions

Recommended explanations on Computer Science Textbooks

Databases

Read Explanation

Algorithms in Computer Science

Read Explanation

Theory of Computation

Read Explanation

Data Representation in Computer Science

Read Explanation

Problem Solving Techniques

Read Explanation

Computer Organisation and Architecture

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free