Unit 6 - The Konigsberg Bridge problem

Question 1

Walk

Answer 1

Is a sequence of adiacent nodes and their corresponding edges.

Question 2

When a walk is closed?

Answer 2

A walk is closed when the walk return to the initial node.

Question 3

Length of the walk

Answer 3

The number of edges in the walk.

Question 4

Connected graph

Answer 4

There is a path from any point to any other point in the graph.

Question 5

A graph with only one node and any number of loops is connected?

Answer 5

yes

Question 6

Directed walk in a diagraph

Answer 6

Is a walk in with all arows point in the same direction.

Question 7

Strongly conneccted diagraph

Answer 7

If for every two nodes u and v, there is a directed path from u to v and from v to u.

Question 8

Eulerian trail

Answer 8

The walk does not contain any edge twice.
The walk contains all edges of the graph.

Question 9

Eulerian circuit

Answer 9

The walk does not contain any edge twice.
The walk contains all edges of the graph.
The beginning and the end of the walk are the same.

Question 10

Eulerian graph

Answer 10

A graph containing an eulerian circuit.

Question 11

In an Eulerian graph, the degree of each node is even or odd?

Answer 11

Even

Question 12

When a connected graph is Eulerian?

Answer 12

A connected graph is Eulerian if and only if the degree of each node is even.

Question 13

When a diagraph is eulerian?

Answer 13

If it’s strongly connected and, for each node, it is true that the input degree is equal to the output degree.

Question 14

What is Hierholzer’s algorithm used for? Explain the procedure of this algorithm.

Answer 14

Hierholzer’s algorithm is used to determine Eulerian cycles in an undirected graph. Prerequisites: Connected graph that has only nodes with even degree.
1. Choose a node and construct from it a subcycle K that does not pass through any edge twice.
2. If K is an Eulerian cycle, then break off. Otherwise, continue to step 3.
3. Neglect all edges of K.
4. At the first vertex of K, let a second subcycle K2 arise which contains no edge of K and no edge of the original graph twice.
5. Insert the second circle K2 into K.
6. Continue with step 2.

Question 15

Explain the postman problem. Give two concrete examples from practice.

Answer 15

Walk all streets with minimal effort and return to starting point; examples include delivery services, street cleaning, city tour.

Question 16

Explain in simplified terms the approach to the postman problem.

Answer 16

The procedure can be summarized as follows:
1. For each pair of nodes with an odd degree, the shortest connecting path is constructed
by applying Dijkstra’s algorithm.
2. The edges of this path are doubled, so the graph no longer contains any nodes with odd
degree.
3. Since the newly created graph is Eulerian, Hierholzer’s algorithm can be used to find a
Eulerian circuit within it.