Eulerian Graphs

Question 1

Definition: Eulerian Trail

Answer 1

A trail which visits every edge of a graph exactly once

Question 2

Definition: Eulerian Circuit

Answer 2

A circuit which traverses all the edges of a graph ( begins and ends at the same place)

Question 3

Definition: Eulerian Graph

Answer 3

A graph which contains a Eulerian circuit

Question 4

Property: Eulerian Graph

Answer 4

A connected multigraph is a Eulerian if and only if the degree of each vertex in G is even

Question 5

Property: Eulerian Trail

Answer 5

A connected multigraph possesses an Eulerian Trail if and only if the graph possesses exactly two odd vertices ( Where the trail begins at the one odd vertex and ends at the other)

Question 6

Algorithm: Fleury’s Algorithm

Answer 6

Fleury’s algorithm outputs an Eulerian trail (If the graph isn’t Eulerian) or circuit (If the graph is Eulerian) given a connected multigraph with at most two odd vertices

Question 7

Property: Directed Eulerian Circuit

Answer 7

A strongly connected multigraph is Eulerian if and only if the indegree and outdegree of each vertex is equal

Question 8

Property: Directed Eulerian Trail

Answer 8

A strongly connected multigraph D possesses a Eulerian Trail if and only if D has two distinct vertices u and v such that:
id(u) = od(u) + 1 and id(v) = od(v) + 1
and the id(w) = od(w) for all other vertices of D where the trail begins at u and ends at v

Question 9

Definition: Tour

Answer 9

A closed walk that traverses each edge at least once in a connected weighted graph

Question 10

Definition: Optimal Tour

Answer 10

An optimal tour is a tour of minimal weight

Question 11

Definition: Chinese Postman Problem

Answer 11

Find an optimal tour in G for a connected weighted graph G.