![Tugas Individu Graph: Program Pascasarjana Universitas Negeri Padang 2020 [PDF]](https://pdfs.asia/img/200x200/tugas-individu-graph-program-pascasarjana-universitas-negeri-padang-2020.jpg)
3 0 1 MB
TUGAS INDIVIDU GRAPH
Oleh: Zul Futria Wati NIM.19205060
Dosen Pembimbing: Dr. ARMIATI, M.Pd
PROGRAM PASCASARJANA UNIVERSITAS NEGERI PADANG 2020
SOAL HAL 20 - 26 1. Gambarlah graph G = (V(G), E(G)) bila diketahui V(G) dan E(G) sebagai berikut: a. V(G)=
b. V(G)=
, , ,
,
c. V(G)= , ,
,
,
dan E(G)=
,
,
,
dan E(G)=
dan E(G)=
,
,
,
,
,
,
,
2. Gambarlah graph komplit dengan 7 titik. Kemudian tentukan, panjang sikel yang mungkin terdapat pada graph tersebut. Apakah graph ini grpah Hamilton? Graph Euler? Jawab:
3. Manakah dari graf-graf berikut yang bipartisi?
Graf Bipartisi
Graf Bipartisi
Graf Bipartisi
4. Perhatikan graph G di bawah ini.
a. Cari sebuah jalan tertutup dengan panjang 9.
,
,
,
,
,
,
,
,
,
,
,
,
b. Cari sebuah jejak terbuka dengan panjang 9.
,
,
,
,
,
c. Cari sebuah jejak tertutup dengan panjang 7.
,
,
,
d. Cari sebuah lintasan dari titik
,
,
ke titik
ke titik
,
e. Cari panjang sikel terpanjang dalam G.
,
,
,
,
,
.
,
,
,
f. Berapakah panjang lintasan terpanjang di graph G?
,
,
,
,
,
13
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
g. Cari sebuah graph bagian bukan rentang dari G. Graph bagian bukan rentang yaitu graph bagian yang tidak memuat seluruh titik pada graph dasar.
h. Cari sebuah graph bagian rentang dari G yang tak terhubung.
Graph bagian rentang jika V(H) = V(G)
i. Cari graph bagian g yang dibangun oleh
,
5. Gambarlah sebuah graph G yang: a. Mempunyai 5 titik, tanpa sikel, dan terhubung.
b. Mempunyai 6 titik, dua komponen.
,
,
,
,
,
c. Mempunyai 10 titik, 8 sisi, 3 komponen, dan tepat 1 sikel.
6. (a).Apakah graph sederhana dengan satu titik terhubung? (b) Apakah ada graph sederhana dengan 10 titik dan 46 sisi? (c) Apakah ada graph dengan 15 titik, 10 sisi dan 4 komponen? Jawab: (a) tidak, karena dari definisi graph sederhana adalah graph yang tidak mempunyai sisi rangkap dan tidak memiliki gelung
(b) Ada
(c) tidak ada karena berdasarkan Definisi 1: sebuah graph G dikatakan terhubung jika untuk setiap dua titik u dan v di G terdapat lintasan di G yang menguhubungkan kedua titik tersebut, sebaliknya graph G disebut graph tak terhubung.
Definisi 2: sebuah komponen dari graph G adaalh sebuah graph bagian terhubung maksimal (titik dan sisi) dari G. Jadi, setiap graph terhubung memiliki satu komponen sedangkan graph tak terhubung memiliki lebih dari satu komponen ≤
7. (a) Jika G graf bipartisi sederhana dengan n titik dan m sisi buktikan bahwa
(b). bila kata “sederhana” dalam pernyataan (a) kita hapus, apakah pernyataan baru tetap benar ? jelaskan! Jawaban : a. Pada graf bipatrisi, sederhana dan dengan n titik, kita bisa mempartisi n titik tersebut dalam himpunan bagian (beranggotakan titik pada graf) dengan ukuran i dan n-i , 0≤
≤
. Sisi yang dimiliki juga harus menghubungkan titik pada himpuna yang
satu ke titik pada himpunan yang lain. Jadi, maksimum sisi yang mungkin adalah ( − ) sisi (terjadi ketika setiap titik pada himpunan yang satu terhubung ke setiap
titik pada himpunan yang lain, atau disebut graf bipartisi lengkap). Jadi, kita dapat tuliskan sebagai suatu fungsi =
−
,0 ≤
≤
akan maksimum saat = , sehingga jumlah maksimum sisinya adalah
−
=
−
=
Jadi terbukti bahwa graf bipartisi, sederhana , dan dengan n titik , tidak mempunyai lebih dari
sisi.
b. Tidak, karena graf sederhanya menjadi syarat benarnya pernyataan
≤
8. Jika G graph bipartisi, tunjukkan bahwa setiap sikel di G panjangnya genap. Tunjukkan bahwa konversi pernyataan ini juga benar. Jawab : Sikel adalah jalan tertutup yang memuat sisi yang berbeda. Misalkan diberikan graph bipartisi G. Andaikan graph ini memiliki setidaknya satu sikel ganjil sehingga partisi himpunan titiknya dapat ditulis sebagai
=
,
,
, . . . dan
,
,
terjadi adalah
, . . . . Karena sikelnya memiliki panjang ganjil, maka jalan yang dapat
Jelas bahwa
dan
,
,
,...,
untuk suatu n bilangan bulat positif.
(ganjil) berada dalam himpunan partisi yang sama, yaitu
.
Akibatnya graph tersebut bukan graph bipartisi (karena terpaksa harus dibuat sisi yang menghubungkan kedua titik tersebut agar menjadi jalan tertutup). Jadi, pengandaian salah. Maka haruslah graph bipartisi memiliki sikel dengan panjang genap.
9. Perhatikan graph G pada soal nomor 4 sebagai berikut:
a. Tentukan derajat titik dari setiap titik G. d(v1)=1 d(v2)=1 d(v3)=3 d(v4)=3 d(v5)=2 d(v6)=4 d(v7)=4 d(v8)=3 d(v9)=3 d(v10)=2 d(v11)=4 d(v12)=2 d(v13)=4 d(v14)=1 d(v15)=1
b. Tentukan
dan ∆
!
= derajat titik minimum = 1
∆
= derajat titikk maksimum = 4
c. Ada berapa titik G yang berderajat ganjil? (v1, v2, v3, v4, v8, v9, v14, v15), ada 8 titik yang berderajat ganjil.
10. (a). Berapa derajat titik-titik pada graph komplit Kn ? Apakah Kn graph beraturan? (b) Adakah graph beraturan-3 dengan 9 titik? Mengapa? (c) Berapakah banyak sisi dari graph beraturan-k dengan n titik? Jawab: (a) n titik. Iya karena, Kn merupakan graph komplit dengan n titik adalah graph beraturan (n-1) (b) tidak ada, karena ada titik yang tidak berderajat tiga. (c) banyak sisi =
×
11. Misalkan G adalah graf beraturan dengan 40 sisi. Berapakah banyaknya titik G? Jawab: Lemma jabat tangan:
d (v) = 2│E│ vV
d (v) = 2 . 40 = 80 vV
Setiap titik berderajat sama yaitu berderajat r, dan jika n adalah jumlah titik pada graf tersebut, maka: nr = 80 Jumlah titik pada graf sederhana tersebut adalah n = 80 / r,
r > 0 dan r Z positif dan habis membagi 80
Untuk r = 1, maka n = 80; akan terbentuk graf tidak terhubung yang masingmasing simpulnya berderajat 1, jumlah sisinya adalah 80/2 = 40 (memenuhi)
Untuk r = 2, maka n = 40, akan terbentuk graf lingkaran dengan sisi 40 (memenuhi)
Untuk r = 3, 6, 7, 9 tidak mungkin sebab hasil pembagian (40/r) tidak bulat.
Untuk r > 2, maka graf sederhana dapat terbentuk jika jumlah sisinya kecil dari jumlah sisi graf lengkap dengan derajat r. Jika lebih maka graf tersebut bukanlah graf sederhana.
r (derajat)
n (titik)
Maksimum sisi yang diizinkan agar terbentuk graf sederhana
Keterangan
Memenuhi sebab 40 ≤ 90 Memenuhi sebab 40 ≤ 5 16 16.7 / 2 = 56 56 Tidak memenuhi 8 10 10.4 / 2 = 20 sebab 40 > 20 Tidak memenuhi 10 8 8.3 / 2 = 12 sebab 20 > 12 ... ... ... ... *) Untuk r yang lebih besar lagi tidak akan mungkin lagi terbentuk graf sederhana 4
20
20.9 / 2 = 90
sebab jumlah simpulnya akan lebih kecil sehingga maksimum sisi yang diizinkan juga semakin kecil. Jadi r yang memenuhi adalah {1, 2, 4, 5}, dan jumlah titik di dalam graf adalah {80, 40, 20, 16}.
12. Sebuah graph G mempunyai 20 sisi. Jika setiap titik di G mempunyai derajat paling sedikit 4, tentukan maksimum banyaknya titik G. Jawab : Setiap titik berderajat sama yaitu paling sedikit 4, artinya graph teratur. Jumlah sisi pada graph teratur berderajat r adalah
=
, jadi
=
Untuk r = 4, jumlah titik yang dapat dibuat adalah maksimum, yaitu Jadi, jumlah maksimum banyaknya titik adalah 10.
=
=
(
)
=
= 10
13. (a). Mungkinkah dalam suatu pesta yang dihadiri 21 orang masing-masing yang hadir bersalaman dengan tepat 5 orang yang lain? JAWABAN: Jika setiap orang yang hadir dalam pesta itu dianggap sebagai titik, maka setiap orang tepat bersalaman dengan 5 orang (diilustrasikan sebagai sisi pada graph), hal ini sama saja dengan setiap titik berderajat 5. Kita fokuskan pikiran kita bahwa ilustrasi orang
yang hadir itu adalah sebuah graph G, maka sebuah graph G tersebut memiliki jumlah derajat titik sebanyak = 21x5=105. Karena jumlah derajat titiknya bernilai ganjil, maka TIDAK MUNGKIN setiap orang berjabatan tangan tepat dengan 5 orang, karena juga hal ini bertentangan dengan LEMMA JABAT TANGAN bahwa banyaknya titik yang berderajat ganjil adalah genap, sehingga seharusnya jumlah orang yang hadir di pesta itu seharusnya sebanyak genap (bukan 21 orang).
(b). Apakah benar dalam suatu pesta banyaknya orang yang telah berjabatan tangan sebanyak ganjil adalah genap? Mengapa? Ya benar karena hal ini sesuai dengan bunyi “AKIBAT LEMMA JABAT TANGAN” bahwa Banyaknya titik yang berderajat ganjiil dalam suatu graph adalah genap. Dimana, orang dalam pesta itu dimisalkan sebagai titik pada sebuah graph, sedangkan banyaknya berjabatan setiap orang dimisalkan sebagai sisi pada sebuah graph.
14. Tunjukkan bahwa jika G adalah graph yang mempunyai tepat dua titik berderajat ganjil, maka kedua titik yang berderajat ganjil tersebut harus terletak pada komponen yang sama. Jawab : V1
V3 V4
V2 V2 berderajat ganjil ; d(V2) = 3 V1, V3, V4 berderajat ganjil ; d(V1) = d(V3) = d(V4) = 1 Titik-titik tersebut berada pada komponen yang sama (Terbukti)
15. Jika G adalah graf sederhana dengan paling sedikit dua titik, maka G memiliki paling sedikit dua titik yang berderajat sama. Buktikan! Jawaban:
Misalnya graf sederhana itu memiliki n titik, dengan
1, tetapi perhatikan bahwa ketika ada
maka deraja maksimum yang mungkin adalah 1 buah titik yang memiliki derajat derajat titik lainnya haruslah
2,
2. Karena ada n titik berbeda,
1, maka tidak ada titik yang berderajat 0 dan
3, … , 3, 2, 1. Padahal ada n titik berbeda dalam
kasus ini, sehingga pastilah setidaknya ada 1 titik yang memiliki derajat yang sama dengan titik lainnya. Contoh misalnya ada graf sederhana dengan 4 titik . , , ,
, degan 2 dan
ambil
3. Ini berakibat tidak ada titik berderajat 0. Agar berbeda, 1. Karena
0, maka derajat titik d yang mungkin
adalah 1, 2, atau 3 (derajatnya sama dengan titik lain).
16. Buktikan bahwa jika G adalah graph sederhana dengan derajat minimum δ ≥ 2, G memuat sikel yang panjangnya paling sedikit δ+1. Jawab : G adalah graph sederhana dengan derajat minimum δ ≥ 2
17. Jika G sebuah graph dengan n titik, m sisi, dan k komponen, maka tunjukkanlah bahwa ! Jawaban: Sebuah graph G dikatakan terhubung jika untuk setiap dua titik G yang berbeda terdapat sebuah lintasan yang menghubungkan kedua titik tersebut. Sebaliknya graph G disebut tidak terhubung. Sebuah komponen graph G adalah sebuah graph bagian terhubung maksimal (titik dan sisi) dari G. Graph H dikatakan graph bagian terhubung maksimal dari graph G, jika tidak ada graph bagian lain dari G yang terhubung dan memuat H. Jadi setiap graph terhubung memiliki tepat satu komponen sedangkan graph tak terhubung memiliki paing sedikit dua komponen.
Perhatikan graph G pada gambar (a) merupakan graph terhubung karena setiap dua titik yang berbeda di g dihubungkan oleh sebuah lintasan. Sedangkan, graph H pada gambar (b) merupakan graph tidak terhubung, karena tidak ada lintasan dari V1 ke V6 di H. Dalam hal ini G1, G2, G3 adalah kompenen-komponen H. Sehingga dari contoh tersebut dapat tertunjukkan bahwa :
.
18. Jika G graph sederhana dengan paling sedikit 6 titik, maka G atau memeuat graph komplit K3. Buktikan! 19. Tunjukkan bahwa jika G graf sederhana, maka G graf terhubung Jawaban: Graf sederhana adalah graf yang tidak memiliki gelung dan tidak memiliki sisi rangkap. Sebuah graf G dikatakan terhubung jika untuk setiap dua titik u dan v di G terdapat lintasan di G yang menghubungkan kedua titik tersebut, jika sebaliknya graf G dikatakan graf tak terhubung. Karena persyaratan suatu graf G dikatakan terhubung telah terpenuhi oleh graf sederhana maka dapat dikatakan jika G graf sederhana maka G graf terhubung.
20. Sebuah graph G yang isomorfik dengan Ğ disebut graph komplemen-diri ( selfcomplementary graph). a) Beri contoh graph komplemen diri dengan 4 titik ; 5 titik. b) Tunjukkan jika G graph komplemen diri dengan n titik, maka
Jawab :
1
4 .
0
4 atau
a. Graph komplemen diri adalah graph yang komplemennya sama dengan isomorfiknya. Contoh : Graph komplemen diri dengan 4 titik
Graph komplemen diri dengan 5 titik
21. Apakah barisan-barisan berikut merupakan barisan derajat sebuah graph? Kalau ya, coba gambarkan graphnya! Jawaban: Suatu barisan bilangan bulat non negatif dikatakan merupakan barisan derajat sebuah graph jika jumlah barisan bilangan bulat non negatif itu bernilai genap. a.
6,5,4,3,3,2,2,2
6
5
4
3
3
2
2
2
27 Karena bernilai ganjil maka ini bukan barisan
3
2
1
0
22 Karena bernilia GENAP maka ini Barisan
derajat sebuah graph.
b.
5,4,4,3,3,2,1,0
5
4
4
3
Derajat Sebuah Graph.
c.
3,3,3,3,3,3,3,3,3,3
3
3
3
3
3
3
3
3
3
3
2
1
0
21 Karena bernilai ganjil maka ini bukan barisan
Barisan Derajat Sebuah Graph
d.
5,4,3,3,3,2,1,0
5
4
3
3
derajat sebuah graph.
3
30Karena bernilia GENAP maka ini
22. Apakah barisan berikut merupakan graphik? Jika ya, konstruk graphnya! a) (5,4,3,3,3,3,3) b) (5,5,3,3,2,2,2) Jawab: a) (5,4,3,3,3,3,3) Perhatikan bahwa banyaknya bilangan pada S = 5, 4, 3, 3, 3, 3, 3 adalah 7. Jelas bahwa n = 7
1. Tampak pula bahwa S tidak memuat bilangan yang lebih dari 5 dan
tidak semua bilangannya 0, serta tidak ada bilangan negatif. S sudah terurut berupa bilangan monoton turun, sehingga langkah selanjutnya adalah sebagai berikut S = 5, 4, 3, 3, 3, 3, 3 (eksekusi 5 dan dikurangi 5 bilangan disampingnya dengan 1) S1 = 4 3 3 3 3 3 -1 Tampak bahwa S1 =memuat bilangan negatif, sehingga S1 bukan grafik. Jadi, S juga bukan grafik. b) (5,5,3,3,2,2,2) Perhatikan bahwa banyaknya bilangan pada S = 5, 5, 3, 3, 2, 2, 2 adalah 7. Jelas bahwa n = 7
1. Tampak pula bahwa S tidak memuat bilangan yang lebih dari 5 dan
tidak semua bilangannya 0, serta tidak ada bilangan negatif. S sudah terurut berupa bilangan monoton turun, sehingga langkah selanjutnya adalah sebagai berikut \
S = 5, 5, 3, 3, 2, 2, 2 (eksekusi 5 dan dikurangi 5 bilangan disampingnya dengan 1) S1 = 3 3 2 2 2 1 (ekesekusi 3 dan kurangi 3 bilangan dismpingnya denan 1) S2 = 2 2 2 0 (eksekusi 2 dan dikurangi 2 bilangan disampingya dengan 1 S3 = 0 0 Tampak bahawa S3 yang hanya memuat bilangan 0. Sehingga S3 grafik. Jadi S juga grafik
23. Gambarlah graf G dengan matriks berhubungan langsung sebagai berikut
24. Tulis matriks berhubungan langsung dan matriks keterkaitan dari graph berikut.
Jawab : Matriks berhubungan langsung dari graph G. 2 3 0 0
Matriks keterkaitan dari graph G.
3 0 3 1
0 3 1 1
0 1 1 2
Banyak kolom = banyak sisi = 13 Banyak baris = banyak titik = 4 2 0 0 0
2 0 0 0
1 1 0 0
11 11 00 00
0 1 1 0
00 11 10 01
0 1 1 0
0 0 2 0
0 0 1 1
0 0 00 00 22
25. Misalkan G graph bipartisi. Tunjukkan bahwa matriks berhubungan langsung dari G dapat ditulis dalam bentuk:
dengan O, P, dan Q adalah sub-sub matriks. O sub matriks yang setiap unsurnya nol, sedangkan P adalah sub matriks yang elemennya transopse dari sub matriks Q. Jawaban: Perhatikan gambar graph ,
matriks keterkaitannya adalah: 1 1 0 0 Perhatikan jumlah semua unsur titik
1 1 0 0
1 1 0 0
0 1 1 0
0 1 0 1
0 0 1 1
0 0 0 2
yang terletak di baris
di graph G, sedangkan jumlah semua unsur
selalu 2.
0 0 1 1
menyatakan derajat dari
yang terletak di suatu kolom
1. Jumlah unsur
yang terletak pada baris 1 menyatakan derajat
di graph G
adalah 3. Jumlah unsur titik
yang terletak pada baris ke 2 adalah 5. Ini menyatakan derajat
adalah 5.
26. Misalkan G adalah graph sederhana dan A adalah matriks berhubungan langsung dari G. Buktikan bahwa, unsur-unsur A2 yang terletak di diagonal utama menyatakan derajat dari titik-titik G. Apakah pernyataan tersebut masih benar jika G bukan graph sederhana? 27. Buktikan bahwa, barisan bilangan bulat non negatif (d1, d2, ..., ) adalah barisan derajat sebuah graf jika dan hanya jika ∑
Jawaban:
⟹Misal G adalah graph dengan non negatif {v1, v2, ..., vn} dan d(vi) = di, 1< i < n. Menurut Lemma jabat tangan ∑ non negatif, maka ∑
= ∑
= 2 | ( )|. Karena | ( )| bilangan bulat
= 2| ( )|.
⟸Karena ∀ i, di bilangan nulat non negatif dan ∑
bilangan genap, maka banyaknya
suku dalam barisan d = (d1, d2, ..., dn) yang bernilai ganjil adalah genap. Konstruksi graph G dengan V(G) = {v1, v2, ..., vn} dan barisan derajat d sedemikian sehingga d(vi) = di∀ I {1, 2, ..., n} sebagai berikut: Konstruksi
dengan
= {v1, v2, ..., vn}.
Korespondensi vi dengan di. ∀ I
{1, 2, ..., n}. Hubungkan dengan sebuah sisi setiap titik pada
yang
berkorespondensi dengan suku barisan d yang bernilai ganjil. Sebut graph ini dengan H. Bentuk graph G dari H dengan menambahkan sebanyak
gelung pada setiap
titik vi, i {1, 2, ..., n}. Maka barisan bilangan bulat non negatif (d1, d2, ..., dn} adalah barisan derajat dari sebuah graph.
28. Misalkan
=
,
,...,
Buktikan bahwa, barisan 1, . . . ,
Jawab : Bukti kanan
− 1,
barisan bilangan bulat non negatif monoton turun. graphik jika dan hanya jika barisan
, . . . ,
graphik.
− 1,
−
Karena d = {d1, d2, d3, ..., dn} graphik maka ada graph sederhana G dengan barisan derajat . Misalkan V(G) = {v1, v2, ..., vn}. d berkorespondensi satu-satu dengan vi; i ;
dG (vi) ={ ;
dimana i
{1, 2, ..., n} dan
{1, 2, ..., n}
|2 ≤
≤
⊆ ( )
Konstruksi graph H dari G sedemikian sehingga V(H) = V(G) – {v1} dan |2 ≤
E(H) = E(G) –
≤
Karena G graph sederhana maka graph H juga graph sederhana, akibatnya ;
dH (vi) ={ ;
Sehingga terbentuk barisan 1,
,
dimana i
{1, 2, ..., n}
, yakni
= (d2 – 1, d3 – 1, d4 – 1, ...,
−
, ..., dn) yang merupakan barisan derajat sederhana H. Dengan kata
lain d1 adalah graphik.
Karena
− 1,
= (d2 – 1, d3 – 1, d4 – 1, ...,
ada graph sederhana G dengan barisan derajat d1.
{1, 2, ..., n – 1}
Konstruksi graph Hdari sedemikian sehingga V(H) = V(G) |1 ≤
E(G)
, ..., dn) graphik maka
; ;
} dengan d(vi) ={
Misal V(G) = {v1, v2, ...,
,
dimana i
{v} ; V(G) dan E(H) =
≤
Karena G graph sederhana maka graph H juga graph sederhana, sehingga diperoleh dH (v) = d1. ; ;
d(vi) ={
Akibatnya π = {d1, d2, d3, ..., dn} adalah barisan derajat dari graph sederhana H. Dengan demikian π adalah graphik.
29. Misalkan G sebuah graph dengan
=
,
,…
yang berhubungan langsung dengan graph G dan =
+
≠ 0;
Jawaban:
+ ⋯+
. Misalkan A adalah matriks = (
) adalah matriks dengan
. Buktikan bahwa graph B terhubung jika dan hanya jika
Perhatikan gambar graph
; ≠ . pada gambar (DIMISALKAN):
Matriks berhubungan langsung dari graph di atas adalah sebagai berikut:
Perhatikan bahwa
0 1 1 1 1
1 0 1 0 0
1 1 0 1 1
1 0 1 0 1
1 0 1 1 0
adalah matriks simetris. Kalau graph G tidak punya gelung
(loop), maka setiap unsur
yang terletak pada diagonal utama adalah nol. Kalau
G graph sederhana, maka unsur-unsur dari
nol atau satu.
SOAL HAL 70-71 1.
Gunakan algoritma djikstra untuk mendapatkan lintasan terpendek dan panjangnya dari titik
ke setiap titik yang lain disetiap graph bobot berikut !
a. a
Jawab : Berdasarkan algoritma djikstra, kita misalkan Langkah 1 : Label
dengan
2,3,4,5,6
dan
0 dan
, ~
dengan
,
Tulis
~
0
Langkah 2 : Pilih
dengan
Langkah 3 : karena → →
-
Kembali ke langkah 2 :
~
~
~
0 minimum
maka langkah 3 dilewati
Langkah 4 : perhatikan titik
0
~
4
, terkait ke min
dan
~,0
4
~,0
3
min ~
, ,
maka ganti label
4 3 ~
~
3
.
Pilih
= 3
dengan
Perhatikan titik
terkait ke
dan
→ → ( )
= =
4
0 -
= min
,
+
(
= min
,
+
(
4, 3 + 2 = 4 ~, 3 + 5 = 8 ~
~
8
3
5
3
-
Kembali ke langkah 2 : Pilih
= 4
dengan
Perhatikan titik
terkait ke
dan
→ → ( )
= =
4
0 −
= min
,
+
(
= min
,
+
(
~, 4 + 6 = 10 8, 4 + 1 = 5 10
−
~
−
Kembali ke langkah 2 : Pilih
= 5
dengan
Perhatikan titik
terkait ke
dan
→ → ( )
0 −
Kembali ke langkah 2 :
4
−
= =
= min
,
+
(
= min
,
+
(
10, 5 + 3 = 8 ~, 5 + 5 = 10 8
10
5
−
3
−
Pilih
8
dengan
Perhatikan titik
terkait ke
→
10, 8
4
0
Dengan
min
demikian
2
,
8
sebuah
lintasan
di graph bobot G adalah lintasan
10 10
5
3
terpendek
dengan
,
,
,
,
,
panjang
10
.
b.
Berdasarkan algoritma djikstra, kita misalkan Langkah 1 : Label
dan
0 dan
dengan
2,3,4,5,6,7,8,9
, ~
dengan
,
.
Tulis
0
~
Langkah 2 : Pilih
~
dengan
Langkah 3 : karena
~
~
~
~
~
0 minimum
maka langkah 3 dilewati
Langkah 4 : perhatikan titik →
,
, terkait ke min
~,0
5
dan ,
5
maka ganti label
~
dari
→
=
→ ( )
0 −
5
=
~
= min
,
+
(
= min
,
+
(
~,0 + 2 = 2 ~,0 + 4 = 4
2
4
~
~
~
~
5
~
5
9
Kembali ke langkah 2 : Pilih
= 2
dengan
Perhatikan titik
terkait ke
→ → → ( )
0 −
5
,
dan
= = =
~
= 4
dengan
Perhatikan titik
terkait ke
→ → → ( )
0 −
5
Kembali ke langkah 2 :
~
,
+
(
= min
,
+
(
= min
,
+
(
4, 2 + 5 = 4 ~, 2 + 2 = 4 ~, 2 + 3 = 5
2
4
−
Kembali ke langkah 2 : Pilih
= min
, = = =
~
4
dan
= min
,
+
(
= min
,
+
(
= min
,
+
(
5, 4 + 3 = 5 5, 4 + 4 = 5 ~, 4 + 5 = 9
2
−
4
−
~
4
Pilih
= 4
dengan
Perhatikan titik
terkait ke
→
( )
0 −
5
=
~
= 5
dengan
Perhatikan titik
terkait ke
→ →
( )
0 −
5
= =
0 −
5
=
9
−
0 −
+
(
= min
,
+
(
~, 5 + 4 = 9 ~, 5 + 5 = 10 4
10
−
= min
,
4
−
+
9, 5 + 4 = 9
2
4
−
terkait ke
→
( )
5
9
5
9
10
5
9
−
5
9
( 4
−
−
= 9
dengan
Perhatikan titik
,
−
Kembali ke langkah 2 : Pilih
−
= min
2
terkait ke
→
( )
−
4
= 5
dengan
Perhatikan titik
~
(
dan
Kembali ke langkah 2 : Pilih
+
4
−
9
−
,
5, 4 + 3 = 5
2
Kembali ke langkah 2 : Pilih
= min
5
−
9
−
=
= min
,
10, 9 + 3 = 10
2
−
4
−
10
+
( 4
−
−
Kembali ke langkah 2 : Pilih
9
dengan
Perhatikan titik
terkait ke
→
0
Dengan 2.
5
demikian
9
sebuah
min
10, 9 2
lintasan
di graph bobot G adalah lintasan
3
,
10
4
10
4
5
terpendek
dengan
,
,
,
,
,
,
,
9
panjang ,
10
dari
.
Sebuah perusahaan elektronik mempunyai cabang di 7 kota besar K1, K2, K3, K4, K5, K6 dan K7 . Harga tiket penerbangan langsung dari kota Ki ke kota Kj diberikan oleh unsur matriks B berikut yang terletak pada baris k-i dan kolom ke-j ( simbol ∞ berarti tidak ada penerbangan langsung). Saudara sebagai karyawan diperusahaan tersebut ditugasi untuk membuat sebuah tabel rute penerbangan termurah untuk setiap kota yang ada. Susunlah tabel yang dimaksud.
Jawab:
Berdasarkan algoritma djikstra, kita misalkan K1 = s dan K2 = t dimana K1 , K2 ∈ N(G). Langkah 1
Label K1 dengan (K1) = 0 dan (K2) = ∼ i = {2, ...7}. Tulis T= V(G) V(G)
K1
K2
K3
K4
K5
K6
K7
(K)
0
T
K1
∼
∼
∼
∼
K5
∼
K6
∼
K7
K2
K3
K4
Langkah 2 Pilih K, dengan (K1) = 0 minimum Langkah 3 Karena K1 ≠ K7, maka Langkah 3 dilewati Langkah 4 Perhatikan K1, terkait ke K2 dan K3 maka ganti label K2 ⟹ (K2) = min { (K2), (K1) + 60} = min {∼, 0 + 60} = 60
K3 ⟹ (K3) = min {∼, 0 + 70 } = 70 V(G)
K1
K2
K3
K4
K5
K6
K7
(K)
0
60
70
T
-
K2
K3
∼
∼
K5
∼
K6
∼
K7
K4
Pilih K2, (K2) = 60 minimum yang terkait ke K2 adalah K3, K4, K5 maka ganti label K3 ⟹ (K3) = min { 70, 60 + 50} = 70
K4 ⟹ (K4) = min {∼, 60 + 50 } = 110
K5 ⟹ (K5) = min {∼, 60 + 20 } = 80
V(G)
K1
K2
K3
K4
K5
K6
K7
(K)
0
60
70
110
80
T
-
-
K3
K4
K5
∼
∼
K6
K7
Pilih K3, (K3) = 70 minimum yang terkait ke K3 adalah K4 dan K6 maka ganti label K4 ⟹ (K4) = min { 110, 70 + 40} = 110
K6 ⟹ (K6) = min {∼, 70 + 70 } = 140
V(G)
K1
K2
K3
K4
K5
K6
K7
(K)
0
60
70
110
80
140
T
-
-
-
K4
K5
K6
∼
K7
Pilih K5, (K5) = 80 minimum yang terkait ke K5 adalah K4 ,K6,K7 maka ganti label K4 ⟹ (K4) = min { 110, 80 + 60} = 110
K6 ⟹ (K6) = min {140, 80 + 30 } = 110
K7 ⟹ (K7) = min {∼, 80 + 70 } = 150
V(G)
K1
K2
K3
K4
K5
K6
K7
(K)
0
60
70
110
80
140
150
T
-
-
-
K4
-
K6
K7
Pilih K4, (K4) = 110 minimum yang berhubungan langsung ke K4 adalah K6 K6 ⟹ (K6) = min {140, 110 + 50 } = 110
V(G)
K1
K2
K3
K4
K5
K6
K7
(K)
0
60
70
110
80
110
150
T
-
-
-
-
-
K6
K7
Pilih K6, (K6) = 110 minimum yang berhubungan dengan K6 adalah K7 maka K7 ⟹ (K7) = min {150, 110 + 50 }
= 150 V(G)
K1
K2
K3
K4
K5
K6
K7
(K)
0
60
70
110
80
110
150
T
-
-
-
-
-
-
K7
Pilih K7, karena s = t, yaitu K7 = K7 maka STOP V(G)
K1
K2
K3
K4
K5
K6
K7
(K)
0
60
70
110
80
110
150
T
-
-
-
-
-
-
-
Sehingga panjang lintasan terpendek dari V1 ke V7 adalah 150. (V7) = 150 = 80 + 70 = (K5) + W(K5 K7) (K5) = 80 = 60 + 20 = (K2) + W(K2 K5) (K2) = 60 = 0 + 60 = (K1) + W(K1 K2) Jadi lintasannya adalah { K1, K2, K5, K7}
V1
V2
V3
V4
V5
V1
V2
V3
V4
V5
V6
V7
-
60
70
110
80
110
150
{ K1, K3,
{ K1, K2,
{ K1, K2,
{ K1, K2,
K4 }
K5 }
K5, K6}
K5, K7}
50
20
50
90
{ K2, K5,
{ K2, K5,
K6}
K7}
70
120
60
70
110
-
50
50
50
-
40
40
-
70 { K1, K2,
{ K3, K5,
K4}
K7}
60
50
100
{ K1, K3,
{ K4, K6,
K4}
K7}
80
20
70
{ K1, K2,
{ K3, K2,
K5}
K5}
60
-
30
40
V6
V7
110
50
70
50
30
-
50
{ K1, K2, K5,
{K2, K5,
K6}
K6}
150
90
120
100
40
50
-
{ K1, K2, K5,
{K2, K5,
{K3, K5,
{K4, K6,
K7}
K6}
K7}
K7}
