Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Struktur Diskrit : Lintasan Euler dan Hamilton beserta Contoh Soal

Introduction

1. Can we travel along the edges of a graph starting at a vertex and returning to it by traversing each edge of the graph exactly one ?

Solve by Euler circuit by examining the degree of vertices.

2. Can we travel along the edges of a graph starting at a vertex and returning to it while visiting each vertex of the graph exactly one ?

Solve by Hamiltonian circuit by examining the degree of vertices.

Euler Paths and Circuits

Discovered by Swiss Mathematician Leonhard Euler (1736). An Euler circuit in a graph G is a simple circuit containing every edge of G. An Euler path in a graph G is a simple path containing every edge of G. 

NECESSARY & SUFFICIENT CONDITIONS OF EULER PATH AND CIRCUITS

Theorem 1 : A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. 

Theorem 2 : A connected multigraph has an Euler path but not an Euler circuit if and only if its has exactly two vertices of odd degree.

EXAMPLES: Euler Paths and Circuits

Euler Circuit : G1 (a, e, c, d, b, a) 

Euler Path : G3 (a, c, d, e, b, d, a, b) 

G2 : no Euler path and Euler circuit

Applications: Euler Paths and Circuits

Seven bridge of Konigsberg problem: is it possible to start at some location at the town ( Prussia ), travel across all the bridges without crossing any bridge twice, and return to starting point ?

We can find a path or circuit that traverse : 

• Each street in a neighborhood exactly one. 
• Each road in a transportation network exactly one. 
• Each link in communication network exactly one. 

Euler path or circuit also applied in 

• Layout of circuits. 
• Network multitasking. 
• Molecular biology (DNA sequencing) 

Exercise

Which of the following graphs have an Euler Circuit? Of those that do not, which have an Euler path ?

Hamiltonian Paths and Circuits

Discovered by Irish Mathematician Sir William Rowan Hamilton (1857). A Hamiltonian circuit in a graph G is a simple circuit that passes through every vertex in G exactly once. A Hamiltonian path in a graph G is a simple path that passes through every vertex in G exactly once.

CERTAIN PROPERTIES IN HAMILTONIAN CIRCUIT (HC)

1. A graph with a vertex of degree one cannot have HC, because each vertex in HC is incident with two edges.
2. If a vertex has degree two, then both edges that are incident with this vertex must be part of any HC.
3. When a HC is being constructed and this circuit passes through a vertex, then all remaining edges incident with this vertex, other than two used in the circuit, can be removed from consideration. 
4. HC cannot contain a smaller circuit within it.

NECESSARY & SUFFICIENT CONDITIONS OF HAMILTONIAN PATH AND CIRCUIT

• The more edges a graph has, the more likely it is to have a HC. 
• Adding edges ( but not vertices ) to a graph with a HC produces a graph with the same HC.

• DIRAC’S Theorem: If G is a simple graph with n vertices with n ≥ 3 such that the degree of every vertex in G is at least n/2, then G has a HC. 
• ORE’S Theorem: If G is a simple graph with n vertices with n ≥ 3 such that deg (u) + deg (v) ≥ n for every pair of nonadjacent vertices u and v in G, then G has a HC. 

EXAMPLES

• Hamiltonian Circuit : G1 (a, b, c, d, e, a) 
• Hamiltonian Path : G2 (a, b, c, d) 
• G3 : no Hamiltonian path and Hamiltonian circuit

Applications: Hamiltonian Paths and Circuits

Icosian Games

A mathematical game invented in 1857 by William Rowan Hamilton. The game's object is finding a Hamiltonian cycle along the edges of a dodecahedron such that every vertex is visited a single time, no edge is visited twice, and the ending point is the same as the starting point. The puzzle was distributed commercially as a pegboard with holes at the nodes of the dodecahedral graph and was subsequently marketed in Europe in many forms. 

We can find a path or circuit that visits : 

• Each road intersection in a city exactly once. 
• Each place pipelines intersect in a utility grid. 
• Each node in a communications network exactly once. 

Hamiltonian path or circuit also applied in 

• Traveling salesman problem which asks for the shortest route a traveling salesman should take to visit a set of cities. 
• Gray Code : labeling the arcs of a circle such that adjacent arcs are labeled with bit strings that differ in exactly one bit. 

Exercise

Which of the following graphs have an Hamiltonian Circuit? Of those that do not, which have an Hamiltonian path ?

Sumber

Slide Strukdis : Euler dan Hamiltonian

http://informatika.unpar.ac.id/