BAB I PENGENALAN TENTANG APLIKASI MATEMATIKA DISKRET
I.1. Pendahuluan Banyak masalah kehidupan sehari-hari yang dapat diabstraksi sebagai masalah yang berkaitan dengan himpunan benda-benda diskret dan relasi biner pada benda-benda tersebut. Sebagai contoh, marilah kita perhatikan serangkaian pol pendapat umum yang dilakukan untuk menentukan kepopuleran para calon presiden. Dalam setiap pol yang diadakan, ingin diketahui pendapat para pemilih tentang dua di antara para calon, dan lalu ditentukan siapa favoritnya. Hasil polpol tersebut ditafsirkan sebagai berikut : Calon a dianggap lebih favorit daripada calon b jika salah satu di antara tiga kondisi berikut dipenuhi : 1. Calon a lebih favorit daripada calon b di dalam pol yang diadakan antara keduanya. 2. Calon a lebih favorit daripada calon c di dalam sebuah pol, sedangkan calon c lebih favorit daripada calon b di dalam pol yang lain. 3. Calon a lebih favorit daripada calon c, dan calon c lebih favorit daripada calon d, dan calon d lebih favorit daripada calon b di dalam tiga pol terpisah yang diadakan, dan begitu seterusnya. Untuk dua calon tertentu, misalnya kita ingin tahu apakah salah satu lebih kuat daripada yang lain atau tidak. Misalkan S = {a, b, c, ...} himpunan para calon presiden dan R sebuah relasi biner pada S sedemikian rupa sehingga (a,b) ada di dalam R jika pol antara a dan b diadakan dan a terpilih sebagai calon yang lebih favorit. Relasi biner pada suatu himpunan dapat disajikan dalam bentuk tabel atau grafik. Misalkan relasi biner pada Gambar 1.1.a dan Gambar 1.1.b mempresentasikan hasil-hasil pol yang diadakan. Kita lihat bahwa calon a lebih favorit daripada calon e sebab pasangan terurut (a, b), (b, d), (d, e) ada di dalam R.
1
a a
b
c
d
e
ü
a
ü
b ü
c
b
ü
ü
d
e
ü
e c
d
(a)
(b) Gambar 1.1 Hasil pol yang diadakan
Sebagai ilustrasi lain, misalkan sejumlah kota dihubungkan oleh jalanjalan raya. Bila diberikan peta jalan-jalan raya tersebut, kita mungkin ingin mengetahui apakah ada rute jalan raya antara kedua kota pada peta tersebut. Dalam berbagai masalah yang berkaitan dengan benda-benda diskret dan relasi biner, representasi grafik seringkali merupakan bentuk penyajian yang memudahkan. Hal ini menuntun kita pada pembelajaran tentang teori graf, suatu pembelajaran tentang aplikasi dari Matematika Diskret.
I.2. Penerapan Graf Dalam Persoalan Matematika Diskret Graf dapat
didefinisikan
sebagai
kumpulan
simpul-simpul
yang
dihubungkan dengan garis. Simpul biasa dinyatakan dengan istilah verteks dan garis biasa dinyatakan dengan istilah edges atau busur. Contoh : 1.1 Struktur kimia adalah kumpulan atom-atom yang terikat menurut aturan ikatan kimia tertentu. Sebagai contoh, CH4 (Metana) merupakan ikatan kimia yang terdiri dari 1 atom C dan 4 atom H, sehingga terbentuk ikatan seperti di bawah ini. H
H
C
H
H CH4 (Metana)
Model Graf Gambar 1.2
2
Dari ikatan yang ada pada Gambar 1.2, dapat diubah ke dalam model graf seperti gambar di sampingnya. 1.2 Jaringan komunikasi adalah kumpulan beberapa pusat atau stasiun yang dapat berkomunikasi secara langsung. Subscriber
Group Switching Centre Local exchange
Gambar 1.3 Jaringan Telepon
Switching Center
Model Graf Gambar 1.4 Jaringan Switching
1.3 Jaringan lalu lintas adalah kumpulan jalan yang saling berhubungan. Jika digambar dalam bentuk graf, simpul melambangkan persimpangan dan busur melambangkan arah lalu lintas.
3
Contoh :
Gambar 1.5 Jaringan Lalu Lintas
Gambar 1.6 Model Graf Jaringan Lalu Lintas
1.4 Sebuah papan sirkuit adalah kumpulan komponen yang dihubungkan dengan sebuah lintasan konduktor. Jika digambar dalam bentuk graf, simpul melambangkan simpangan dan busur melambangkan terminal dari komponen. Model alternatif lainnya adalah simpul melambangkan komponen dan busur melambangkan lintasan konduktor antara terminalterminal dalam komponen.
Gambar 1.7 Sirkuit dan Model Grafnya
4
Contoh-contoh di atas merupakan beberapa contoh tentang aplikasi graf dalam sistem model yang nyata. Dalam setiap persoalan, graf memberikan sebuah sruktur model tentang sistem yang kita pelajari, menjelaskan interaksi dan hubungan antara berbagai komponen dalam sistem. Sedangkan dalam berbagai persoalan,
masalah
yang
sering
muncul dalam pelaksanaannya adalah
mendapatkan sebuah penyusunan yang memenuhi semua permintaan, dan optimal menurut beberapa kriteria seperti harga, pengeluaran atau penampilan. Masalah dasar yang sering muncul pada Matematika Diskret yaitu : 1. Masalah eksistensi Apakah sedikitnya ada satu penyusunan dalam tipe khusus ? 2. Masalah perhitungan Berapa banyak penyusunan dari tipe khusus yang ada ? 3. Masalah optimisasi Diperoleh dengan memilih bentuk dari semua penyusunan yang mungkin untuk tipe yang pasti dan terbaik menurut beberapa kriteria. Kita dapat mengilustrasikan masalah-masalah ini ke dalam contoh berikut : Contoh 1.5 : Masalah Alokasi : Pada permasalahan pengalokasian frekuensi pengangkutan ke stasiun pengirim, dimisalkan ada m saluran (frekuensi) yang mungkin digunakan oleh n stasiun pengirim. Stasiun yang dialokasikan dekat dengan stasiun yang lain dan tidak dapat menggunakan saluran yang sama tanpa menyebabkan percampuran. Jadi, diberikan dua stasiun yang dapat atau tidak dapat dinyatakan bahwa kedua stasiun itu menggunakan saluran yang sama. Sejumlah persoalan terjadi. Masalah Eksistensi : Apakah mungkin untuk mengalokasikan sebuah saluran pada setiap gardu di mana untuk dua stasiun yang berbeda saluran harus mempunyai saluran yang berbeda? Jika ya, bagaimana cara mendapatkan alokasi tersebut ? Masalah Perhitungan : Berapa banyak alokasi yang sesuai ?
5
Masalah Optimasi : Berapa jumlah saluran minimum yang memenuhi kondisi alokasi ? Bagaimana kita dapat memodelkan situasi ini ? Sebuah model graf dapat dikembangkan sebagai berikut. Setiap stasiun dihubungkan oleh simpul dan 2 simpul dihubungkan oleh 1 busur jika dan hanya jika stasiun yang berhubungan tidak menggunakan saluran yang sama. Sebagai contoh, dimisalkan ada 5 stasiun dan informasi yang ada dinyatakan dalam hubungan matriks berikut. 1
2
3
4
5
1
-
1
0
0
1
2
1
-
1
1
0
3
0
1
-
1
1
4
0
1
1
-
1
5
1
0
1
1
-
Tabel 1.1
1 menunjukkan adanya hubungan (Gardu tidak bisa diberikan pada channel yang sama) dan 0 menunjukkan tidak ada hubungan. Dari informasi yang ada, dapat dibuat model graf seperti di bawah ini. 1
5
2
4
3 Gambar 1.8
Penggambaran matriks konflik yang ada ke dalam bentuk graf tentu saja tidak menyelesaikan masalah. Tetapi, aspek visual dari model graf tersebut
6
memberikan beberapa pandangan. Sebagai contoh, pembuatan segitiga ke dalam bentuk graf, menunjukkan bahwa kita membutuhkan sedikitnya tiga saluran yang berbeda. Dapatkah kita membuat alokasi, jika kita hanya mempunyai tiga saluran? Bagaimana kita menyelesaikan masalah eksistensi jika kita hanya punya m saluran? Sebuah alokasi mungkin terjadi hanya jika kita dapat mempartisi simpul dalam graf menjadi m himpunan di mana tidak ada dua simpul dalam himpunan yang sama terhubung oleh sebuah busur. Hal inilah yang membawa kita ke konsep pewarnaan. Sebuah graf dikatakan Graf k-colourable jika simpul-simpul dalam graf dapat diwarnai dengan syarat 2 simpul yang adjacent (berdampingan) diwarnai berbeda. Sebagai contoh Graf Gi, i = 1, 2, 3, 4, ... yang disajikan ke dalam Gambar 1.8 mempunyai i-pewarnaan.
G1
G2
G3
G4
Gambar 1.9
Sebuah Combinatorial Design merupakan cara memilih himpunan bagian dari suatu himpunan berhingga jika dan hanya jika beberapa kondisi khusus terpenuhi. Kondisi khusus ini disebut dengan mengeliminasi bias. Contoh 1.6 : Sebuah percobaan yang dilakukan untuk menguji efek samping dari 5 jenis obat terhadap 5 subyek. Dimisalkan obat-obat yang ada diberi label 1,2,3,4,5 dan subyeknya diberi nama A,B,C,D,E. Kemungkinan 1 : A
B
C
D
E
1
2
3
4
5
(Subyek A diberi obat berlabel 1, subyek B diberi obat berlabel 2, dan seterusnya.) Apa yang salah dengan kemungkinan 1 ?
7
Beberapa subyek mungkin alergi terhadap obat tertentu sehingga hasilnya akan bias. Kemungkinan 2 : Memberi setiap subyek setiap jenis obat, 5 hari berturut-turut. S U B Y E K
A B C D E
Senin 1 1 1 1 1
HARI Selasa Rabu 2 3 2 3 2 3 2 3 2 3
Kamis 4 4 4 4 4
Jumat 5 5 5 5 5
Tabel 1.2
Apakah solusi ini benar ? Hasilnya dapat mengakibatkan bias, karena : (i) Hari-hari tertentu, obat diberikan (Tiap hari sama obat) (ii) Efek dari obat pertama dapat mempengaruhi efek obat terakhir Bagaimana cara menghilangkan bias ? Untuk menghilangkan bias, tidak ada 2 subyek yang mendapatkan jenis obat yang sama pada hari yang sama. Jadi muncul tepat 1 kali pada setiap baris dan kolom. S U B Y E K
A B C D E
Senin 1 2 3 4 5
HARI Selasa Rabu 2 3 3 4 4 5 5 1 1 2
Kamis 4 5 1 2 3
Jumat 5 1 2 3 4
Tabel 1.3
Inilah solusi yang terbaik. Sejumlah persoalan akan timbul, seperti : 1. Apakah solusinya tunggal ? 2. Apa yang terjadi, jika kita hanya punya 4 subyek ? Bentuk matriks yang diberikan di atas dapat disebut dengan istilah Latin Square. Latin square didefinisikan sebagai suatu bentuk matriks di mana antara satu baris dan satu kolom tidak ada yang sel yang sama.
8
LATIHAN SOAL
1. Gambarkan sebuah graf yang mewakili setiap komponen kimia berikut ! (a)
H
H
H
H
H
C
C
C
C
H
H
H
H
H
C4H10 (Butana) (b) H
H
C
H
H
H
H
C
C
H
C
H
H
H C4H10 (Iso-butane)
Susunan di atas mempunyai komposisi yang sama tetapi berbeda bentuk. Dapatkah kamu menjelaskan mengapa hal ini dapat terjadi ? 2. Untuk masing-masing graf di bawah ini, tentukan minimum warna yang dibutuhkan untuk mewarnai simpul-simpul dibawah ini sehingga simpul yang berdampingan dapat diwarnai berbeda.
(a)
(b)
(c)
9
3. Tentukan Latin Square dengan order : (a) 2 (b) 3 (c) 4
4. Dua Latin Square A = (aij) dan B = (bij) dari n order yang sama dikatakan ortogonal jika n2 order yang berpasangan (aij, bij) semuanya berbeda. Tentukan sepasang Latin Square ortogonal order 3 !
10
BAB II GRAF DAN JARINGAN
Pada bab terdahulu diberikan beberapa contoh tentang graf. Dalam bab ini, kita akan melihat beberapa permasalahan khusus dalam rancangan jaringan. Masyarakat modern didominasi oleh sistem jaringan untuk informasi penyaluran, transportasi rakyat, dan penyaluran barang-barang serta energi. Jaringan telekomunikasi dan jaringan komputer adalah contoh umumnya. Secara luas dikatakan, sebuah jaringan adalah sebuah sistem yang melibatkan aliran atau perpindahan komoditas. Komoditas yang dimaksud dapat berupa benda yang dapat disentuh, seperti komponen elektronik, mobil-mobil, kaleng bir, gas alam atau benda yang tidak dapat disentuh seperti informasi, persahabatan dan hubungan kekeluargaan. Jaringan-jaringan ini dapat dimodelkan ke dalam kesatuan matematika yang disebut graf. Seperti yang telah dijelaskan dalam pendahuluan, sebuah graf dapat disebut sebagai kumpulan titik yang disebut simpul dan dihubungkan oleh garis yang disebut busur. Graf dapat digunakan sebagai cara yang sangat sederhana untuk memodelkan banyak jaringan. Sebagai contoh, sebuah jaringan komunikasi dapat dimodelkan ke dalam bentuk graf, dengan simpul menyatakan pusat komunikasi (contohnya, saluran telepon) dan busur menyatakan jaringan komunikasi (contohnya, saluran telegraf). Dalam memodelkan sebuah jaringan dengan graf, simpul dalam graf umumnya dinyatakan dalam bentuk titik yang menyatakan asal aliran serta tempat berakhir (contohnya, stasiun kereta api, terminal, pabrik, gudang, dan lain-lain). Busur dalam graf secara umum menyatakan saluran di mana komoditas berakhir (contohnya, trayek kereta api, rute penerbangan, aliran pipa, dan lain-lain). Sebuah graf memberikan model struktural dari jaringan. Dalam kebanyakan jaringan, metode konstruksi biasanya dinyatakan oleh harga, efisiensi, kehandalan dan kapasitas.
11
II.1. Graf Graf adalah kumpulan simpul atau verteks yang dihubungkan dengan garis atau busur. Definisi 2.1 Graf adalah himpunan busur dan simpul yang banyaknya berhingga dan busurbusurnya menghubungkan sebagian atau keseluruhan pasangan dari simpulsimpulnya. (C.L. Liu) Graf G(V, E) terdiri
atas
himpunan
simpul yang
dinyatakan
dengan V = {v1,v2, v3, ..., vn} dan himpunan busur yang dinyatakan dengan E = {e1, e2, e3, ..., en} dengan ei = (vi, vj) merupakan busur yang menghubungkan simpul vi dan simpul vj. Dalam menggambarkan graf, simpul digambarkan dengan lingkaran kecil atau titik tebal dan busur digambarkan dengan garis, dan arah panah pada garis melambangkan arah dari garis tersebut. Nomor atau nama simpul dapat diletakkan di dalam lingkaran kecil atau di tepi titik tebal. Busur (i,j) disebut busur berarah jika terdapat suatu aliran dari simpul i menuju ke simpul j. Dalam hal ini simpul i disebut simpul awal, sumber atau pangkal dan simpul j disebut simpul akhir, ujung, tujuan, atau terminal dari busur (i, j). Jika tidak terdapat aliran dari simpul i ke simpul j, maka busur (i, j) disebut busur tidak berarah. i
j
a. busur tak berarah
i
j b. busur berarah Gambar 2.1
i
j c. busur dua arah
Penulisan simpul dan busur dari graf G (V, E) yang digunakan seperti Gambar 2.1. Jika simpul s telah diberi nomor i maka cukup ditulis i, dan jika simpul s telah diberi nomor j, maka cukup ditulis simpul j. Demikian juga busur yang menghubungkan simpul i dan j cukup ditulis busur (i,j). II.2. Jaringan Suatu jaringan G (V, E, W) terdiri atas himpunan simpul yang dinyatakan dengan V = {v1,v2, v3, ..., vn} dan himpunan busur yang menghubungkan simpul-
12
simpul ∈ V dinyatakan dengan E = {e1, e2, e3, ..., en} = {(vi, vj) : vi ∈ V } dan setiap busur pada jaringan diberikan bobot (W). Dengan kata lain, jaringan merupakan suatu graf yang memiliki bobot pada setiap busurnya. Oleh karena itu, pada umumnya graf dinotasikan dengan G (V, E) dan jaringan dinotasikan dengan G(V, E, W). Jaringan komunikasi jika dibuat dalam bentuk graf, maka simpul melambangkan pusat komunikasi dan busur melambangkan link komunikasi. Contoh : Perusahaan memproduksi l tanaman, P1, P2, ..., Pl yang dibutuhkan m outlets atau pasar M1, M2, ..., Mm. Komoditas khusus disimpan pada n gudang, W1, W2, ..., Wn. Dalam graf, busur melambangkan hubungan transportasi dan simpul melambangkan produksi tanaman, gudang dan pasar. Pada tiap busur, akan ditentukan jumlah maksimum komoditas yang dapat ditransport sepanjang hubungan dan harga transport 1 unit. Pada simpul mewakili: Tanaman Pi, i = 1, 2, ..., l . Kita dapat menentukan bobot sebagai rata-rata produksi tanaman dan harga produksi per unit untuk Pi. Gudang Wj, j = 1, 2, ..., n. Kita dapat menentukan bobot sebagai kemampuan penyimpanan pada gudang Wj dan harga penyimpanan satu unit per waktu. Pasar Mk, k = 1, 2, ..., m, kita dapat menentukan bobot sebagai permintaan per waktu, dan harga penjualan komoditas. Pembahasan selanjutnya tentang seberapa jauh penggunaan graf sebagai model struktural. Sekarang, kita akan membahas beberapa persoalan khusus yang muncul. Persoalan Penghubung Sebuah
jaringan komunikasi (contohnya,
jaringan telepon)
yang
menghubungkan n pusat atau kota T1, T2, ..., Tn harus diinstall. Masing-masing pusat mampu untuk menerima dan menyalurkan informasi. Jadi dua pusat dapat berkomunikasi secara langsung maupun tidak langsung. Diberikan contoh n × n matriks C = [cij] di mana cij menyatakan harga penginstallan
13
jaringan komunikasi (contohnya, jaringan telepon) antara pusat Ti dan Tj, disusun menjadi sebuah jaringan untuk mencapai dua tujuan berikut : (i) sedikitnya dua pusat yang dapat berkomunikasi, dan (ii) jumlah biaya instalasi adalah minimum. Berdasarkan Persoalan Penghubung di atas, jika n = 6, dan matriks biayanya adalah : T1 0 5 10 ∞ ∞ 3
T1 T2 T3 T4 T5 T6
T2 5 0 8 4 10 ∞
T3 10 8 0 5 15 ∞
T4 ∞ 4 5 0 13 7
T5 ∞ 10 15 13 0 2
T6 3 ∞ ∞ 7 2 0
Tabel 2.1
Graf yang digambarkan berdasarkan matriks di atas adalah pada Gambar 2.2. di bawah ini : T1
5
T2 10
8
3 10
4
T3
T6 15 7
5
2 13 T5
T4 Gambar 2.2
Biaya yang bertanda ∞ artinya pusat yang berhubungan tidak dapat berkomunikasi secara langsung, sehingga kita dapat menghilangkan busur tersebut dari graf kita. Persoalan Lintasan Terpendek Perhatian khusus ditujukan untuk menemukan rute terpendek antara pasangan pusat dalam sebuah jaringan. Contohnya, sebuah perusahaan bisnis besar dengan kantor pusat di New York mempunyai beberapa cabang utama di negara-negara seluruh dunia. Kantor pusat mengkoordinasi seluruh kegiatan operasi perusahaan, dan setiap hari seluruh informasi (meliputi permintaan,
14
penawaran dan biaya) harus diberikan dari kantor pusat ke kantor-kantor cabang. Informasi yang ada dikirimkan via teleks. Diberikan biaya pengiriman pesan melalui teleks antara dua perusahaan, dan ditentukan rute komunikasi termurah dari kantor pusat dan setiap kantor cabang lainnya. Perusahaan perbankan dengan kantor pusat di New York (NY) dan kantor cabang di Paris (P), Zurich (Z), Berlin (B), Tokyo (T), Hongkong(HK) dan Sydney (S). Setiap hari informasi penting (meliputi permintaan, penawaran dan biaya) harus diberikan dari kantor pusat ke kantor-kantor cabang. Informasi yang ada dikirimkan via teleks. Biaya pengiriman pesan antara dua kantor cabang diberikan dalam matriks di bawah ini : NY P Z B T HK S
NY 0 8 10 12 10 15 20
P 8 0 2 1 10 10 10
Z 10 2 0 3 12 12 15
B 12 1 3 0 10 10 10
T 10 10 12 10 0 3 5
HK 15 10 12 10 3 0 5
S 20 10 15 10 5 5 0
Tabel 2.2
Graf yang digambarkan berdasarkan matriks di atas adalah pada Gambar 2.3. di bawah ini : 10 P
1
B
10
2
10
10
8
3 10
10 T
12 10 20 15
NY
5 3
S
10 HK
Z
12
5 15 12
Gambar 2.3
Seperti contoh terdahulu, model graf ini memberikan himpunan semua hubungan yang mungkin dan permasalahannya adalah memilih sebuah
15
himpunan bagian dari himpunan ini yang menunjukkan bahwa jaringan yang ada sesuai dan jumlah biaya dari pengiriman informasi dari kantor pusat ke kantor cabang dapat diminimalkan. Persoalan Aliran Maksimum Persoalan dasar dimulai dengan menentukan jumlah aliran maksimum yang dapat dikirim antara pasangan pusat dalam jaringan. Sebagai contoh sebuah jaringan telepon menghubungkan n pusat (sambungan telepon) T1, T2, ..., Tn. Jumlah maksimum panggilan langsung yang disebut cij dapat dibuat per unit waktu antara Ti dan Tj, tergantung jumlah saluran yang menghubungkan dua pusat. Setiap pusat tentu saja dapat menerima dan mengirim panggilan. Diberikan matriks C = [cij]. Permasalahannya adalah menentukan jumlah panggilan maksimum yang dapat terjadi antara dua pusat yang diberikan. Sesuai contoh jika n = 6 dan kapasitas matriks C diberikan seperti di bawah ini 0 40 80 C= 0 0 0
40 80 0 0 0 0 20 60 20 0 20 0 20 100 0 60 20 0 20 80 20 100 20 0 50 0 0 80 50 0
Jaringan yang ada dapat digambarkan sebagai berikut :
C2 40 C1
60
C4
20
80
20 80
20 20 100
C3
C6 50
C5 Gambar 2.4
Perkembangan teori graf diawali dari teka-teki (puzzle). Salah satu tekatekinya adalah masalah jembatan Konigsberg. Solusi dari teka-teki ini mengilhami beberapa konsep dasar dalam teori graf.
16
Sebuah rencana kota tua Konigsberg (sekarang Kaliningrad) di Prussia Timur dan sungai Pregel (sekarang Pregolya) dengan tujuh jembatan perentang ditunjukkan pada Gambar 2.5. Hal ini menunjukkan bahwa masyarakat Konigsberg dapat menghibur diri mereka dengan mengelilingi kota dan menyeberangi tujuh jembatan tepat satu kali. Pada tahun 1736 Leonhard Euler, seorang matematikawan dari Swiss, dalam artikel perdananya mengembangkan sebuah metode untuk menyelesaikan persoalan umum ini. C
B
A
D Gambar 2.5
Metode Euler menjelaskan bahwa setiap daratan dinyatakan dengan simpul dan setiap jembatan dinyatakan dengan busur yang menghubungkan simpul-simpul. Berdasarkan informasi tersebut, dapat dibuat graf seperti di bawah ini : C
A
B
D Gambar 2.6
Hal inilah yang membuat hasil kerja Euler memberikan konsep penting dalam “graf Eulerian” yang muncul dalam kehidupan modern sekarang. Aplikasi hal ini dalam teori graf seperti pengiriman surat, pengeplotan mesin dan masih banyak lagi. Aplikasi ini akan dibahas dalam Bab 6.
17
LATIHAN SOAL
1. Sebuah perusahaan minuman mempunyai 3 jenis minuman B1, B2, dan B3. Masing-masing minuman mempunyai kapasitas produksi 5000 karton per bulan. Perusahaan mempunyai outlet di Louisville (M1), Plains (M2), Pittsburg (M3) dan St. Louis (M4) yang membutuhkan 1.500, 3.500, 2.000, dan 2.500 karton per bulan. Biaya pengiriman per 100 karton minuman Bi, i = 1, 2, 3, ke outlet-outlet Mj, j = 1, 2, 3, 4 diberikan dalam matriks di bawah ini : M1 M2 M3 M4 B1 5 30 15 20 B2 8 25 18 17 B3 12 35 20 25 a. Gambarkan graf berbobot untuk menunjukkan situasi di atas ! b. Permasalahan optimasi apa yang akan muncul ? 2. Seorang penjual koran bertanggung jawab dalam mengirimkan koran-koran ke rumah-rumah yang ditunjukkan dalam map ini pada sore hari. Karena kemacetan lalu lintas, dia tidak dapat menyeberang jalan kembali dan tidak dapat mengirimkan koran ke rumah-rumah di seberang jalan. Jadi ia harus berjalan sebanyak dua kali. Apakah mungkin bagi penjual koran untuk menentukan rute terpendek agar ia dapat berjalan di jalan itu tepat hanya satu kali ?
18
3. Air dikirimkan dari sumber penampungan utama D ke sebuah penampungan cabang lainnya, R, melalui sebuah saluran pipa yang terdiri atas 5 stasiun pemompa P1, P2, ..., P5. Rata-rata air yang dialirkan antara berbagai stasiun per hari dalam jutaan liter disajikan dalam tabel di bawah ini. D P1
P2
P3
P4
P5
R
D 0 230 200 170 0 0 0 P1 0 0 100 0 200 0 0 P2 0 0 0 0 0 160 180 P3 0 0 0 0 0 150 0 P4 0 0 0 0 0 0 200 P5 0 0 0 0 0 0 250 R 0 0 0 0 0 0 0 Permasalahannya adalah untuk memaksimumkan aliran air per hari dari sumber penampungan utama ke penampungan cabang lainnya. (a) Gambarkan jaringannya ! (b) Dimisalkan sebuah penampungan R` ditambahkan ke dalam jaringan. Stasiun pemompa P3, P4 dan P5 dihubungkan ke R` dengan saluran pipa yang mempunyai kapasitas 50, 75, dan 100 juta liter per hari. Bagaimana perubahan yang terjadi pada jaringan? Permasalahan optimasi apa yang muncul ? (c) Dimisalkan pompa P4 mempunyai kapasitas maksimum 280 juta liter per hari dan kapasitas pipa tidak berubah. Bagaimana jaringan dalam soal (a) akan berubah ? 4. Perpustakaan universitas dikelompokkan ke dalam empat fasilitas, dengan nama Catalog (C), Photocopy (P), Jurnal (J) dan Buku baru (B). Sebuah investigasi menjelaskan permintaan harian, dan jumlah peredaran setiap pasangan fasilitas :
E
C
P
J
B
E − 200 4 80 32 C 200 − 77 125 42 P 4 77 − 64 19 J 80 125 64 − 26 B 32 42 19 26 −
19
E menyatakan jalan masuk. Diputuskan untuk mengatur fasilitas-fasilitas ke dalam bentuk jalan, dengan tujuan memaksimumkan jumlah nilai pasangan fasilitas yang berdampingan. Gambarkan model graf untuk persoalan ini ! 5. Sebuah universitas mensponsori seminar setengah hari tentang Optimasi Kombinatorial. Ada tujuh pembicara, masing-masing dari mereka berbicara selama 1 jam. Seminar ini memerlukan waktu lebih dari 4 jam dan oleh karena itu beberapa pembicara harus menjadwalkan waktunya pada jam yang sama. Matriks berikut memberikan hubungan antara para pembicara dalam seminar. “1” menunjukkan pembicara tidak dapat menjadwalkan pada waktu yang sama dan “-“ menunjukkan tidak ada hubungan. 1 1 − 2 1 3 − 4 − 5 1 6 − 7 1
2 1 − − − − − −
3 − − − 1 1 1 1
4 − − 1 − 1 1 −
5 1 − 1 1 − 1 1
6 − − 1 1 1 − −
7 1 − 1 − 1 − −
a. Gambarkan matriks di atas ke dalam bentuk graf ! b. Dapatkan seminar diatur dalam waktu yang spesifik ?
20
BAB III KONSEP DASAR TEORI GRAF
Pada bab ini akan diperkenalkan konsep-konsep dasar dari teori graf. Graf biasa dilambangkan dengan G, verteks atau simpul dilambangkan dengan V dan busur atau garis dilambangkan dengan E. Sebuah graf G terdiri dari himpunan V(G) dari simpul, himpunan E(G) dari busur dan suatu relasi insidensi yang menghubungkan setiap busur. Jika e adalah sebuah busur dari G dengan ujung u dan v maka e dikatakan menghubungkan u dan v. Definisi 3.1 Sebuah busur dikatakan berinsidensi (insident), jika simpul tersebut terdapat busur yang menghubungkannya dengan simpul yang lain. Sebuah busur yang memiliki ujung yang sama dikatakan loop. Misalkan busur berarah (a) berinsidensi dari simpul a dan berinsidensi ke simpul a, maka dikatakan loop. Dengan kata lain loop merupakan sebuah busur yang berinsidensi dari dan ke simpul yang sama. Pada Gambar 3.1 diberikan sebuah contoh graf G dengan V(G) = {v1, v2, ..., v5} dan E(G) = {e1, e2, ..., e8}. Busur e8 merupakan loop. Gambar lain dari Graf G digambarkan pada Gambar 3.2 : v2 e1
e5 e7
v1
e3
e4
e8 v4
e2
v5
e6 v3 Gambar 3.1
v2 e1
e5 e4
e3
v1
e8 v5 e7 e6
e2
v4
v3 Gambar 3.2
21
Definisi 3.2 Dua simpul dikatakan berdampingan (adjacent), jika kedua simpul tersebut dihubungkan oleh sebuah busur. Pada busur berarah (a,b), simpul a dikatakan berdampingan (adjacent) ke simpul b, dan simpul b dikatakan berdampingan (adjacent) dari simpul a. Definisi 3.3 Sebuah simpul dikatakan simpul terasing atau terisolasi jika tidak terdapat busur yang berinsidensi dengannya. Sebuah busur dari suatu graf dikatakan insidensi jika busur tersebut memiliki satu simpul persekutuan. Dua simpul dikatakan berdampingan jika simpul-simpul tersebut berada pada ujung garis yang sama. Sebuah simpul dikatakan terasing jika tidak ada busur yang menghubungkannya dengan simpul yang lain. e3 v1
e1 v2
e4
e2
v5
v6
e6 v3
v4 e5 Gambar 3.3. Graf dengan 6 simpul dan 6 busur
Perhatikan Gambar 3.3 di atas : v6 merupakan simpul terasing, karena tidak ada busur yang menghubungkan simpul v6 dengan simpul lainnya. Busur e1 merupakan loop, karena menghubungkan v2 dengan dirinya sendiri. Busur e2, e5 dan e6 insidensi pada v4. v1 dan v2 berdampingan, karena berada pada satu garis yaitu e3. Secara umum, bentuk graf tidak unique atau tunggal. Definisi 3.4 Suatu graf dikatakan multiple edges jika terdapat lebih dari 1 busur yang menghubungkan pasangan titik yang sama.
22
Pada Gambar 3.2 didapatkan bahwa busur e3 dan e4 multiple edges. Simpul v2 dan v3 sama-sama dihubungkan e3 dan e4. Definisi 3.5 Suatu graf dikatakan simpel atau sederhana jika tidak memiliki loop dan multiple edges. Contoh 3.1 : v1
v2
v3
v4
Gambar 3.4 Graf Simpel
Gambar 3.1 dan Gambar 3.2 merupakan graf tidak simpel Definisi 3.6 Suatu graf dikatakan graf complete atau graf lengkap jika graf tersebut simpel dan setiap pasangan simpul yang berbeda dihubungkan oleh satu busur. Graf complete yang mempunyai n titik dinotasikan Kn. n 1 Kn punya = n(n − 1) busur. 2 2 Bukti : n
C2 =
n! n(n − 1)!(n − 2)! 1 = = n(n − 1) 2!(n − 2)! 2!(n − 2)! 2
Definisi 3.7 Graf yang memiliki himpunan simpul yang dapat dipartisi menjadi 2 himpunan X dan Y, di mana ujung satunya di X dan ujung yang lain di Y, dinamakan graf Bipartite. Definisi 3.8 Graf Bipartite Complete adalah graf Bipartite dengan bipartisi (X,Y) di mana setiap simpul X dihubungkan dengan setiap simpul Y. Graf Bipartite Complete dinotasikan dengan Km,n , di mana X = m dan Y = n.
23
Contoh 3.2 :
K1,3
K2,3
K3,3
Gambar 3.5
Catatan : Graf Bipartite tidak mungkin punya loop, tidak harus simpel tetapi punya multiple edges. Sebuah graf G adalah k-colourable jika simpul-simpulnya dapat diwarnai, tidak lebih dari k-warna, di mana tidak ada dua simpul yang berdampingan diwarnai yang sama. Jika graf G 2-colourable, maka graf ini memiliki bipartisi (X,Y) dengan simpul dari X diberi 1 warna dan simpul di Y diberi warna lainnya. Kesimpulannya, jika G merupakan graf Bipartite maka G merupakan 2colourable. Oleh karena itu, kita dapat mengatakan bahwa graf G bipartite jika dan hanya jika 2-colourable.Jika G merupakan graf Bipartite akan mempunyai 2 warna atau yang lebih dikenal dengan istilah 2-colourable. Contoh 3.3 : Mana dari graf di bawah ini yang merupakan graf Bipartite ? u2
v2
v5
v3
v6
u6 u5 u4
v1
v8
u7 v4
u1
v7
u3 G1
G2 Gambar 3.6
24
Jawaban : G1 tidak 2-colourable, karena graf ini berbentuk segitiga dengan simpul u1u2u3. Jadi G1 bukan merupakan graf Bipartite. Selain itu, G2 adalah 2colourable seperti yang ditunjukkan pada Gambar 3.7 di bawah ini : v2
v5 hitam
v1
v3
v6
v8 putih
v4
v7
Gambar 3.7
Kita mendapatkan bahwa graf di atas 2-colourable. Pertama, simpul v1 diwarnai hitam. Kemudian simpul v2, v3 dan v4 yang berdampingan dengan v1 diberi warna putih. Simpul v5, v6, dan v7 yang berdampingan ke satu atau lebih dari simpul v2, v3 dan v4 diwarnai hitam. Terakhir, simpul v8 yang berdampingan dengan simpul v5, v6, dan v7 diberi warna putih. Jadi G2 adalah sebuah graf Bipartite dengan bipartisi (X,Y) di mana X = {v1, v5, v6, v7} dan Y = {v2, v3, v4, v8}. Gambar alternatif dari G2 digambarkan sebagai berikut : v1
v5
v6
v7 G2
v2
v3
v4
v8
Gambar 3.8
Catatan : Contoh di atas merupakan cara sederhana untuk menentukan apakah graf yang diberikan Bipartite atau tidak. Definisi 3.9 Sub graf dari graf G adalah graf H dengan sifat : 1. V ( H ) ⊆ V (G ) 2. E ( H ) ⊆ E (G )
25
3. Jika e adalah busur H yang menghubungkan simpul u dan v maka e adalah busur G yang menghubungkan u dan v. Definisi 3.10 Jika sub graf H dari G tidak identik atau tidak sama terhadap G maka H dikatakan proper sub graf dari G. Definisi 3.11 Jika jumlah simpul di H sama dengan jumlah simpul di G (V(H) = V(G)) maka H dikatakan spanning subgraf dari G. Contoh 3.4 : v1
v2
v1
v5
v2
v1
v5 v6
v8
v6
v8 v3
G
v5 v6
v7
v4
v2
v4
v8 v3
A proper subgraph of G.
v4
v7 v3
A spanning subgraph of G.
Gambar 3.9
Derajat d(v) dari simpul v di G adalah jumlah busur di G yang insiden dengan v. Jika loop dihitung 2 busur. Contoh 3.5 : Dari graf G, buktikan bahwa :
∑ d (v) = 2 E (G )
V ∈V ( G )
Bukti : Ketika menjumlahkan derajat simpul-simpul dari G, kita menghitung masing-masing busur di G dua kali, satu kali untuk setiap dua simpul yang insiden dengan busur (loop dihitung sebagai dua busur). Jadi, jumlah derajat dari simpulsimpul di G sama dengan dua kali jumlah busur di G.
26
Definisi 3.12 Graf G dikatakan k-regular, jika setiap simpul di G punya derajat k. Graf complete Kn = (n-1)-regular, di mana n menunjukkan jumlah simpul. Graf complete bipartite Kn,n= n regular. Contoh 3.6 : Sebuah perusahaan membutuhkan 6 pekerja W1, W2, ..., W6 untuk 6 pekerjaan J1, J2, ..., J6 dengan permintaan keahlian yang berbeda. Setiap pekerja dikualifikasi utnuk satu atau lebih pekerjaan, seperti yang ditunjukkan di bawah ini : Pekerja
Pekerjaan yang dikualifikasikan
W1
J1, J2 dan J3
W2
J2 dan J4
W3
J1 dan J3
W4
J3, J5 dan J6
W5
J2
W6
J4 dan J5
Dapatkah semua pekerja ditugaskan sehingga tiap orang untuk 1 pekerjaan yang dikualifikasikan ? Penyelesaian : Kita dapat membentuk graf Bipartite G dengan bipartisi (X,Y) dimana misal X = pekerja = { W1, W2, ..., W6 } Y = pekerjaannya = { J1, J2, ..., J6 } W1 dihubungkan dengan Jk jika dan hanya jika W1 dikualifikasikan untuk pekerjaan Jk. Graf hasil digambarkan pada Gambar 3.10. W1
W2
W3
W4
W5
W6 G
J1
J2
J3
J4
J5
J6
Gambar 3.10
Penugasan mungkin jika dan hanya jika G memuat 1 regular spanning graf (sub graf yang memiliki 1 faktor). Graf di atas hanya latihan untuk menentukan apakah sub graf ada. Salah satu dari sub graf ditunjukkan oleh Gambar 3.11 di bawah ini, dengan busur-busur dari sub graf diberi garis tebal.
27
W1
W2
W3
J1
J2
J3
W4
W5
W6
J4
J5
J6
Gambar 3.11
Jadi penugasan pekerja untuk tiap jenis pekerjaan yang dikualifikasikan mungkin. Penugasan yang dilakukan seperti di bawah ini : Pekerja
Pekerjaan
W1
J1
W2
J4
W3
J3
W4
J6
W5
J2
W6
J5 Tabel 3.1
Catatan : 1. Diberikan graf Bipartite G dengan bipartisi (X,Y) maka G mempunyai 1regular spanning subgraf, jika dan hanya jika (i) X = Y {jumlah bipartisi X=Y} (ii) untuk himpunan bagian S dari simpul X sedikitnya S dari Y yang berdampingan ke satu atau lebih S. Contoh : W5
J2
W1
J1, J2,
J3
2. Ada sebuah algoritma yang disebut Metode Hungarian, menugaskan n orang untuk n pekerjaan sehingga tiap orang punya tugas sesuai dengan yang dikualifikasikan. Definisi 3.13 Walk dalam graf G merupakan barisan non-null berhingga w = v0 e1 v1 e2 v2 ... ek vk di mana menunjukkan titik dan busur sehingga untuk 1 ≤ i ≤ k , ujung ei = vi-1 dan vi . W dikatakan walk dari v0 (asal) ke vk (tepat berhenti) atau (v0-vk)-walk.
28
Panjang walk merupakan jumlah busur dari w. Jika simpul vo, v1, ..., vk dari walk w berbeda maka disebut lintasan atau path. Jika panjangnya positif dan asal serta simpul berhentinya sama maka dikatakan walk tertutup. Cycle merupakan walk tertutup yang memiliki asal dan simpul-simpul di dalamnya berbeda. Jadi dapat disimpulkan bahwa sebuah lintasan pasti merupakan walk tetapi walk belum tentu merupakan lintasan. Gambar 3.12 mempunyai banyak cycle, contohnya v0e1v1e2 v2e10v5e7v0 adalah cycle dengan panjangnya 4. e3 v1
e2 v2
e1 v0
e4 e8
e9
e11
Walk: v0 e1 v1 e8 v5 e10 v2 e3 v2 v3
e10
Path : v0 e1 v1 e8 v5 e6 v4 e5 v3
e7
e5 v5
e6
v4 Gambar 3.12
Cycle : v0 e1 v1 e8 v5 e7 v0 dengan panjang atau length 3 Length atau panjang merupakan jumlah dari busurnya.
Contoh 3.7: Tunjukkan jika G merupakan graf bipartite dan tidak punya cycle dari length ganjil ! Bukti : Misal C = v0 e1 v1 e2 v2 ... ek-1 vk
-1
ek v0 adalah cycle di G. G bipartite jika 2-
colourable. Jadi simpul C dapat diwarnai dengan 2 warna berbeda, jika dan hanya jika simpul lainnya berbeda warna. Simpul v0, v2, v4, ..., vk-2 diberi satu warna dan v1, v3, v5, ..., vk-1 diberi warna lainnya. Satu kemungkinannya, k bilangan bulat genap dan c sebuah cycle dengan length genap.
29
Catatan : Graf yang tidak punya cycle dari length ganjil adalah bipartite. Dengan kata lain graf dikatakan bipartite jika dan hanya jika tidak punya length cycle ganjil. Dua simpul u dan v dari graf G dikatakan terhubung jika ada lintasan (u,v) di G. Graf G terhubung jika setiap pasangan titik G terhubung, selainnya dari G tidak terhubung. Maksimal sub graf terhubung dari G disebut komponen G. Gambar 3.13 mengilustrasikan definisi ini.
Gambar 3.13 Graf tidak terhubung dengan 5 komponen
Dari Gambar 3.13, diperoleh sub graf yang terhubung maksimal 5 komponen. Dengan kata lain dari gambar di atas berarti ada 5 komponen, 9 simpul dan 8 busur. Sebuah graf terhubung tanpa cycle disebut tree atau pohon. Dalam pohon ada 2 simpul terhubung oleh lintasan yang tunggal. Pemindahan sembarang busur dari pohon menghasilkan graf tak terhubung. Dengan kata lain sebuah pohon adalah minimal graf terhubung (dalam arti memiliki jumlah busur paling sedikit). Contoh 3.8 : Tunjukkan bahwa setiap graf terhubung memiliki pohon perentang ! Jawab : Misal G graf terhubung dan T adalah minimal sub graf perentang terhubung. Akan ditunjukkan bahwa T adalah pohon dan T tidak punya cycle. Ambil busur e yang menghubungkan x dan y di T. Selama T adalah minimal penghapusan e dari hasil T pada graf tak terhubung. Jadi ada simpul u dan v di T, yang tak terhubung di sub graf T-e dengan menghapus busur e. P menyatakan lintasan (u-v) di T, lintasan ini ada selama T terhubung. Jelas bahwa e terdapat di P. x mendahului y di P (lihat Gambar 3.14).
30
x u
y
v
e
V Gambar 3.14
Jika e ada di cycle C di T, maka x dan y akan terhubung di T-e oleh lintasan C-e (lihat Gambar 3.15). Tetapi, kemudian u dan v akan dihubungkan ke T-e, selama di T-e, u dihubungkan dengan x dan v dihubungkan dengan y. e tidak dapat masuk ke cycle T. Jadi T adalah pohon. Gambar 3.15 mengilustrasikan hasil pembuktian di atas.
G a spanning tree of G Gambar 3.15
Jika dua simpul u dan v terhubung di graf G, jarak d(u,v) antara u dan v merupakan panjang lintasan (u,v) yang paling pendek di G. Jika tidak ada lintasan yang menghubungkan u dan v di G, kita definisikan d(u,v) tak terbatas. Diameter dari graf G dinyatakan sebagai Diam (G), yang didefinisikan sebagai berikut. Diam (G) = max {d (u, v )} ( u ,v )∈V ( G )
Distance merupakan jarak terpendek dan Diam merupakan maksimum dari distance graf G.
31
Contoh 3.9 : Cari diameter dari graf berikut ! v2
v3 d (v1,v7) = 1 d (v1,v5) = 3
v1
v7
v8
v4
d (v1,v8) = 2 d (v2,v5) = 2
v6
G
v5
diam (G) = 3
Gambar 3.16
Dalam rancangan jaringan, diameter dari sebuah graf merupakan sebuah parameter penting yang menghubungkan jumlah maksimum dari jaringan termasuk pesan antara dua pusat dalam jaringan harus dilalui. Jadi, diameter merupakan ukuran keefisienan dan keefektifan yang penting dalam jaringan di mana waktu ditunda atau signal diturunkan secara proporsional terhadap panjang lintasan yang akan digunakan. Contohnya jaringan komunikasi. Kegunaan penting dari parameter untuk mengukur kehandalan jaringan adalah konektivitas, yang akan dibahas pada Bab 7. Tujuan
kita
adalah
mengembangkan
algoritma
yang
dapat
diimplementasikan ke dalam komputer sehingga kita dapat menspesifikasikan graf ke dalam program komputer. Representasi Graf pada Matriks Di dalam suatu graf seringkali perhitungan-perhitungan yang dikerjakan akan lebih sederhana bila graf yang dihadapi dinyatakan dalam bentuk matriks. Dalam pembahasan ini, ada tiga bentuk representasi matriks dari suatu graf, yaitu: 1. Matriks Adjasensi Matriks Adjasensi dari G dengan m× m matriks A = [aij] menunjukkan jumlah busur yang menghubungkan vi dan vj. Xij bernilai 1 jika busur (i. j) ∈ E mempunyai arah dari simpul i ∈ V ke simpul j ∈ V, dan bernilai 0 jika tidak ada hubungan sama sekali. Jika loop diberi nilai 2.
32
Jika graf G merupakan graf tak berarah, setiap busur (i, j) dapat dinyatakan sebagai suatu busur dengan dua arah. Dalam hal ini matriks Adjasensi X merupakan matriks simetris. Contoh 3.10 : e6
e7
v1
v2
e4
e5
v3
v6 e3
v4
v5
e1
e2 Gambar 3.17
Matriks Adjasensi X dari graf berarah pada Gambar 3.17 adalah : 0 0 0 X = [ X ij ] = 1 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 1 1 0 0 0
0 1 0 1 0 0
e6
e7
v1
v2
e4 v3
0 1 0 0 0 0 v6
e5
e3
v4
v5
e1
e2 Gambar 3.18
Matriks Adjasensi X dari graf tak berarah pada Gambar 3.18 adalah : 0 1 0 X = [ X ij ] = 1 0 0
1 0 0 1 1 1
0 0 0 1 0 0
1 1 1 0 1 0
0 1 0 1 0 0
0 1 0 0 0 0
Beberapa sifat penting dapat diturunkan dari representasi matriks suatu graf berarah maupun graf tak berarah. Dengan melihat contoh di atas, dapat diturunkan sifat bahwa :
33
Matriks Adjasensi X dari graf berarah : Suatu kolom yang seluruh elemennya bernilai 0 menyatakan suatu sumber. Suatu baris yang seluruh elemennya bernilai 0 menyatakan suatu muara. Jika seluruh elemen diagonal utamanya bernilai 0, maka menyatakan tidak terdapat loop dalam graf tersebut. Sebaliknya, suatu elemen yang tidak bernilai 0 pada diagonal menyatakan suatu loop. Matriks X tidak simetri. Matriks Adjasensi X dari graf tak berarah : Jika pada graf ditambahkan suatu simpul yang tidak terhubung, maka pada matriks X akan ditambahkan pula baris dan kolom yang seluruh elemennya bernilai 0. Matriks X simetris. Elemen yang tidak bernilai 0 pada diagonal menyatakan suatu loop. 2. Matriks Insidensi Secara khusus, jika V(G) = {v1,v2, ..., vm} dan E(G) = {e1, e2, ..., en} kita definisikan sebagai matriks Insidensi dari G dengan ordo m× n. Matriks Insidensi Z dari graf berarah merupakan matriks [zij] di mana zij bernilai 1 jika simpul i merupakan simpul awal busur, zij bernilai -1 jika simpul i merupakan simpul akhir busur, dan bernilai 0 jika lainnya. Berdasarkan Gambar 3.17, matriks Insidensi Z dari graf berarah tersebut adalah : 1 0 −1 0 0 − 1 0 0 1 1 0 0 0 1 0 Z = [ Z ij ] = 1 −1 −1 0 1 0 −1 0 −1 0 0 0 0 − 1 0
0 1 0 0 0 0
Matriks Insidensi Z dari graf tak berarah adalah matriks [zij] di mana zij bernilai 1 jika simpul i dihubungkan dengan busur dan bernilai 0 jika lainnya. Matriks Insidensi dari graf tak berarah Gambar 3.18 adalah :
34
0 1 0 Z = [ Z ij ] = 1 0 0
1 0 0 1 1 1
0 0 0 1 0 0
1 1 1 0 1 0
0 1 0 1 0 0
0 1 0 0 0 0
Dari representasi matriks Insidensi Z pada contoh di atas dapat dilihat bahwa : Pada graf tak berarah : Jumlah elemen tidak nol pada suatu baris menunjukkan derajat dari simpul. Setiap kolom mempunyai tepat dua elemen yang tidak nol. Suatu kolom yang hanya mempunyai satu elemen tidak nol menunjukkan suatu gelung. Pada graf berarah : Pada suatu baris yang semua elemen-elemen tidak nolnya adalah 1 menunjukkan bahwa barisan (simpul) merupakan suatu sumber. Suatu baris yang semua elemen-elemen tidak nolnya adalah -1 menunjukkan bahwa baris (simpul) merupakan muara. Jumlah elemen 1 pada suatu baris menunjukkan derajat keluar dari baris (simpul). Jumlah elemen -1 pada suatu baris menunjukkan derajat masuk dari simpul. Setiap kolom mempunyai satu elemen -1 dan satu elemen 1. Hal ini sebagai akibat bahwa setiap busur selalu mempunyai satu simpul awal dan satu simpul akhir. 3. Matriks Biaya Diberikan jaringan G(V, E, W) matriks biaya C dari jaringan G merupakan matriks [Cij] di mana Cij menyatakan biaya (pengangkutan satu satuan barang) pada busur (i, j). Pada representasi di atas, Cij menyatakan bobot w(i, j). Matriks biaya C tersebut merupakan matriks bujur sangkar n × n. Bilamana G merupakan jaringan tak berarah maka matriks C merupakan matriks yang simetri.
35
Graf terboboti merupakan graf G di mana setiap busur e dan G memiliki bilangan real w(e) yang disebut bobot. Jika H merupakan sub graf terboboti dari G, maka bobot w(H) didefinisikan sebagai w( H ) =
∑ w(e)
e∈E ( H )
Contoh 3.11 : Jaringan komunikasi dapat dinyatakan dalam graf terboboti. Titik G adalah pusat T1, T2, ..., Tn. Kita menghubungkan dua titik dengan sebuah busur jika link komunikasi dapat diinstall antara pusat yang berhubungan, biaya untuk menginstall dinyatakan sebagai bobot suatu busur. Bobotnya tidak negatif, selama bobot tersebut menyatakan biaya. Graf berarah adalah suatu graf G di mana setiap busur mempunyai arah. Sebuah digraf D terdiri dari himpunan simpul V(D), himpunan busur berarah dan sebuah relasi insidensi yang menghubungkan setiap busur D yang merupakan pasangan berurut di D. Jika a adalah sebuah busur dari D yang menunjukkan pasangan terurut (u,v), maka a dikatakan yang menghubungkan u (ekornya a) ke v (kepalanya a). Sebuah digraf dikatakan simpel jika tidak punya loop dan tidak ada dua busur yang memiliki pangkal dan ujung yang sama. Seperti halnya graf, digraf dapat dilambangkan di mana verteks dilambangkan dengan titik, busur oleh garis dan panah diletakkan di atas busur untuk menunjukkan arah. Diberikan graf G, kita dapat memperoleh digraf D dari G dengan: (i) menentukan arah untuk setiap busur G (ii) mengubah setiap busur G dengan suatu pasangan yang memiliki arah busur yang berbeda.
G Gambar 3.19
36
Graf yang diperoleh dengan cara (i) disebut Orientasi Graf G. Diberikan sebuah digraf D, kita dapat memperoleh graf G dengan mengubah setiap busur di D dengan suatu busur yang menghubungkan ujung yang sama. Graf G yang diperoleh dengan cara (ii) disebut Underlying Graf G. Sebuah jalan berarah di D merupakan barisan tak kosong berhingga W = vo a1 v1 a2 ... ak vk di mana menunjukkan simpul dan busur, dan untuk 1 ≤ i ≤ k busur ai menghubungkan vi-1 ke vi. Jumlah busur di W disebut panjang W. Jika titik v0, v1, ..., vk berbeda dan jalan berarah yang merupakan lintasan, maka disebut lintasan berarah / Dipath . Contoh 3.12 : Tentukan graf berarah terboboti D, di mana busur terboboti menunjukkan rata-rata alur maksimum, dan alur maksimum di antara pasangan titik tertentu dalam jaringan. Solusi : Solusi
dari
permasalahan
di
atas
dapat
diselesaikan
dengan
mengembangkan algoritma yang tepat. Penggunaan suatu algoritma biasanya didasarkan pada waktu prosesnya. Hal inilah yang mendasari kita untuk membicarakan algoritma kompleksitas waktu. Algoritma dikelompokkan berdasarkan waktu proses dari implementasi dalam komputer, tergantung ukuran masukan (input). Dalam algoritma teori graf, masukan yang dimaksud berupa jumlah simpul dan busur. Biasanya pernyataan di atas
digunakan
untuk
memperkirakan
jumlah
operasi dasar
komputer
(penjumlahan, perkalian, dan perbandingan) yang dibutuhkan dalam proses algoritma. Jika algoritma memproses masukan waktu cn2 untuk beberapa konstanta c, maka waktu kompleksitas T(n) dari algoritma dapat ditulis O(n2) (dibaca “order n2”). Secara umum, T(n) disebut O(f(n)), jika ada a konstanta real c>0 sehingga T(n) ≤ cf(n) untuk semua bilangan n. Waktu kompleksitas dari sebuah algoritma menunujukkan ukuran masalah yang dapat diselesaikan. Tabel 3.2 dan 3.3 di bawah memberikan ilustrasi tentang hal di atas. Kita asumsikan bahwa komputer mempunyai kecepatan 106 per detik.
37
Algoritma A1 A2 A3 A4 A5
Kompleksitas 2
n n3 n5 2n 3n
20 0,0004 detik 0,008 detik 3,200 detik 1,049 detik 58,113 menit
Ukuran n 30 0,0009 detik 0,027 detik 24,300 detik 17,896 menit 6,529 tahun
60 0,0036 detik 0,216 detik 12,96 detik 366 abad 1,3x1013 abad
Tabel 3.2. Waktu Proses Untuk Berbagai Algoritma
Algoritma
Kompleksitas
A1 A2 A3 A4 A5
n2 n3 n5 2n 3n
Komputer sekarang 60.000 1.533 81 32 20
Ukuran n Komputer 100 x lebih cepat 600.000 7.114 205 38,4 24,2
Komputer 1000 x lebih cepat 1.897.367 15.326 325 41,7 26,3
Tabel 3.3 Ukuran Maksimum Pemecahan Masalah Dalam Satu Jam Waktu Komputer
Tabel 3.3 memberikan masalah besar yang dapat diselesaikan dalam 1 jam oleh komputer dengan kecepatan berbeda. Untuk algoritma A4 dan A5, sebuah komputer yang cepat tidak dapat menyelesaikannya. Sebuah algoritma di mana T(n) adalah polinomial terbanyak dalam n disebut sebagai algoritma polinomial. Sebuah algoritma dikatakan eksponensial jika ada sebuah aplikasi di mana T(n) eksponensial di n. Algoritma A1 dan A3 adalah polinomial selama algoritma A4 dan A5 adalah eksponensial. Algoritma eksponensial tidak efisien dan biasanya merupakan variasi dari penelusuran ekshaustive. Tujuan kita adalah mengembangkan algoritma polinomial. Algoritma polinomial menentukan sebuah algoritma di mana T(n) eksponensial di n. Jika n2, n3, n5 maka polinomial (nk), k = 1,2,3, ... Jika 2n, 3n maka eksponen (kn), k = 1,2, ...
38
LATIHAN SOAL
1. Diberikan graf G di bawah ini : v2 v3 v1 G v4 v7
v6 v5
(a) Berikan sebuah contoh : (i)
sebuah jalan tetapi bukan lintasan,
(ii)
sebuah lintasan
(iii) sebuah cycle (b) Tentukan jarak dari v6 ke setiap simpul lainnya di graf G ! (c) Tentukan sebuah sub graf perentang di G yang tidak punya cycle. (d) Tentukan matriks adjasensi dan insidensi dari G ! 2. Berikan sebuah contoh dari graf yang (i)
tidak mempunyai simpul yang berderajat ganjil
(ii)
tidak mempunyai simpul yang berderajat genap
(iii) mempunyai 4 komponen, 6 simpul dan 3 busur (iv) 3-regular tetapi tidak lengkap. 3. (a) Misalkan m dan n adalah bilangan bulat sehingga 1 ≤ m ≤ n . Berikan contoh graf yang mempunyai n simpul dan m komponen. (b) Apakah mungkin bagi sebuah graf untuk mempunyai komponen lebih dari simpulnya ? Jelaskan !
39
4. Mana dari graf di bawah ini yang merupakan graf bipartite ?
5. Jika mungkin, gambarkan graf G yang memiliki sifat berikut, dan jika tidak ada jelaskan mengapa ? (a) G adalah graf simpel dengan derajat simpulnya 2, 3, 4, 4 dan 5 (b) G adalah graf simpel dengan tepat hanya 3 simpul yang berderajat 5 (c) G adalah graf bipartite regular yang tidak terhubung. (d) G adalah pohon dengan 5 simpul dan 6 busur (e) G adalah graf di mana untuk n simpul mempunyai lintasan dengan panjang maksimal 3 antara tiap pasangan simpul. 6. Berapa banyak busur yang mungkin dari : (a) sebuah graf bipartite (b) sebuah graf k-regular ? 7. Tunjukkan bahwa dalam sebuah graf simpel, jumlah simpul dari derajat ganjil adalah genap ! 8. Misalkan G adalah graf dengan 15 simpul yang terdapat dalam 4 komponen. Tunjukkan bahwa sedikitnya satu komponen yang mempunyai 4 simpul atau lebih!
40
9. Untuk setiap graf yang digambarkan dibawah ini, tentukan mungkin atau tidak untuk mengorientasikan tiap graf sehingga digraf yang dihasilkan mempunyai sedikitnya satu dipath antara sedikitnya dua simpul. Jelaskan !
41
BAB IV BEBERAPA ALGORITMA GRAF
Dalam bab ini, kita mempelajari sejumlah algoritma (yang dipelajari dalam Matematika Diskrit). Ada dua jenis algoritma yang kita bahas dalam bab ini, yaitu : a. Algoritma Kruskal Algoritma ini digunakan untuk menentukan pohon perentang terbobot minimum. b. Algoritma Dijkstra Algoritma ini digunakan untuk menentukan lintasan terpendek pada graf berbobot. 4.1. Pohon Perentang Terbobot Minimum Pohon perentang terbobot minimum disebut juga pohon optimal. Untuk mencari pohon optimal, harus graf terhubung. Kita hanya memodifikasikan sedikit algoritma yang diberikan sebelumnya untuk menentukan pohon perentang G. Modifikasi yang dilakukan sederhana. Pada setiap tahap pemilihan busur, pilih busur yang tidak membentuk cycle dan pilih busur dengan bobot terkecil. Algoritma Kruskal : 1. Pilih busur e1 sehingga bobot w(e1) yang paling kecil. 2. Jika busur e1, e2, ..., ek telah terpilih, pilih busur ek+1 dari busur yang belum dipilih sedemikian hingga (i)
ek+1 tidak menjadi siklus di G dengan busur e1, e2, ..., ek
(ii)
w(ek+1) sekecil mungkin berhubungan dengan (i)
3. Berhenti ketika langkah 2 tidak dapat dilanjutkan lagi. Contoh 4.1: Gunakan Algoritma Kruskal untuk menentukan pohon perentang terbobot minimum !
42
5 6
2 3
4 2
1
4 5
6
7 8 Gambar 4.1
Solusi : Busur dari pohon optimal digambarkan dalam garis tebal. (1)
(2) 5
6
5
2
6
3
2
4
1
3 2
5 7
4
1
4
2 5
6
7
4 6
8
8
(3)
(4) 5
6
5
2
6
3
4
5
4
1
2
2
7
6
3
4
5
4
1
2
7
6
8
8
(5)
(6) 5
6
2
6
3
2
4
1
3 2
5 7
5
4 6
2 5
7 8
4
1 4 6 8
Pohon perentang terbobot minimum = 17
43
LATIHAN SOAL
1. Gunakan algoritma Kruskal untuk menemukan pohon perentang terbobot minimum . 2
4
1
2 5
1 3
3
2 3
6 1
5
5 3
4
1
2
2
2 1
3 5
4 5 5
3
5
4
6
6
7
7
2. Sebuah jaringan telepon diperlukan untuk diinstall di sebuah negara baru yang terdiri dari 8 kota T1, T2, ..., T8. Biaya untuk menginstall sebuah saluran antara kota Ti dan Tj diberikan dalam matriks di bawah ini. ( ∞ menyatakan bahwa tidak mungkin untuk menginstal sebuah saluran). Diputuskan bahwa : (i)
setiap kota dapat berkomunikasi secara langsung maupun tidak langsung ke setiap kota lainnya.
(ii)
Total biaya instalasi diminimumkan.
Gambarkan sebuah jaringan dengan tujuan di atas ! T1 T1 0 T2 20 T3 15 T4 ∞ T5 ∞ T6 10 T7 10 T8 5
T2 20 0 30 15 5 5 ∞ 10
T3 15 30 0 10 17 ∞ 11 8
T4 ∞ 15 10 0 3 5 40 9
T5 ∞ 5 17 3 0 21 12 ∞
T6 10 5 ∞ 5 21 0 31 70
T7 T8 10 5 ∞ 10 11 8 40 9 12 ∞ 31 70 0 ∞ ∞ 0
3. The White Country, yang terletak di daerah bersalju, Ontario Pusat, terdiri dari 8 kota T1, T2, ..., T8. Beberapa badai salju membuat salju-salju menutupi sebagian jalan-jalan di daerah tersebut. Selain badai salju, masalah utama yang sering terjadi adalah pembukaan kembali jalan-jalan. Waktu dalam jam, diperlukan untuk membersihkan jalan, dengan menggunakan peralatan yang
44
lengkap, sehingga pengembalian jalan untuk transportasi antara kota Ti dan Tj diberikan dalam matriks di bawah ini. ∞ menyatakan bahwa tidak ada jalan langsung yang menghubungkan kota Ti dan Tj. T1 T1 0 T2 1,5 T3 3 T4 ∞ T5 ∞ T6 4,5 T7 0,75 T8 1,0
T2 T3 1,5 3,0 0 ∞ ∞ 0 ∞ 0,5 4,5 1, 25 1,5 3,0 2,0 8,0 ∞ 10,5
T4 T5 T6 T7 T8 ∞ ∞ 4,5 0,75 1,0 ∞ 4,5 1,5 2,0 ∞ 0,5 1,25 3,0 8,0 10,5 0 3,0 2,5 1,8 ∞ 3,0 0 3,75 5,25 ∞ 2,5 3,75 0 ∞ ∞ 1,8 5,25 ∞ 0 1,5 ∞ ∞ ∞ 1,5 0
Transportasi jalan dapat dibuka kembali jika memungkinkan untuk dilalui dengan jalan antara dua kota. Tujuan pertama adalah membuka kembali transportasi jalan di daerah tersebut secepat mungkin. Bagaimana cara mencapai tujuan ini ? Anda dapat mengasumsikan bahwa waktu yang diperlukan untuk memindahkan peralatan dalam membersihkan jalan diabaikan. 4. Empat kota C1, C2, C3 dan C4 diletakkan pada sudut dari sebuah persegi. Kota kelima C5 diletakkan di tengah persegi yang dihubungkan oleh C1, C2, C3 dan C4. Biaya untuk membangun jalan antara dua kota sebanding dengan jarak antara kedua kota tersebut. Tentukan biaya termurah
yang
dapat
menghubungkan kelima kota tersebut !
45
4.2. Lintasan Terpendek Dalam kehidupan sehari-hari kita sering dihadapkan pada permasalahan untuk menentukan lintasan terpendek dari suatu tempat ke tempat lain. Misalnya dalam masalah transportasi, jaringan dapat menggambarkan jalan yang menghubungkan satu kota dengan kota-kota lainnya, dan sepanjang jalan yang menghubungkan satu kota (sebagai kota asal) ke satu kota lainnya (sebagai kota tujuan) disebut lintasan. Kita mengetahui bahwa untuk menuju ke satu kota tujuan dapat ditempuh melalui beberapa lintasan. Dalam hal ini, kita akan menentukan kota-kota atau jalan manakah yang harus dilalui sehingga kita dapat mencari tempat tujuan dengan jarak terpendek. Dengan demikian lintasan terpendek dapat diartikan sebagai bobot minimal dari suatu lintasan, yaitu jumlah bobot dari seluruh busur yang membentuk lintasan. Pada
jaringan
G(S,B,W)
terdapat
minimal
satu
lintasan
yang
menghubungkan sumber dan tujuan. Kita akan memilih salah satu bilangan terkecil di antara sejumlah bilangan yang menyatakan bobot dari suatu lintasan. Jelas hanya terdapat satu bilangan yang memenuhi. Dengan kata lain hanya terdapat satu bobot lintasan yang memenuhi, sedangkan lintasannya sendiri dapat lebih dari satu dengan bobot yang sama. Ada beberapa metode yang dapat digunakan untuk menentukan lintasan terpendek, yaitu metode Dijkstra, Moore, Bellman, Matriks, dan Ford. Selain beberapa metode tersebut masih terdapat metode lainnya sebagai pengembangan dari metode Ford, yaitu Hert et al (1968), Floyd (1962), Spira (1973), serta Johnson (1973). Akan tetapi, yang kita bahas dalam bab ini hanya metode Dijkstra. Length merupakan jumlah bobot dari lintasan, sedangkan bobot minimum dari lintasan (u,v) disebut distance d(u,v). Bobot minimum lintasan disebut lintasan terpendek. Jika e ∉ E (G ) maka w(e) = ∞ Asumsi mencari lintasan terpendek yaitu : 1. G merupakan graf simpel 2. Semua bobot di G positif
46
Observasi Penting : 1. Jika P = u0, u1, ..., uk, uk+1 adalah lintasan terpendek (u0, uk+1) di G, maka bagian (u0, ui) yaitu u0, u1, ..., ui, 1 ≤ i ≤ k dari P adalah lintasan terpendek (u0, ui) di G. Jadi, d(u0, uk+1) = d(u0, uk) + w (uk, uk+1).
(4.2.1)
2. Jika S adalah himpunan bagian dari V, maka u0 ∈S dan lintasan terpendek dari u0 ke simpul lainnya di S diketahui. Misal S = semua simpul kecuali di S. Kita definisikan jarak dari u0 ke S sebagai berikut : d(u0, S ) = min{d (u0 , v)}
(4.2.2)
v∈S
Hal ini merupakan cara untuk menentukan simpul S yang terdekat ke u0. Jelas bahwa P = u0, u1, ..., uk, uk+1 adalah lintasan terpendek dari u0 ke S . Jadi d (u0 , S ) = min {d (u0 , u ) + w(uv)}
(4.2.3)
u ∈S v∈S
Untuk graf yang disajikan di bawah ini (busur dari lintasan terpendek ditunjukkan oleh garis tebal) d(u0, S ) = 7, dan v2 adalah simpul S yang dekat ke u0. Lintasan u0, u1, u2, v2 adalah lintasan terdekat (u0, v2) di G. u1
2
u4
v5 8
1
4 5
2 5 u0
v1
5 6
1
3
4
u2
u5
2
v4
4 3
3
5
8 10
u3
v2
7 v3
Gambar 4.2
S = {u0, u1,…, u5}
S = {v1, v2,…, v5}
Persamaan 4.2.3 memberikan suatu prosedur untuk menemukan lintasan terpendek dari simpul spesifik u0 ke setiap simpul lain di G. Gagasan dasarnya adalah : dimulai dari himpunan S0 = {u0} sebuah barisan naik S0, S1, ..., Sn-1,
47
n= V (G ) , terhubung dalam cara yang sama dan berakhir pada tahap i, lintasan terpendek dari u0 ke semua simpul di Si diketahui. Algoritma Dijkstra : 1. Tentukan u0 paling kiri. Biasanya u0 diberi tahu. 2. Lintasan berakhir paling ujung. 3. Lintasan atau busur yang dilalui tidak boleh membentuk cycle. 4. Harus berurutan pemberian labelnya pada tiap simpul. 5. Carilah busur dengan bobot yang paling minimum. Contoh 4.2 : Carilah lintasan terpendek dari u0 ke setiap simpul lainnya, dari graf di bawah ini ! 5 1
2 5
6
2
5
2
6
u0 3
4
3
4
1 8 Gambar 4.3
Solusi : Gambar-gambar untuk menentukan lintasan terpendek dari graf pada Gambar 4.3 di atas, disajikan di bawah ini. Busur yang merupakan lintasan terpendek, diberi garis tebal. 5 1
2 5
6
2
5
2
6
u0
S0 = {u0} 3
4
3
4
1 8 u1
1
5
2 5
6
2
5
2
6
u0
S1 = {u0, u1} 3
4
4
3 1
8
48
u1 1
5
2 5
6
u2
2
5
2
6
u0
S2 = {u0, u1, u2} 3
4
3
4
1 8 u1
1
5 2
5
6
u2
2
5
2
6
u0
S3 = {u0, u1, u2, u3} 3
4
3
4
1 u3
8
u1 1
5
2 5
u2
6 2
2 u4
5 6
u0
S4 = {u0, u1,…, u4} 3
4
3
4
1 u3
8
u1 1
5 2
5
u2
u5
6 2
2 u4
5 6
u0
S5 = {u0, u1,…, u5} 3
4
3
4
1 u3
8
u1 1
5 2
5
u2
u5
6 2
2 u4
5 6
u0
S6 = {u0, u1,…, u6} 3
4
3
4
1 u3
8
u6
49
u1 1
5 2
5
u2
u5
6
2 u4
2
5 6
u0
u7 S7 = {u0, u1,…, u7} 3
4
3
4
1 u3
8
u6
Lintasan terpendek = 29 Secara ringkas, algoritma Dijkstra dapat dituliskan di bawah ini : 1. Misal l(u0 ) = 0 , l(v) = ∞ untuk v ≠ u0 , S 0 = {u0 } dan i=0. 2. Untuk setiap v ∈ Si , ganti l(v) dengan min{ l(v), l(ui ) + w(ui v )}. Hitung min {l(v )} dan misal ui+1 menyatakan sebuah simpul di mana minimum v∈ S i
didapat. Maka Si +1 = Si ∪ {ui +1} . 3. Jika i = V (G ) − 1, berhenti. Jika tidak ganti i dengan i + 1 dan lanjutkan ke langkah 2. Contoh 4.3 : Untuk graf pada Gambar 4.4, carilah lintasan terpendek dari u0 ke setiap simpul lainnya dengan menggunakan algoritma Djikstra ! 1
8
2
5 4 8
1 2 4
u0
3
2
4
2
3
6
2 2
3 Gambar 4.4
Solusi : Gambar-gambar untuk menentukan lintasan terpendek dari graf pada Gambar 4.4 di atas, disajikan di bawah ini. Busur yang merupakan lintasan terpendek, diberi garis tebal.
50
∞
∞ 1
8
∞
2
5
4 0
8
u0
2
∞
3
∞
2
3
∞
6
2
2
3
∞
∞
∞
2 u1 1
8
∞
2
5
4 8
u0
2
∞
3
∞
2
1
3
∞
6
2
2
3
6
∞ ∞
2 u1 1
3
8
2
5 4 8
u2 3
2 4
u0 2
1
2 3
6
∞
2 u1
11 1
2
3
8
4 8
5 u3
5 u2 3
2 4
∞
2
2
1
∞
4 3
6
6 2 6
∞
4 3
2
u0
∞
2
∞
6
0
∞
4
4 2
0
∞
4
4 2
0
1
2 3
∞
51
2 u1
11 1
2 0
3
8
4 8
u0
5 u3
5 u2 3
2 4
∞
2
2 6 6 u4
2
2
3 ∞
2 u1
11 1
2
3
8
4 8
u0
5 u3
5 2 4
2
u2 3
∞
2
6 u5
6 6 u4
3 ∞ 8 u6 3
8
4 8
u0
5 u3
5 2 4
2
u2 3
∞
2
6 u5
6 6 u4
0
3 9 8 3
u6
8
4 8
5 u3
5 2 4
2
u2 3
1 2
9
6 u5
6 6 u4
∞
4
2
2
1
u0
1
3
2 u1 2
∞
4
2
2
1
0
1
3
2 u1 2
∞
4 3
6
0
1
2
4
13
3 2 3
9 u7
52
2 u1
8 1
2 0
3
8
4 8
u0
5 u3
5 2 4
2 6 u4
u2 3
1 2
4
2
2
3
2 u1 3
u6
8
4 8
u0
9 u7
8 1
2
5 u3
5 2 4
2
u2 3
1 2
4
2
11 u9
9 u8 3
6 u5
6 6 u4
11
9 u8 3
6 u5
6
0
u6
2 3
9 u7
53
LATIHAN SOAL
1. Untuk setiap graf di bawah ini, gunakan algoritma Djikstra untuk menemukan lintasan terpendek dari u0 ke setiap simpul lainnya. Anda diharuskan untuk menggambarkan graf per tahap, sehingga masing-masing pelabelan dapat digambarkan dengan jelas. (i) 1 2
6
2
5
9
7
9
3 u0
8
1
6
7
2
4
2
3
1
1
4 9
1
(ii) 4 2 2 5 u0
1 3
2
4 6
1
3
2 1
3
5
1
5
4 (iii) 1 2
5 3
4
6
4
3
3
2 2
3
u0 2
6
1
4
5
5
3
2
3
2
1
1
54
(iv) 2 3
1
1 3
6
4 3
u0
4 5
5
6
2
1
4
5
1
1
5 7 2
2. Sebuah paket berisi barang-barang asli di Los Angeles dapat dikirimkan ke Boston melalui beberapa rute berbeda, yang ditunjukkan di bawah ini. Bobot tiap busur menyatakan biaya transportasi atau pengiriman paket antar kota yang berhubungan. Gunakan algoritma Djikstra untuk menemukan rute terpendek yang dapat meminimumkan biaya dari Los Angeles ke Boston! H
A
58 130
F
48
40 B 85
58
29 66 D
43
75
63 27
29
53 G
C
28 85
A B C D E
25 I
= = = = =
Portland Salt Lake City Los Angeles Kansas City Dallas
E
F G H I
= = = =
Chicago Memphis Boston Washington
3. Sebuah perusahaan perbankan dengan kantor pusat di New York (NY) mempunyai beberapa cabang utama di London (L), Paris (P), Zurich (Z), Roma (R), Berlin (B), Montreal (M), dan Vienna (V). Setiap hari informasi penting (meliputi rata-rata pertukaran mata uang, dan lainnya) harus
55
diinformasikan dari kantor pusat ke kantor cabang. Biaya pengiriman pesan melalui teleks antara dua kantor cabang, diberikan pada matriks di bawah ini. NY L P Z R B NY 0 8 10 12 9 11 L 8 0 3 3 2 2 P 10 3 0 1 2 3 Z 12 3 1 0 2 5 R 9 2 2 2 0 8 B 11 2 3 5 8 0 M 3 1.000 8 1.000 1.000 1.000 V 15 10 1.000 1.000 1.000 1.000
M 3 1.000 8 1.000 1.000 1.000 0 1.000
V 15 10 1.000 1.000 1.000 1.000 1.000 0
Tentukan rute komunikasi termurah antara kantor pusat dengan setiap kantor cabang lainnya ! 4. Pelayaran dengan tujuan untuk mengirimkan barang-barang bekas melakukan perjalanan dari Coquitlam ke Saskatoon. Rute-rute yang mungkin ditunjukkan di bawah ini. Bobot untuk tiap busur menyatakan biaya pengiriman barangbarang bekas antara kota yang berhubungan. Gunakan algoritma Djikstra untuk menentukan rute terpendek yang dapat meminimumkan total biaya transportasi ! H E
20 43 42 F
62 42
B
18 I
K 56
26 48
5 31 A
24 20
32 40
39
C 5 D
22
41 J
52
61
16
L
G
A B C D E F
= = = = = =
Coquitlan Kamlocpe Kelama Penticton Jasper Golden
G H I J K L
= = = = = =
Cranbrook Bdmonton Calgary Swift Current Saskatoon Regina
56
5. Berdasarkan jaringan di bawah ini, bobot busur menyatakan kemungkinan yang diberikan oleh fungsi busur. 90 2
4
80 1
70
90
80
80 3
5 75
Tentukan rute yang handal atau efektif dalam jaringan tersebut !
57
KONSEP LEBIH JAUH DALAM TEORI GRAF
Dalam Bab 3, kita mempelajari beberapa konsep dasar dalam teori graf, di mana sebagian besar telah dipelajari dalam Matematika Diskret. Dalam bab ini, kita memperkenalkan beberapa konsep dan ide lebih jauh dalam teori graf. Tujuan pertama adalah mengilustrasikan beberapa metode pembuktian dalam teori graf. Kita mulai dengan memperkenalkan beberapa notasi yang sering digunakan dalam teori graf. Untuk sebuah graf G : V(G) = jumlah simpul di G ε (G) = jumlah busur di G d(u) = derajat simpul u di G δ (G) = derajat paling minimum di G ∆ (G) = derajat paling maksimum di G Derajat suatu simpul sama dengan dua kali jumlah busurnya.
∑ d (v) = 2ε (G)
(5.1)
v∈v ( G )
Sebagai akibatnya, sebuah graf simpel mempunyai jumlah genap dari simpul berderajat ganjil. Teorema 1.1 : Untuk graf G, buktikan bahwa δ ≤
2ε ≤∆ ! v
Bukti : Dari (5.1) kita memperoleh 2ε =
∑ d ( v)
v∈v ( G )
≥ δv sehingga δ ≤ 2ε =
2ε dan v
∑ d ( v)
v∈v ( G )
≤ ∆v sehingga
2ε ≤∆ v
58
Jadi terbukti bahwa δ ≤
2ε ≤ ∆. v
Untuk kesimpulan selanjutnya dengan mudah dinyatakan bahwa himpunan simpul yang berdampingan ke sebuah simpul u dinyatakan dengan N(u) dan yang berjauhan dinyatakan dengan N (u). Dengan kata lain N(u) sebagai tetangga dari u dan N (u) bukan tetangga dari u. Teorema 5.2 : 1 Misal G adalah graf simpel dengan δ ≥ v ( x ) menunjukkan bilangan bulat x, 2 maka G terhubung. Bukti : Misal d(u) = δ . Ambil himpunan lain N(u) dari u 1 N (u ) ≥ v 2 1 N (u ) ≤ v − v − 1 2 1 w ∈ N (u ) maka N (u ) − 1 ≤ v − v − 2 < δ 2 Titik N (u ) harus berhubungan dengan sedikitnya satu titik di N (u ) . Jadi G terhubung. Teorema 5.3 : G adalah graf dengan δ ≥ 2 . G punya cycle. Bukti : P = v0, v1, v2, ..., vl lintasan terpanjang di G
v0 v1 v2 vk vl v0 ada di P. Karena δ ≥ 2 , v0 dihubungkan ke beberapa simpul vk dengan 1
59
Teorema 5.4 : G adalah graf dengan ε ≥ v . G punya cycle. Bukti : P(n) adalah Graf G dengan n simpul dari ε ≥ n punya cycle. Langkah 1 : Jika v = 1 dan ε ≥ 1 , g punya sedikitnya 1 loop dan memiliki cycle yang panjangnya satu. P(1) terbukti. Langkah 2 :
(Langkah induktif) P(n) benar dan g graf dengan simpul n+1 dan ε ≥ n + 1 . Jika δ (G ) ≥ 2 , G punya cycle.
δ (G ) < 2 dan v simpul di G dengan d (v ) ≤ 1 . Maka graf G-V didapat dengan menghapus v dan semua busur insiden ke v memiliki ε (G − V ) ≥ n = V (G − V ) . Jadi G-V punya cycle dan G punya cycle. P(n+1) benar jika P(n) benar. BARISAN DERAJAT Menyatakan banyaknya busur yang insiden dengan simpul. Jika V(G) = {v1, v2, ..., vn}, barisan (d(v1), d(v2), ..., d(vn)) disebut barisan derajat G. Contoh 5.1 : Perhatikan graf di bawah ini. v3
v1 v5
v2
v4 Barisan derajat dari G : (v1, v2, v3, v4, v5) = (1, 5, 4, 4, 4)
60
Teorema 5.5 : Sebuah barisan (d1, d2, ..., dn) dari bilangan bulat tak negatif adalah barisan derajat n
dari G jika dan hanya jika
∑d i =1
i
genap.
Bukti : Kita akan membuktikan 2 kenyataan : n
(i)
Jika (d1, d2, ..., dn) adalah barisan derajat maka
∑d i =1
i
= genap. (syarat
cukup) (ii)
Jika (d1, d2, ..., dn) adalah barisan dari bilangan bulat tak negatif maka n
∑d i =1
i
genap, maka ada graf yang memiliki barisan derajat (d1, d2, ...,
dn). (syarat perlu) Bukti : Untuk membuktikan (ii) buat graf dengan barisan derajat (d1, d2, ..., dn) seperti ini. n
V(G) = {v1, v2, ..., vn}, karena
∑d i =1
i
genap, jumlah simpul di yang
ganjil adalah genap. Pasangkan di dan gabungkan setiap pasangan dengan satu busur. Tambahkan loop sebesar
di pada setiap simpul i. 2
Jadi graf yang dihasilkan akan memiliki barisan derajat (d1, d2, ..., dn). Contoh 5.2 : Bentuk graf dengan barisan (4, 1, 3, 6, 5, 1) ! v1
v6
v2
v5
v3
v1
v6
v5
v2
v3
61
v4 Ada 4 komponen yang tidak terhubung.
v4
Graf dikatakan grafik jika ada graf simpel dengan barisan derajat d. Contoh 5.3 : Apakah barisan berikut grafik ? 1. (4, 1, 3, 6, 5, 1) 2. (6, 6, 5, 5, 4, 3, 1) Jawaban : 1. (4, 1, 3, 6, 5, 1) berarti ada 6 simpul. Derajat maksimum pada graf simpel dengan 6 simpul adalah 5. Jadi bukan grafik. Derajat maksimum = Jumlah simpul – 1 2. (6, 6, 5, 5, 4, 3, 1) berarti ada 7 simpul. Andai G grafik, v1 dan v2 menyatakan dua simpul di G dengan derajat g. Karena G punya 7 simpul, v1 dan v2 berdampingan maka v1 dan v2 berdampingan ke simpul di G lainnya dengan menunjukkan bahwa δ (G ) ≥ 2 . Jadi G bukan grafik. Teorema 5.6 : Misal d = (d1, d2, ..., dn) adalah barisan tidak naik dari bilangan bulat tidak negatif, dan menyatakan barisan ( d 2 − 1, d 3 − 1,..., d d1 +1 − 1, d d1 + 2 ,..., d n ) oleh d`. Maka d adalah grafik jika dan hanya jika d` grafik. Bukti : Misalkan d` adalah grafik. Maka dengan definisi, ada sebuah graf simpel G` dengan V(G`) = {v2, v3, ..., vn} yaitu : d − 1, jika 2 ≤ i ≤ d1 + 1 dG `(vi ) = i d i , jikad1 + 2 ≤ i ≤ n Sebuah graf baru dapat digambarkan dengan menghubungkan sebuah simpul baru, v1 ke G` dan menggabungkan v1 ke v2, v3, ..., vd 1 +1 . Jelas G adalah simpel dan
62
mempunyai d sebagai barisan derajat. Maka d juga grafik. Misal d adalah barisan grafik. Maka G ada dengan V(G) = {v1, v2, ..., vn} sehingga d(vi) = di untuk 1 ≤ i ≤ n . Kita mempunyai dua kemungkinan. Kemungkinan 1 : v1 berdampingan dengan v2, v3, ..., vd 1 +1 . Maka graf G-v1 mempunyai barisan derajat d` sehingga grafik. Kemungkinan 2 : v1 tidak berdampingan dengan semua simpul v2, v3, ..., vd 1 +1 . Maka harus ada simpul vj dan vk dengan j < k sehingga v1 berdampingan ke vk tetapi tidak ke vj. Kita dapat memisalkan dj > dk selama jika dj = dk kita dapat mengubah vj dan vk. Jadi harus ada sebuah simpul vm misalnya, yang berdampingan ke vj tetapi tidak ke vk. Misal G` adalah graf yang diperoleh dari G dengan menghapus busur v1 vk dan vmvj dan menambah busur v1 vj dan vkvm. v1
vj
v1
vj
vk
vm
vk
vm
G G΄ Jelas bahwa G` mempunyai barisan derajat d. Tetapi di G`, jumlah derajat dari simpul yang berdampingan dengan v1 lebih luas dari pada di G. Akibatnya, jika kita melanjutkan prosedur ini, kita mengakhiri sebuah graf dengan barisan derajat d di mana v1 memenuhi hipotesis dari kemungkinan pertama. Jadi d adalah grafik. Catatan : Pembuktian-pembuktian di atas memberikan gambaran algoritma untuk menguji apakah suatu barisan grafik atau tidak. Kita ilustrasikan dalam contoh berikut. Contoh 5.4 : Tunjukkan apakah barisan ini grafik ? Jika ya, buat grafnya ! 1. (4, 4, 3, 2, 1, 0) 2. (5, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0) Solusi :
63
1. (4, 4, 3, 2, 1, 0) adalah grafik jika dan hanya jika (3, 2, 1, 0, 0) adalah grafik. Akan tetapi (3, 2, 1, 0, 0) adalah
bukan grafik. Tidak ada graf yang
menyatakan simpel. 2. (5, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0) adalah grafik jika dan hanya jika (2, 2, 2, 2, 1, 2, 2, 1, 1, 1, 0) adalah grafik. Disusun kembali (2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 0) adalah grafik jika dan hanya jika (1, 1, 2, 2, 2, 1, 1, 1, 1, 0) adalah grafik. Disusun kembali (2, 2, 2, 1, 1, 1, 1, 1, 1, 0) adalah grafik jika dan hanya jika (1, 1, 1, 1, 1, 1, 1, 1, 0) adalah grafik. Jadi barisan ini merupakan grafik. Graf dari barisan di atas disajikan di bawah ini.
(1,1,1,1,1,1,1,1,0)
(2,2,2,1,1,1,1,1,1,0)
(2,2,2,2,2,2,1,1,1,1,0)
(5,3,3,3,3,2,2,2,1,1,1,0)
64
Penggambaran grafik dimulai dari yang paling akhir. Bentuk grafnya tidak tunggal.
APLIKASI TEORI GRAF DALAM KIMIA Bentuk struktur dari susunan kimia adalah sebuah diagram yang menyatakan ikatan antara atom-atom dalam molekul. Sebagai contoh, H
H
C
H
H
H C1H4 (Metana)
H
H
C
C
H
H
H
C2H6 (Etana)
H O O
S
O
O H SO4H2 (Asam Sulfat) Jadi jelas bahwa sebuah struktur hanya bagian khusus dari graf. Bentuk modelnya adalah : Ikatan Kimia
Model Graf
ATOM
SIMPUL
IKATAN
BUSUR
65
Dengan
catatan
bahwa
komposisi
kimia
tersebut
tidak
cukup
untuk
mengidentifikasikan substansi, selama ada substansi yang mempunyai komposisi kimia yang sama tetapi berbeda bentuk fisiknya. Sebagai contoh,
H
H
H
H
C
C
C
C
H
H
H
H
H
H
C4H10 (Butana) H
H
C
H
H
H
H
C
C
H
C
H
H H C4H10 (Iso-butana)
Atom-atom di atas disusun dalam bentuk yang berbeda. Teorema berikut menunjukkan bagaimana teori graf dapat diaplikasikan ke dalam hasil informasi tentang susunan kimia. Teorema 5.7 (Cayley) : Struktur dari parafin (hidrokarbon) CnH2n+2 direpresentasikan dalam bentuk pohon. Bukti : Sebuah parafin adalah molekul di mana setiap atom karbon mempunyai 4 ikatan dan setiap atom hidrogen mempunyai satu ikatan. Misal G adalah graf yang
66
menggambarkan molekul tersebut. Kemudian setiap simpul G mempunyai derajat 1 atau 4. Selanjutnya v(G) = 3n + 2 dan ε (G ) =
1 ∑ deg(v) 2 v∈V (G )
1 = [4n + 2n + 2] 2 = 3n + 1 = v(G) – 1 Jadi G pasti adalah pohon.
PERMASALAHAN DOKUMENTASI KIMIA
Permasalahan dasar adalah memberi sebuah nama yang tunggal untuk setiap struktur kimia. Seorang ahli kimia yang mengisolasi beberapa susunan dari produk alami secara jelas ingin mengetahui : (i)
mungkin atau tidak susunan itu telah diketahui,
(ii)
semua susunan yang telah diketahui yang mengandung sebuah fragmen pasti merupakan bagian dari keseluruhan susunan kimia tersebut.
ISOMORFIK Dua buah graf dikatakan isomorfik (G1 ≅ G2) jika ada pemetaan satu-satu dari simpul G1 ke G2 yang menunjukkan kedekatannya. Contoh 5.5 : Berdasarkan graf G1 dan G2 yang ditunjukkan di bawah ini : u1
u2
u3
v4
v2
v1
u4
u5
u6
v5
v6
v3
67
G1 G1 ≅ G2 selama pemetaan φ : V (G1 ) → V (G2 )
G2
didefinisikan oleh φ (ui ) = vi , i = 1, 2, ..., 6 adalah sebuah pemetaan satu-satu yang membentuk kedekatan.
PERMASALAHAN KODING DALAM TEORI GRAF Temukan sebuah algoritma yang baik untuk memberikan setiap graf sebuah kode tunggal yang merupakan sebuah simbol string, dengan cara yang sama, dua graf diberikan kode yang sama jika dan hanya jika keduanya isomorfik. PERMASALAHAN ISOMORFISMA GRAF Temukan sebuah algoritma yang baik untuk menentukan mungkin atau tidak dua graf yang diberikan isomorfik. PERMASALAHAN ISOMORFISMA SUB GRAF Diberikan dua graf G dan H. Temukan sebuah algoritma yang baik untuk menentukan mungkin atau tidak sub graf dari G isomorfik dengan H. Catatan : 1. Permasalahan koding hanya permasalahan dokumentasi kimia. 2. Permasalahan isomorfisma sub graf membuat kimiawan tertarik untuk meletakkan semua susunan yang diketahui. 3. Permasalahan isomorfisma graf tidak sesederhana dapat menjadi pembuktian pada akhir latihan bab ini. PENGUJIAN ISOMORFISMA Apakah G1 ≅ G2 ? BRUTE FORCE 1. Beri label salah satu graf, misalnya G1. Hasilnya akan terbentuk sebuah matriks adjasensi yang tunggal untuk G1.
68
2. Untuk setiap pelabelan yang mungkin bagi G2, periksa mungkin atau tidak menghasilkan matriks adjasensi yang sama dengan G1 ?
KOMPLEKSITAS Dalam kemungkinan terburuk prosedur di atas membutuhkan k.n2.n! operasi, di mana k adalah sebuah konstanta dan n = V (G ) . Eksponensial ! PERBAIKAN KEMBALI Simpul-simpul diklasifikasikan ke dalam kelas-kelas menurut beberapa graf yang sejenis. Dalam simpul-simpul yang isomorfisma di G1 harus dipetakan secara onto ke simpul-simpul yang berhubungan di G2. Hal ini memberikan sedikit latihan permutasi. FORMULA CAYLEY UNTUK MENGHITUNG POHON PERENTANG Permasalahan yang ada adalah bagaimana menentukan jumlah pohon perentang yang mungkin. Sebuah busur e dikatakan berhimpit jika dihapus dan ujungnya diidentifikasi. Graf yang dihasilkan dinotasikan dengan G.e. Berikut diberikan ilustrasi dari definisi ini. Contoh 5.6 : v1
e1
vj
{v1v3}
e1
v2
e2 e4
v4
e
e3
e2
e4
v3
v4
G
G.e
e1 v1
e3
{v1v2} v2
e2
69
e2 e3
e4
e3
e4
v3 G
G.e1
Ingat v(G.e) = v(G) – 1 ε (G.e) = ε (G ) − 1 dan jumlah komponen G.e sama dengan jumlah di G. Jadi, jika G adalah pohon, maka G.e juga. Notasi : τ (G ) : jumlah pohon perentang di G Teorema 5.8 : Jika e adalah sebuah busur dari loop di graf G, maka τ (G ) = τ (G − e) + τ (G.e) Bukti : Kita dapat mengasumsikan bahwa G terhubung dengan tujuan teorema ini adalah benar. Selama setiap pohon perentang di G tidak mengandung e, maka juga merupakan sebuah pohon perentang G – e, dan τ (G − e) = # jumlah pohon perentang di G yang tidak mengandung e. Untuk setiap pohon perentang T di G yang mengandung e, ada hubungan pohon perentang T.e di G.e. Maka τ (G.e) = # jumlah pohon perentang di G yang mengandung e. Terbukti. Teorema 5.8 memberikan sebuah metode untuk menentukan τ (G ) . Kita ilustrasikan hal ini dalam contoh berikut. Contoh 5.7 : Gunakan rumus rekursif dari Teorema 5.8 untuk menentukan jumlah pohon perentang dari graf di bawah ini !
70
Solusi : Untuk kemudahan, tebalkan busur yang menunjukkan busur e di mana rumus rekursif diterapkan. τ
= τ
+ τ
= τ
+ τ
τ
+ τ
+
= 5 + 2τ
τ
= 5 + 2τ
+
+ τ
. τ
+ 3 + 4
= 24 Catatan : 1. Teorema 5.8 memberikan sebuah metode untuk menghitung τ (G ) yang tidak tepat untuk graf yang besar. 2. Untuk G ≅ K n , Cayley membuktikan bahwa τ ( K n ) = n n − 2 . 3. Ada sebuah formula tertutup untuk τ (G ) yang menyatakan τ (G ) sebagai sebuah determinan. 4. Jika G = G1 ∪ G2 dengan V(G1) ∩ V(G2) = {u} maka τ (G ) = τ (G1 ) × τ (G2 ).
71
Sebagai contoh, G1
G2
G
τ (G ) = τ (G1 ) × τ (G2 ). Penggunaan rumus di atas menjelaskan bahwa Contoh soal 5.7 dapat disederhanakan menjadi : τ (G)
= τ
+ τ
= τ
+ τ
= 0 + τ
+ τ
+ 16
+ 16
= 3 + 5 + 16 = 24
72
LATIHAN SOAL
1. Dalam setiap kemungkinan, gambarkan jika mungkin, sebuah graf G dengan sifat-sifat berikut; jika tidak jelaskan mengapa graf ini tidak ada ! a. Diameter (G) = 3, ∆(G ) = 4 , dan v(G) = 54. b. G adalah graf simpel dan mempunyai simpul dengan derajatnya 8, 6, 5, 4, 4, 3, 3, 3, 3, 0, 0. c. G adalah 5-regular, v(G) =13 dan ε (G ) = 28 . d. G adalah simpel, tidak terhubung, δ (G ) = 7 , dan v(G) = 14. e. G adalah sebuah pohon dengan sedikitnya 3 simpul yang isomorfik. f. G adalah sebuah graf simpel berderajat ganjil dengan 1-regular sub graf perentang. g. G adalah sebuah graf simpel 4-regular graf bipartite. h. G mempunyai barisan derajat (6, 6, 5, 5, 1, 1). i. Diameter (G) = 2, ∆(G ) = 4 , dan v(G) = 20. j. Diameter (G) = 2, δ (G ) = 3 , dan v(G) = 10. k. G adalah sebuag graf simpel, mempunyai 4 komponen, v(G) = 20, dan ε (G ) = 15 . 2. Apakah barisan berikut grafik ? Jika ya, gambarkan graf dengan barisan derajat tersebut ! a. 4, 3, 3, 3, 2, 2, 2, 1, 0. b. 8, 7, 6, 5, 4, 3, 2, 2, 1, 0, 0. c. 5, 5, 5, 4, 4, 4, 4, 4, 0. d. 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1.
73
e. 7, 6, 4, 4, 4, 3, 3, 3, 3, 1, 1, 0. f. 5, 4, 4, 3, 3, 2, 2, 1, 0, 0. g. 6, 6, 5, 5, 4, 4, 3, 2, 2, 1, 0, 0. h. 8, 6, 5, 4, 4, 3, 3, 3, 2, 0, 0.
3. Tentukan jumlah pohon perentang dari graf di bawah ini ! a.
b.
c.
d.
e.
f.
g.
4. Tentukan jumlah pohon yang tidak isomorfis dari graf di bawah ini ! a. b.
74
5. Dalam masing-masing kemungkinan, tentukan mungkin atau tidak graf berpasangan yang diberikan berikut adalah isomorfik ! a.
b.
c.
d.
75
e.
f.
6. Komplemen G dari graf simpel G adalah graf dengan himpunan simpul V(G), dua simpul menjadi berdampingan di G jika dan hanya jika kedua simpul ini tidak berdampingan di G. Tentukan komplemen dari graf berikut ! a.
c. Km, n
b.
d. Kn
7. Sebuah graf adalah self-complementary jika G ≅ G . Apakah graf di bawah ini self complementary ? Buktikan jawabanmu ! a.
b.
c.
d.
76
e.
77
DAFTAR PUSTAKA
Chartrand, Gary & Oellermann, Ortrud R. 1993, Applied and Algorithmic Graph Theory, McGraw-Hill, Inc. McHugh, James A. 1990, Algoritmic Graph Theory, Prentice-Hall International, Inc.
78
79
