2. Sirkuit [Cycle] adalah suatu lintasan tertutup dengan derajat setiap simpul dua. Struktur Pohon adalah salah satu kasus dalam graf. Penerapannya pada Teori Struktur Data. Daun adalah titik di dalam Pohon yang berderajat 1. Titik dalam Pohon yang berderajat > 1 disebut Titik Cabang.
Apa itu subgraf?
Adapun subgraf dari suatu graf G adalah suatu graf yang memiliki verteks – verteks yang merupakan himpunan bagian tak kosong dari himpunan verteks graf G dan rusuk – rusuknya adalah himpunan bagian dari himpunan rusuk graf G, selain itu setiap rusuk di dalam subgraf itu yang bersesuaian dengan rusuk dari graf G harus …
Apa saja 2 syarat pohon berakar?
Sebuah pohon pada graph G yang memuat semua titik G disebut pohon rentang dari G. Pohon berakar adalah graph berarah [digraph] T yang memenuhi dua syarat: [1] Bila arah sisi-sisi pada T diabaikan, hasil graph tidak berarahnya merupakan sebuah pohon, dan [2] Ada titik tunggal R sedemikian hingga derajat masuk R adalah 0 …
Apa yang membedakan pohon dengan sirkuit dalam graf?
Dalam pohon hanya ada satu jalur antara dua simpul sedangkan grafik dapat memiliki jalur searah dan dua arah antara node. Di pohon, tepat ada satu simpul root, dan setiap anak hanya dapat memiliki satu orangtua. Sebagai lawan, dalam grafik, tidak ada konsep simpul akar.
Apa yang dimaksud dengan graf pohon?
Dalam teori graf, sebuah pohon adalah graf tak berarah yang setiap dua simpul [vertice] atau titiknya [node] saling terhubung melalui hanya sebuah sisi [edge] atau garis [line], dan tidak membentuk sirkuit atau putaran [asiklik].
Apa itu degree pada graph?
Degree atau derajat dari vertex vi adalah banyaknya edge yang insident pada vertex vi dalam graph G dan loop dihitung dua kali. Dinotasikan dengan d[vi].
Apa itu derajat simpul?
Derajat simpul adalah banyaknya ruas yang incidence [terhubung] ke simput tersebut.
Apa yang dimaksud dengan pohon merentang?
Pohon Merentang [spanning tree] Pohon merentang dari graf terhubung adalah upagraf merentang yang berupa pohon. Pohon merentang diperoleh dengan memutus sirkuit di dalam graf.
Apa itu graf pohon berakar?
Graf pohon berakar adalah graf pohon yang satu titik dari graf pohon tersebut dijadikan sebagai akar dan setiap sisi mengarah keluar dari akar tersebut. Graf sebelah kiri adalah graf pohon. Dua graf pohon disebelahnya adalah graf pohon berakar yang menjadikan titik a dan titik c sebagai akarnya.
Apa yg dimaksud dengan saraf tepi?
Sistem saraf tepi atau sistem saraf perifer adalah bagian dari sistem saraf yang di dalam sarafnya terdiri dari sel-sel yang membawa informasi ke [sel saraf sensorik] dan dari [sel saraf motorik] sistem saraf pusat [SSP], yang terletak di luar otak dan sumsum tulang belakang.
Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan hingga sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungannya antara objek-objek tersebut.
Gambar berikut merupakan contoh graph yang menyatakan peta jaringan jalan raya.
Graph
I. Sejarah Graf
Menurut catatan sejarah, masalah jembatan Konigsberg adalah masalah yang pertama kali menggunakan graf [tahun 1736]. Di kota Konigsberg [sebelah timur negara bagian Prussia, Jerman], terdapat sungai Pregal yang mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai.
Ada 7 jembatan yang menghubungkan dataran lalu dibelah oleh sungai tersebut. Masalah jembatan Konigsberg adalah : apakah mungkin melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi ke tempat semula?
Sebagian penduduk kota sepakat bahwa memang tidak mungkin melalui setiap jembatan itu hanya sekali dan kembali lagi ke tempat asal mula keberangkatan, tetapi mereka tidak dapat menjelaskan mengapa demikian jawabannya, kecuali dengan cara coba-coba.
Tahun 1736, seorang matematikawan Swiss, L. Euler, adalah orang pertama yang berhasil menemukan jawaban masalah itu dengan pembuktian sederhana.
5 April 1707 – 18 September 1783
Ia memodelkan masalah ini ke dalam graf. Daratan [titik-titik yang dihubungkan oleh jembatan] dinyatakan sebagai titik — yang disebut simpul [vertex] — dan jembatan dinyatakan sebagai garis — yang disebut sisi [edge]. Setiap titik diberi label huruf A, B, C, dan D.
Jawaban yang dikemukakan oleh Euler adalah :
Orang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya genap.
II. Defenisi Graf
Graf G didefenisikan sebagai pasangan himpunan [V, E], ditulis dengan notasi G = [V, E], yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul dan E adalah himpunan sisi yang menghubungkan sepasang simpul.
Dari defenisi di atas, menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpul harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial.
Dalam graph terdapat :
- Simpul [1, 2, 3, 4]
- Sisi [yang menghubungkan simpul] [e1, e2, e3, dst]
Kesimpulan :
- Mustahil ada sisi, tidak ada simpul;
- Mustahil ada sisi, simpulnya cuma satu;
- Sisi menghubungkan dua buah simpul;
Graph G1 adalah graph dengan :
- V [simpul] = {1, 2, 3, 4}
- E [sisi] = {[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]}
Graph G2 adalah graph dengan :
- V = { 1, 2, 3, 4 }
- E = { [1, 2], [2, 3], [1, 3], [1, 3], [2, 4], [3, 4], [3, 4] } = { e1, e2, e3, e4, e5, e6, e7}
Sisi e3 dan sisi e4 dinamakan sisi ganda, karena menghubungkan 2 buah simpul yang sama [1 dan 3].
Sisi e8 = [3, 3] dinamakan gelang/kalang atau looping karena berawal dan berakhir pada simpul yang sama.
III. Jenis-Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda, maka graph dapat digolongkan menjadi 2 jenis :
- Graph sederhana [simple graph]
- Graph tak-sederhana [unsimple-graph]
1. Graph sederhana
Graph yang tidak mengandung gelang maupun sisi-ganda dinamakan graph sederhana.
Contoh graph sederhana :
2. Graph tak-sederhana
Graph yang mengandung sisi ganda atau gelang dinamakan graph tak-sederhana [unsimple graph].
Contoh graph tak-sederhana.
Berdasarkan orientasi arah pada sisi, maka graph dapat digolongkan menjadi 2 jenis :
- Graph tak-berarah [undirected graph]
- Graph berarah [directed graph atau digraph]
1. Graph tak-berarah
Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah.
Graph G1, G2, dan G3 adalah graph tak-berarah.
2. Graph Berarah
Graph yang setiap sisinya diberikan orientasi arah disebut sebagai graph berarah.
IV. Istilah-Istilah dalam Graph
Ada beberapa istilah yang wajib Anda pahami dalam belajar graf.
1. Ketetanggaan [Adjacent]
Dua buah simpul dikatakan bertetangga apabila dihubungkan oleh sisi [keduanya terhubung langsung].
- Simpul 1 bertetangga dengan simpul 2 dan 3;
- Simpul 1 tidak bertetangga dengan simpul 4.
2. Bersisian [Incidency]
Bersisian, hubungannya simpul dengan sisi.
- Simpul 1, bersisian dengan sisi [1, 2] dan sisi [1, 3];
- Simpul 2, bersisian dengan sisi [2, 4], sisi [2, 3] dan sisi [2, 1];
- Tetapi simpul 4, tidak bersisian dengan sisi [1, 2].
3. Simpul Terpencil [Isolated Vertex]
Simpul yang tidak mempunyai sisi yang bersisian dengannya.
Simpul 5 adalah simpul terpencil.
4. Graph Kosong [Null graph atau empty graph]
Graph yang didalamnya hanya terdapat simpul, tidak ada sisi.
Graph kosong [null graph].
5. Derajat [Degree]
Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi : d[v]
- d[1] = d[4] = 2
- d[2] = d[3] = 3
- d[1] = 2; d[2] = 2; d[3] = 2; d[5]=0 dan
- d[4] = 1 simpul anting-anting [pendant vertex]
- d[1] = 3 → bersisian dengan sisi ganda
- d[3] = 4 → bersisian dengan sisi gelang [loop]
Pada graph berarah :
din [v] = derajat-masuk [in-degree] = jumlah busur yang masuk ke simpul v
dout [v] = derajat-keluar [out-degree] = jumlah busur yang keluar dari simpul v
d[v]= din [v]+ dout [v]
din [1]=2;dout [1]=1
din [2]=2 ;dout [2]=3
din [3]=2;dout [3]=1
din [4]=1;dout [4]=2
6. Lemma Jabat Tangan
Jumlah derajat semua simpul pada suatu graph adalah genap, yaitu 2 kali jumlah sisi pada graph tersebut.
Jika G = [V, E] maka :
Contoh :
d[1] + d[2] + d[3] + d[4] = 2 + 3 + 3 + 2 = 10
= 2 × jumlah sisi = 2 × 5
d[1] + d[2] + d[3] = 3 + 3 + 4 = 10
= 2 × jumlah sisi = 2 × 5
d[1] + d[2] + d[3] + d[4] + d[5]
= 2 + 2 + 3 + 1 + 0 = 8
= 2 × jumlah sisi = 2 × 4
Contoh Soal :
Diketahui graph dengan 5 buah simpul. Dapatkan kita menggambar graph tersebut jika derajat masing-masing simpul adalah :
- [i] 2, 3, 1, 1, 2
- [ii] 2, 3, 3, 4, 4
Penyelesaian :
- [i] Tidak bisa diselesaikan karena jumlah simpul ganjil, ingat lemma jabat tangan;
- [ii]
7. Lintasan [Path]
Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graph G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,…, vn-1, en, vn sedemikian sehingga e1=[v0, v1],e2=[v1, v2], … , en=[vn-1,vn] adalah sisi-sisi dari graph G.
Lintasan simpul 1 ke simpul 3 :
- Lewat simpul 1 langsung ke simpul 3;
- Lewat simpul 1, ke simpul 2, kemudian ke simpul 3;
- Melalui simpul 2, ke simpul 2, ke simpul 4, kemudian ke simpul 3.
Panjang lintasan merupakan jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada graph di atas memiliki panjang 3.
8. Siklus [Cylce] atau Sirkuit [Circuit]
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus. Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1 memiliki panjang 3.
Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1,2,3,1 pada graph di atas memiliki panjang 3.
9. Graph Terhubung [Connected]
Contoh graph terhubung :
Contoh graph tak-terhubung :
Misal kita membuat lintasan dari simpul 2 ke simpul 6. Tidak ada jalan yang bisa ditempuh, maka graph di atas termasuk graph tak-terhubung.
V. Graph Sederhana Khusus
- Graph Lengkap [Complete Graph];
- Graph Lingkaran;
- Graph Teratur [Regular Graph];
- Graph Bipartite [Bipartite Graph].
1. Graph Lengkap [Complete Graph]
Graph lengkap merupakan graph sederhana yang setiap simpulnya mempunyai sisi ke semua simpul yang lain. Graph lengkap dengan n buah simpul dilambangkan dengan Kn.
Jumlah sisi pada graph lengkap yang terdiri dari n buah simpul adalah :
2. Graph Lingkaran
Graph lingkaran adalah graph sederhana yang setiap simpulnya berderajat dua. Dilambangkan dengan Cn.
3. Graph Teratur [Regular Graph]
Graph yang setiap simpulnya mempunyai derajat yang sama disebut graph teratur. Apabila derajat setiap simpul adalah r, maka graph tersebut disebut sebagai graph teratur derajat r.
4. Graph Bipartite [Bipartite Graph]
Graph yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian sehingga setiap sisi menghubungkan simpul di V1 ke sebuah simpul di V2.
Dinyatakan sebagai G[V1,V2].
Simpul pada kelompok V1 tidak boleh saling berhubungan, begitu juga dengan kelompok pada V2.
Graph di bawah ini adalah graph bipartit karena simpul-simpulnya dapat dibagi menjadi : V1 = {a,b,d} dan V2 = {c,e,f,g}.
Contoh berikutnya :
VI. Representasi Graph
- Matriks Ketetanggaan [Adjacency Matrix]
- Matriks Bersisian [Incidency Matrix]
- Senarai Ketetanggaan [Adjacency list]
1. Matriks Ketetanggaan [Adjacency Matrix]
Untuk graph sederhana :
- Nilai 1, jika simpul bertetangga;
- Nilai 0, jika simpul tidak bertetangga.
Untuk graph tak-sederhana :
- Isi dengan nilai derajatnya.
2. Matriks Bersisian [Incidency Matrix]
3. Senarai Ketanggaan [Incidency List]
VII. Graph Isomorfik [Isomorphic Graph]
Dua buah graph yang sama tetapi secara geometri berbeda disebut graph yang saling isomorfik.
Dua buah graph, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.
Dengan kata lain, misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e’ yang berkoresponden di G2 harus bersisian dengan simpul u’ dan v’ yang di G2.
Dua buah graph yang isomorfik adalah graph yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda. Ini benar karena sebuah graph dapat digambarkan dalam banyak cara.
G1 isomorfik dengan G2, tetapi tidak isomorfik dengan G3.
Dari definisi graph isomorfik dapat dikemukakan bahwa dua buah graph isomorfik memenuhi ketiga syarat berikut:
- Mempunyai jumlah simpul yang sama;
- Mempunyai jumlah sisi yang sama;
- Mempunyai jumlah simpul yang sama berderajat tertentu.
Ketiga syarat ini ternyata belum cukup menjamin. Pemeriksaan secara visual perlu dilakukan.
VIII. Graph Planar [Planar Graph] & Graph Bidang [Plane Graph]
Graph planar adalah graph yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong, jika tidak, disebut graph tak-planar.
Contoh graph planar :
Contoh graph tak-planar :
Sisi-sisi pada graph planar membagi bidang menjadi beberapa wilayah [region] atau muka [face].
Jumlah wilayah pada graph planar dapat dihitung dengan mudah. Untuk menghitung banyaknya bidang pada sebuah graph planar :
Graph planar yang terdiri dari 6 wilayah [bagian luar dari graph — R6 –juga merupakan wilayah].
n = 7e = 11
f = 11 – 7 + 2 = 6
Contoh Soal :
Graf planar sederhana dan terhubung memiliki 10 buah simpul, masing-masing simpul berderajat 4. Representasi planar dari graf tersebut membagi bidang datar menjadi sejumlah wilayah atau muka. Berapa banyak wilayah yang terbentuk ?
Penyelesaian :
n = 10; r = 4, maka jumlah derajat seluruh simpul =10 × 4 = 40
Sehingga, jumlah sisi [e], menurut lemma jabat tangan :
e = jumlah derajat/2 = 40/2 = 20.
Jadi, jumlah wilayah [f]=e-n+2=20-10+2=12.
Gambar :
1. Ketidaksamaan Euler
Untuk mengetahui sebuah graph sederhana apakah planar atau tidak, bisa menggunakan Ketidaksamaan Euler.
Pertidaksamaan I :
Digunakan jika jumlah simpul [vertex] v ≥ 3
Pertidaksamaan II :
e = Jumlah sisi
n = Jumlah simpul
Contoh 1 :
Pada graph di atas :
n = 4; e = 6; terdapat sirkuit yang panjangnya 3, maka gunakan ketidaksamaan euler :
e ≤ 3n -66 ≤ 3.4 – 6
6 ≤ 6 → terpenuhi
Graph di atas merupakan graph planar.
Contoh 2.
n = 5; e = 10; terdapat sirkuit yang panjangnya 3, maka gunakan ketidaksamaan euler :
e ≤ 3n – 6
10 ≤ 3.5 – 6
10 ≤ 9 → tidak terpenuhi, maka graph di atas merupakan graph tak-planar.
2. Teorema Kuratoswki
Teorema ini berguna untuk menentukan dengan tegas keplanaran suatu graph.
Gbr [a] : Merupakan graph tak-planar dengan jumlah simpul paling sedikit. Tidak ada lagi yang lebih kecil dari 5 simpul untuk membentuk graph tidak planar. Jka dihilangkan 1 simpul, maka graph akan menjadi planar.
Gbr [b] : Merupakan graph tak-planar dengan jumlah sisi paling sedikit.
Contoh :
Graph di atas bukan graph planar karena mengandung upagraph [G1] yang sama dengan Graph [b] Kuratowski
G tidak planar karena mengandung upagraph [G1] yang homeomorfik dengan K5 [dengan membuang simpul-simpul yang berderajat 2 dari G1, diperoleh K5].
IX. Lintasan dan Sirkuit Euler
- Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graph tepat satu kali.
- Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali.
- Graph yang mempunyai sirkuit Euler disebut graph Euler [Eulerian graph]. Graph yang mempunyai lintasan Euler dinamakan juga graph semi-Euler [semi-Eulerian graph].
- [a] Terdapat lintasan euler : 3, 1, 2, 3, 4,1
- [b] Terdapat lintasan euler : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3, 5
- [c] Terdapat sirkuit euler : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1
- [d] Terdapat Sirkuit euler;
- [e] Tidak terdapat lintasan maupun sirkuit euler;
- [f] Terdapat lintasan euler.
- [a] Bukan euler;
- [b] Sirkuit euler;
- [c] Bukan euler;
- [d] Sirkuit euler.
Teorema Sirkuit Euler
- Graph tidak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali;
- Graph tidak berarah G adalah graph Euler [memiliki sirkuit Euler] jika dan hanya jika setiap simpul berderajat genap;
- Graph yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya;
- Graph berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama.
- G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.
- [a] Graph berarah Euler [a, g, c, b, g, e, d, f, a];
- [b] Graph berarah semi-Euler [d, a, b, d, c, b];
- [c] Graph berarah Euler.
X. Lintasan dan Sirkuit Hamilton
- Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graph tepat satu kali.
- Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graph tepat satu kali, kecuali simpul asal [sekaligus simpul akhir] yang dilalui dua kali.
- Graph yang memiliki sirkuit Hamilton dinamakan graph Hamilton, sedangkan graph yang hanya memiliki lintasan Hamilton disebut graph semi-Hamilton.
- [a] graph yang memiliki lintasan Hamilton [misal: 3, 2, 1, 4];
- [b] graph yang memiliki sirkuit Hamilton [1, 2, 3, 4, 1];
- [c] graph yang tidak memiliki lintasan maupun sirkuit Hamilton.
- [a] Lintasan Hamilton
- [b] Lintasan Hamilton
- [c] Sirkuit Hamilton
- [d] Sirkuit Hamilton
XI. Aplikasi Graph
a. Lintasan Terpendek [Shortest Path]
1. Algoritma Djikstra
Tentukan titik awal, contohnya A.Titik awal A diberikan bobot panjang lintasan L[A]=0;
Selain simpul awal, diberikan bobot : L[B]=L[C]=L[D]=L[E]=L[F] = ∞
A→B atau L[k]→L[j]
Patokan formula :L[V_j ]=min[L[V_j ],L[V_k ]+W[V_k,V_J ]]
A→bertetangga dengan B,C,E
L[A]=0
A→B=L[B]=min[L[B],L[A]+W[A,B]]=min[∞,0+7]=7A→C=L[C]=min[L[C],L[A]+W[A,C]=min[∞,0+9]=9A→E=L[E]=min[L[E],L[A]+W[A,E]=min[∞,0+14]=14
Sehingga lintasan terpendek adalah [A,B]=7, jadi lintasan dari A menuju ke B.
B→bertetangga dengan C,D.Sementara A tidak perlu dipertimbangkan lagi karena sudah masuk di himpunan [A, B].B→D=L[D]=min[L[D],L[B]+W[B,D]=min[∞,7+15]=22B→C=L[C]=min[L[C],L[B]+W[B,C]=min[9,7+10]=9
Sehingga lintasan terpendek adalah 9 menuju C. Karena 9 diperoleh dari sisi kiri, maka kita tidak pernah melintasi B, sehingga himpunannya menjadi [A,C]=9.
C→bertetangga dengan D,EC→D=L[D]=min[L[D],L[C]+W[C,D]=min[22,9+11]=20C→E=L[E]=min[L[E],L[C]+W[C,E]=min[14,9+2]=11
Lintasan terpendek adalah [A,C,E]=11
E→bertetangga dengan FE→F=L[F]=min[L[F],L[E]+W[E,F]=min[∞,11+9]=20
Lintasan terpendek adalah [A,C,E,F]=20
F→bertetangga dengan DF→D=L[D]=min[L[D],L[F]+W[F,D]=min[20,20+6]=20
Lintasan terpendek adalah [A,C,D]=20
Kesimpulan :A→B=7 [A,B]A→C=9 [A,C]A→D=20 [A,C,D]A→E=11 [A,C,E]
A→F=20 [A,C,E,F]
XII. Pewarnaan Graph
Sebuah pewarnaan dari graph G adalah sebuah pemetaan warna-warna ke simpul-simpul dari G sedemikian hingga simpul relasinya mempunyai warna warna yang berbeda.
Bilangan Kromatik
Bilangan kromatik dari G adalah jumlah warna minimum yang diperlukan untuk mewarnai graph G, dilambangkan dengan λ.
Graph H :
Contoh :
Sehingga λ[H]=3
Sehingga λ[H]=2
Permasalahan :
- Labon memelihara lima jenis ular [A, B, C, D, E] di dalam kotak kaca. Beberapa jenis ular akan menyerang beberapa jenis ular lainnya, sehingga tidak bisa disimpan pada kotak yang sama. Pada tabel di bawah ini, tanda bintang menunjukkan bahwa kedua jenis ular tidak bisa diletakkan pada kotak yang sama.
Berapakah jumlah minimum kotak kaca yang harus dimiliki Labon? Gambarkan grafnya.
Penyelesaian : Ular dianggap simpul, dan ular yang saling menyerang menjadi sisi.
- Misalkan terdapat 8 orang mahasiswa [1,2,…,8] dan 5 mata kuliah yang dapat dipilih [A, B, C, D, E]. Tabel berikut memperlihatkan matriksnya :
Lambang * pada elemen [i,j] berarti mahasiswa i memilih mata kuliah j. Tentukan jadwal ujian sedemikian rupa sehingga semua mahasiswa dapat mengikuti ujian mata kuliah yang diambilnya tanpa bertabrakan waktunya dengan mata kuliah lain yang juga diambilnya. Berapa paling sedikit hari yang dibutuhkan untuk jadwal ujian tersebut?
Penyelesaian :
- Simpul menyatakan mata kuliah;
- Sisi yang menghubungkan dua buah simpul menyatakan bahwa ada mahasiswa yang mengambil kedua mata kuliah tersebut.
Kesimpulan : λ=2
Mata ujian B, C dapat dilaksanakan bersamaan dan mata ujian A, D, E dapat dilaksanakan bersamaan namun harus berbeda waktu pelaksanaan dengan mata ujian B, C.
Pohon
I. Defenisi Pohon
Merupakan graph tak-berarah, tetapi tidak semua graph disebut sebagai pohon.
Syarat graph yang disebut sebagai pohon :
- Graf harus terhubung;
- Graf yang tidak memiliki sirkut.
II. Hutan
- Merupakan kumpulan pohon yang saling lepas; atau
- Graf tidak terhubung yang tidak mengandung sirkuit
III. Istilah-istilah pada Pohon
1. Pohon berakar [rooted tree]
Pohon yang satu buah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah sehingga menjadi graf berarah dinamakan pohon berakar [rooted tree].
2. Anak [child atau children] dan Orangtua [Parent]
- b, c, dan d adalah anak simpul a;
- a adalah orangtua dari anak-anak tersebut.
3. Lintasan [path]
- Lintasan dari a ke j adalah a, b, e, j.
- Panjang lintasan dari a ke j adalah 3.
4. Saudara kandung [sibling]
f adalah saudara kandung e, tetapi g bukan saudara kandung e, karena orangtua mereka berbeda.
5. Upapohon [subtree]
6. Derajat [degree]
Derajat sebuah simpul adalah jumlah upapohon atau jumlah anak pada simpul tersebut.
Derajat a adalah 3, derajat b adalah 2, derajat d adalah 1 dan derajat c adalah 0.
Derajat maksimum dari semua simpul merupakan derajat pohon itu sendiri. Pohon di atas berderajat 3.
7. Daun [leaf]
Simpul yang berderajat nol [atau tidak mempunyai anak] disebut daun. Simpul h, I, j, l, m adalah daun.
8. Simpul dalam [internal nodes]
Simpul yang mempunyai anak disebut simpul dalam. Simpul b, d, e, g, dan k adalah simpul dalam.
9. Aras [level] atau Tingkat
10. Tinggi [height] atau Kedalaman [depth]
Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon tersebut. Pohon di atas mempunyai tinggi 4.
Spanning Tree / Pohon Merentang
Pohon merentang merupakan upagraph merentang yang bisa dibentuk dan bersifat pohon.
Minimum Spinning Tree [MST] / Pohon Merentang Minimum
Merupakan pohon merentang dengan bobot minimum.
1. Algoritma Prim’s
- Langkah 1 : Ambil sisi graf G yang berbobot minimum, masukkan ke dalam T.
- Langkah 2 : Pilih sisi [u,v] yang mempunyai bobot minimum dan bersisian dengan simpul T, tetapi [U, v] tidak membentuk sirkuit di T. Masukkan [u, v] ke dalam T.
- Langkah 3 : Ulangi langkah 2 sebanyak n-2 kali.
Contoh :
Penyelesaian :
Bobot = 10 + 25 + 15 + 20 + 35 = 105
2. Algoritma Kruskal
- Langkah 0 : Urutkan sisi-sisi graf dari terkecil hingga terbesar;
- Langkah 1 : Buat graf kosong;
- Langkah 2 : Pilih sisi [u,v] dengan bobot minimum yang tidak membentuk sirkuit di T. Tambahkan [u,v] ke dalam T;
- Langkah 3 : Ulangi langkah 2 sebanyak n-1 kali.
Penyelesaian :
Pohon merentang minimum yang dihasilkan :
Bobot = 10 + 25 + 15 + 20 + 35 = 105
Contoh Soal :
Temukan Minimum Spinning Tree dari Pohon berikut :
Penyelesaian :
Soal Latihan :
- Mungkinkah dibuat graf-sederhana 6 simpul dengan derajat masing-masing simpul adalah:[a] 4, 4, 4, 3, 3, 2[b] 5, 2, 3, 3, 4, 3[c] 5, 4, 3, 2, 2, 3[d] 5, 3, 3, 3, 3, 3
Jika mungkin, berikan satu contohnya, jika tidak mungkin, berikan alasan singkat.
- Tentukan apakah graf berikut merupakan graf bipartite atau tidak. Jika ya, buktikan dalam bentuk gambar, jika tidak, berikan alasannya.
- gambarkan graf yang isomorfik dengan graf berikut.
- Tentukan lintasan terpendek dengan Algoritma Djikstra dari simpul A ke semua simpul yang ada pada graf berikut :
- Jurusan TI mempunyai 6 kelompok kerja yang setiap bulannya masing-masing selalu mengadakan rapat satu kali. Masing-masing anggotanya adalah : K_1={Amir,Budi,Yanti},K_2={Budi,Hasan,Tommy},K_3={Amir,Tommy,Yanti} K_4={Hasan,Tommy,Yanti},K_5={Amir,Budi},K_6={Budi,Tommy,Yanti,Hasan}. Berapa sedikitnya banyak waktu rapat berbeda yang harus direncanakan sehingga tidak ada anggota kelompok kerja yang dijadwalkan rapat pada waktu yang sama. Gambarkan graf yang merepresentasikan persoalan ini [sisi menyatakan apa, simpul menyatakan apa] lalu tentukan jumlah waktu rapat tersebut.
- Perhatikan graph berikut :
- Apakah graf planar? Jika ya, gambarkan grafnya dan tentukan jumlah Regionnya. Jika tidak, buktikan dengan ketidaksamaan Euler.
- Apakah graf tersebut memiliki sirkuit euler, lintasan euler atau tidak sama sekali ? Jika ada, tuliskan sirkuit atau lintasannya
- Gambarkan graf hamilton dari graf tersebut, setiap orang harus menggambarkan 1 graf unik [tidak boleh sama dengan graf temannya]
- Tentukan temukan MST dengan algoritma Prim atau Kruskal pada graph berikut
- temukan Pohon merentang minimum dari graf berikut :
- Dalam suatu propinsi, ada 8 kota yang akan dihubungkan dengan jaringan listrik. Biaya pemasangan jaringan listrik yang mungkin dibuat antara 2 kota adalah sebagai berikut :
Pecandu IT, pencinta seni fotografi dan penikmat kopi.. :]