Teori Graph dan Pohon [Matematika Diskrit]

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.

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;

III. Jenis-Jenis Graf

Berdasarkan ada tidaknya gelang atau sisi ganda, maka graph dapat digolongkan menjadi 2 jenis :

1. Graph sederhana (simple graph)
2. 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 :

1. Graph tak-berarah (undirected graph)
2. Graph berarah (directed graph atau digraph)

1. Graph tak-berarah

Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah.

Graph G₁, G₂, dan G₃ 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).

2. Bersisian (Incidency)

3. Simpul Terpencil (Isolated Vertex)

Simpul yang tidak mempunyai sisi yang bersisian dengannya.

4. Graph Kosong (Null graph atau empty graph)

Graph yang didalamnya hanya terdapat simpul, tidak ada sisi.

5. Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.

Notasi : d(v)

Pada graph berarah :

d_in (v) = derajat-masuk (in-degree) = jumlah busur yang masuk ke simpul v
d_out (v) = derajat-keluar (out-degree) = jumlah busur yang keluar dari simpul v
d(v)= d_in (v)+ d_out (v)

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 :

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 v₀ ke simpul tujuan v_n di dalam graph G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v₀, e₁, v₁, e₂, v₂,…, v_n-1, e_n, v_n sedemikian sehingga e₁=(v₀, v₁),e₂=(v₁, v₂), … , e_n=(v_n-1,v_n) 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 :

V. Graph Sederhana Khusus

1. Graph Lengkap (Complete Graph);
2. Graph Lingkaran;
3. Graph Teratur (Regular Graph);
4. 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 V₁ ke sebuah simpul di V₂.

Dinyatakan sebagai G(V₁,V₂).

Graph di bawah ini adalah graph bipartit karena simpul-simpulnya dapat dibagi menjadi : V₁ = {a,b,d} dan V₂ = {c,e,f,g}.

Contoh berikutnya :

VI. Representasi Graph

1. Matriks Ketetanggaan (Adjacency Matrix)
2. Matriks Bersisian (Incidency Matrix)
3. 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:

1. Mempunyai jumlah simpul yang sama;
2. Mempunyai jumlah sisi yang sama;
3. 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).

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 -6
6 ≤ 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]=7
A→C=L(C)=min⁡[L(C),L(A)+W(A,C)=min⁡[∞,0+9)=9
A→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]=22
B→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,E
C→D=L(D)=min⁡[L(D),L(C)+W(C,D)=min⁡[22,9+11]=20
C→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 F
E→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 D
F→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 :

1. 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.

2. 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 :

1. Graf harus terhubung;
2. 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 :

1. 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.
2. Tentukan apakah graf berikut merupakan graf bipartite atau tidak. Jika ya, buktikan dalam bentuk gambar, jika tidak, berikan alasannya.
3. gambarkan graf yang isomorfik dengan graf berikut.
4. Tentukan lintasan terpendek dengan Algoritma Djikstra dari simpul A ke semua simpul yang ada pada graf berikut :
5. 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.
6. 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)
7. Tentukan temukan MST dengan algoritma Prim atau Kruskal pada graph berikut
8. temukan Pohon merentang minimum dari  graf berikut :
9. 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 :