PENJELASAN LENGKAP DAN MUDAH DIPAHAMI MENGENAI SIRKUIT EULER DAN HAMILTON

DOWNLOAD VERSI PPT DISINI

PENJELASAN LENGKAP DAN  MUDAH DIPAHAMI MENGENAI SIRKUIT EULER DAN HAMILTON

Rinaldi M/IF2091 Strukdis 1
Lintasan dan Sirkuit Euler
• Lintasan Euler ialah lintasan yang melalui masing-masing sisi di
dalam graf tepat satu kali.
• Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu
kali..
• Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian
graph). Graf yang mempunyai lintasan Euler dinamakan juga graf
semi-Euler (semi-Eulerian graph).
Rinaldi M/IF2091 Strukdis 2
Contoh.
Lintasan Euler pada graf (a) : 3, 1, 2, 3, 4, 1
Lintasan Euler pada graf (b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3
Sirkuit Euler pada graf (c) : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1
Sirkuit Euler pada graf (d) : a, c, f, e, c, b, d, e, a, d, f, b, a
Graf (e) dan (f) tidak mempunyai lintasan maupun sirkuit Euler
(a) dan (b) graf semi-Euler
(c) dan (d) graf Euler
(e) dan (f) bukan graf semi-Euler atau graf Euler
2 1
3 4
1 2
3
4
5 6
1
2 3
4
5
6 7
a
b
e
d

PENJELASAN LENGKAP DAN  MUDAH DIPAHAMI MENGENAI SIRKUIT EULER DAN HAMILTON

c
f
a b
c d
1 2
3
4 5 e
(a) (b) (c)
(d) (e) (f)
Rinaldi M/IF2091 Strukdis 3
TEOREMA. Graf tidak berarah memiliki lintasan
Euler jika (graf semi-Euler) dan hanya jika terhubung
dan memiliki dua buah simpul berderajat ganjil atau
tidak ada simpul berderajat ganjil sama sekali.
TEOREMA. Graf tidak berarah G adalah graf Euler
(memiliki sirkuit Euler) jika dan hanya jika setiap
simpul berderajat genap.
Rinaldi M/IF2091 Strukdis 4
TEOREMA. (a) Graf berarah G memiliki sirkuit Euler jika dan hanya jika
G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar
sama.
(b) G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap
simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul,
yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan
yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.
Gambar (a) Graf berarah Euler (a, g, c, b, g, e, d, f, a)
(b) Graf berarah semi-Euler (d, a, b, d, c, b)

PENJELASAN LENGKAP DAN  MUDAH DIPAHAMI MENGENAI SIRKUIT EULER DAN HAMILTON

(c) Graf berarah bukan Euler maupun semi-Euler
a
b
c
e d
f
g
a b
d c
a b
d c
(a) (b) (c)
Rinaldi M/IF2091 Strukdis 5
Latihan
Manakah di antara graf di bawah ini yang dapat
dilukis tanpa mengangkat pensil sekalipun?
Rinaldi M/IF2091 Strukdis 6
Lintasan dan Sirkuit
Hamilton
• Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam
graf tepat satu kali.
• Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf
tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang
dilalui dua kali.
• Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton,
sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf
semi-Hamilton.

PENJELASAN LENGKAP DAN  MUDAH DIPAHAMI MENGENAI SIRKUIT EULER DAN HAMILTON

Rinaldi M/IF2091 Strukdis 7
(a) (b) (c)
(a) graf yang memiliki lintasan Hamilton (misal: 3, 2, 1, 4)
(b) graf yang memiliki lintasan Hamilton (1, 2, 3, 4, 1)
(c) graf yang tidak memiliki lintasan maupun sirkuit Hamilton
1 2
4 3
1
3
2
4
1 2
4 3
Rinaldi M/IF2091 Strukdis 8
(a) (b)
(a) Dodecahedron Hamilton,
(b) graf yang mengandung sirkuit Hamilton
Rinaldi M/IF2091 Strukdis 9
TEOREMA. Syarat cukup supaya graf sederhana G dengan
n ( 3) buah simpul adalah graf Hamilton ialah bila derajat
tiap simpul paling sedikit n/2 (yaitu, d(v)  n/2 untuk setiap
simpul v di G). (coba nyatakan dalam “jika p maka q”)
TEOREMA. Setiap graf lengkap adalah graf Hamilton.
TEOREMA. Di dalam graf lengkap G dengan n buah simpul
(n  3), terdapat (n – 1)!/2 buah sirkuit Hamilton.
Rinaldi M/IF2091 Strukdis 10

PENJELASAN LENGKAP DAN  MUDAH DIPAHAMI MENGENAI SIRKUIT EULER DAN HAMILTON

TEOREMA. Di dalam graf lengkap G dengan n buah simpul (n  3 dan n
ganjil), terdapat (n – 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada
sisi yang beririsan). Jika n genap dan n  4, maka di dalam G terdapat (n –
2)/2 buah sirkuit Hamilton yang saling lepas.
Contoh. Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada
sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota
mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari pengaturan
tersebut dapat dilaksanakan?
Jawaban: Jumlah pengaturan tempat duduk yang berbeda adalah (9 – 1)/2 = 4.
Gambar Graf yang merepresentasikan persoalan pengaturan tempat duduk.
1
2
3
5
6
7
8
9
Rinaldi M/IF2091 Strukdis 11
Beberapa graf dapat mengandung sirkuit Euler dan sirkuit
Hamilton sekaligus, mengandung sirkuit Euler tetapi tidak
mengandung sirkuit Hamilton, dan sebagainya..
(a) (b)
(a) Graf Hamilton sekaligus graf Euler
(b) Graf Hamilton sekaligus graf semi-Euler
6
5
4
1
3

PENJELASAN LENGKAP DAN  MUDAH DIPAHAMI MENGENAI SIRKUIT EULER DAN HAMILTON

2
5
1 2
4 3
Rinaldi M/IF2091 Strukdis 12
Latihan
Gambar di bawah ini adalah denah lantai dasar
sebuah gedung. Apakah dimungkinkan berjalan
melalui setiap pintu di lantai itu hanya satu kali saja
jika kita boleh mulai memasuki pintu yang mana
saja?
Rinaldi M/IF2091 Strukdis 13
Jawaban:
Nyatakan ruangan sebagai simpul dan pintu antar ruangan
sebagai sisi.
Setiap pintu hanya boleh dilewati sekali (tidak harus kembali ke
titik asal) → melewati sisi tepat sekali → lintasan Euler
Di dalam graf tersebut ada 2 simpul berderajat ganjil (simpul 1
dan 6), selebihnya genap → pasti ada lintasan Euler
Kesimpulan: setiap pintu dapat dilewati sekali saja
1
2 3
4
5 6
7
Rinaldi M/IF2091 Strukdis 14
Beberapa Aplikasi Graf
Lintasan terpendek (shortest path)
(akan dibahas pada kuliah IF3051)
Persoalan pedagang keliling (travelling
salesperson problem)
Persoalan tukang pos Cina (chinese
postman problem)

PENJELASAN LENGKAP DAN  MUDAH DIPAHAMI MENGENAI SIRKUIT EULER DAN HAMILTON

Pewarnaan graf (graph colouring)
Rinaldi M/IF2091 Strukdis 15
Persoalan Pedagang Keliling
(travelling salesperson problem (TSP)
Diberikan sejumlah kota dan diketahui jarak antar
kota. Tentukan tur terpendek yang harus dilalui oleh
seorang pedagang bila pedagang itu berangkat dari
sebuah kota asal dan menyinggahi setiap kota tepat
satu kali dan kembali lagi ke kota asal
keberangkatan.
==> menentukan sirkuit Hamilton yang
memiliki bobot minimum.
Rinaldi M/IF2091 Strukdis 16
Rinaldi M/IF2091 Strukdis 17
Aplikasi TSP:
1. Pak Pos mengambil surat di kotak pos yang
tersebar pada n buah lokasi di berbagai
sudut kota.
2. Lengan robot mengencangkan n buah mur
pada beberapa buah peralatan mesin dalam
sebuah jalur perakitan.
3. Produksi n komoditi berbeda dalam sebuah
siklus.
Rinaldi M/IF2091 Strukdis 18
Jumlah sirkuit Hamilton di dalam graf lengkap dengan n simpul: (n – 1)!/2.
Graf di atas memiliki (4 – 1)!/2 = 3 sirkuit Hamilton, yaitu:

a b
d c

PENJELASAN LENGKAP DAN  MUDAH DIPAHAMI MENGENAI SIRKUIT EULER DAN HAMILTON

12
8
15
10
5 9
a b
d c
1 2
8
1 5
1 0
a b
d c
1 2
1 5
5 9
a b
d c
1 0 8
5 9
Rinaldi M/IF2091 Strukdis 19
I
1 = (a, b, c, d, a) → bobot = 10 + 12 + 8 + 15 = 45
I
2 = (a, c, d, b, a) → bobot = 12 + 5 + 9 + 15 = 41
I
3 = (a, c, b, d, a) → bobot = 10 + 5 + 9 + 8 = 32
Sirkuit Hamilton terpendek: I
3 = (a, c, b, d, a)
dengan bobot = 10 + 5 + 9 + 8 = 32.
• Jika jumlah simpul n = 20 akan terdapat (19!)/2 sirkuit
Hamilton atau sekitar 6  1016 penyelesaian.
a b
d c
12
8
15
10
a b
d c
12
15
5 9
a b
d c
10 8
5 9
Rinaldi M/IF2091 Strukdis 20
Persoalan Tukang Pos Cina
(Chinese Postman Problem)
Dikemukakan oleh Mei Gan (berasal dari
Cina) pada tahun 1962.
Persoalan: seorang tukang pos akan mengantar surat
ke alamat-alamat sepanjang jalan di suatu daerah.
Bagaimana ia merencanakan rute perjalanannya
supaya ia melewati setiap jalan tepat sekali dan
kembali lagi ke tempat awal keberangkatan?
➔ menentukan sirkuit Euler di dalam graf
Rinaldi M/IF2091 Strukdis 21
Lintasan yang dilalui tukang pos: A, B, C, D, E, F, C, E, B, F, A.
B C
F E
8
5
A 3 D
8
2
1
6
4
4
2
Rinaldi M/IF2091 Strukdis 22
Jika graf yang merepresentasikan persoalan
adalah graf Euler, maka sirkuit Eulernya mudah
ditemukan.
Jika grafnya bukan graf Euler, maka beberapa sisi
di dalam graf harus dilalui lebih dari sekali.
Jadi, pak pos harus menemukan sirkuit yang
mengunjungi setiap jalan paling sedikit sekali dan
mempunyai jarak terpendek.
Rinaldi M/IF2091 Strukdis 23
Persoalan tukang pos Cina menjadi:
Seorang tukang pos akan mengantar surat ke alamatalamat sepanjang jalan di suatu daerah. Bagaimana ia
merencanakan rute perjalanannya yang mempunyai jarak
terpendek supaya ia melewati setiap jalan paling sedikit
sekali dan kembali lagi ke tempat awal keberangkatan?

Tweet

Postingan terkait:

— Sunday, May 31, 2020 — Add Comment — matematika