Eulerian Graphs and RIP

Question 1

What is a Eulerian trail?

Answer 1

Trail that visits each edge exactly once

Question 2

What is a Eulerian circuit?

Answer 2

Eulerian trail that begins and ends at same vertex

Question 3

What is the difference between a path and a trail?

Answer 3

A path is a walk with no repeating vertices
A trail is a walk with no repeating edges

Question 4

When is a graph Eulerian?

Answer 4

If and only if Degree of each vertex even
If graph contains Eulerian circuit

Question 5

When does a graph posess a eulerian trail?

Answer 5

Iff graph has exactly two vertices of odd degree. The trail must begin at once and end at other.

Question 6

What is Fleury’s algorithm used for and under which conditions?

Answer 6

Used to find Eulerian Trail to other odd vertex, given there are 2 odd neighboured vertices.

Question 7

What are the steps of Fleury’s algorithm?

Answer 7

1. Ensure graph has 0 or 2 odd v
2. If 0 odd, start anywhere. If 2, start path at any.
3. Follow edges one at a time, choosing bridge (edge which will turn destination vertex into an isolate if removed) iff only option.

Question 8

What are necessary and sufficient conditions

Answer 8

Consider events A, B
B necessary for A iff A guaranteed false if B false
B sufficient for A iff A true if B true

Question 9

How do we prove that even degrees implies a eulerian graph?

Answer 9

In notes.

Question 10

When is a strongly connected digraph Eulerian?

Answer 10

Iff indegree and out degree of each vertex is equal
Contains Eulerian circuit

Question 11

When does a graph contain a Eulerian trail?

Answer 11

iff D contains two vertices u, v such that:
- od(u) = id(u) + 1
- id(v) = od(u) + 1

and all other vertices have equal in and out degrees. Trail starts at u and ends at v

Question 12

How can we calculate the amount of pairings for k pairs of vertices?

Answer 12

Since there is always an even number of odd vertices, there are n = 2k odd vertices.
(n-1)(n-3)(n-5)…(1)

Question 13

What is the RIP and what are its steps?

Answer 13

Problem: Given connected weighted graph, find closed walk of minimum weight traversing each edge of G at least once

Steps:
1. Construct Eulerian graph by adding edges until all vertices have even degree, where added edgers are parallel to existing ones and sum of total weight is minimised.
2. Find eulerian circuit using Fleury’s algorithm