Soal dan Pembahasan – Ujian Akhir Semester (UAS) Matematika Diskrit (Graf)


Berikut ini adalah 6 soal UAS Matematika Diskrit (TA 2017/2018) yang diujikan pada tanggal 8 Januari 2018 oleh Drs. Ade Mirza, M.Pd. Materi yang diujikan seluruhnya mengenai graf.

Soal Nomor 1
Jika G graf sederhana dengan |V(G)| \geq 2, buktikan bahwa G memiliki paling sedikit 2 titik berbeda dengan derajat yang sama.

Penyelesaian

Misalnya graf sederhana itu memiliki n titik, dengan n \geq 2. Karena ada n titik berbeda, maka derajat maksimum yang mungkin adalah n - 1, tetapi perhatikan bahwa ketika ada 1 buah titik yang memiliki derajat n - 1, maka tidak ada titik yang berderajat 0 dan derajat titik lainnya haruslah n - 2, n - 3, n - 4, ...., 3, 2, 1. Padahal ada n titik berbeda dalam kasus ini, sehingga pastilah setidaknya ada 1 titik yang memiliki derajat yang sama dengan titik lainnya.
Contoh: Misal ada graf sederhana dengan 4 titik. V(G) = \{a, b, c, d\}, dengan d(a) = 3. Ini berakibat tidak ada titik yang berderajat 0. Agar berbeda, ambil d(b) = 2 dan d(c) = 1. Karena d(d) \neq 0, maka derajat titik d yang mungkin adalah 1, 2, atau 3 (derajatnya sama dengan titik lain).

[collapse]

Soal Nomor 2
Buatlah 2 buah graf yang tidak isomorfik, beraturan dengan 8 titik dan 12 sisi.

Penyelesaian


Graf H dan H pada gambar di atas tidak isomorfik, beraturan (berderajat 3) dengan 8 titik dan 12 sisi.

[collapse]

Soal Nomor 3
Tunjukkan bahwa graf pohon dengan n titik memiliki tepat n - 1 sisi.

Penyelesaian

Misalkan H adalah graf pohon, dengan |V(H)| = n. Akan dibuktikan bahwa |E(H)| = n - 1.
Dengan menggunakan induksi matematika pada titik n, maka untuk n=1, maka |E(H)| = 1 - 1 = 0 merupakan pernyataan yang benar karena pohon dengan satu titik jelas tidak memiliki sisi.
Asumsikan benar bahwa untuk n = k, |E(H)| = k - 1. Akan dibuktikan benar untuk n = k + 1 sebagai berikut.
Misalkan e adalah salah satu sisi pada pohon H. Karena H tidak memuat sikel dan terhubung (definisi pohon), maka bila sisi ini dihapus, akan diperoleh graf yang terdiri dari dua komponen, masing-masing komponen memiliki k_1 dan k_2 titik, dengan k_1+k_2=n. Masing-masing komponen pada graf itu merupakan pohon. Berdasarkan asumsi, masing-masing komponen memiliki (k_1-1) dan (k_2-1) sisi. Jika sisi e dimasukkan kembali pada H, maka diperoleh total sisinya, yaitu
\begin{aligned} |E(H)| & = (k_1 - 1)+(k_2-1)+1 \\ & = (k_1 + k_2) - 1 \\ & = n - 1 \end{aligned}
Dengan demikian benar untuk semua n. Jadi, terbukti bahwa pohon dengan n titik mempunyai tepat n - 1 sisi.

[collapse]

Soal Nomor 4
Jika Q_n adalah graf kubus,
a) berapa banyak titik Q_n
b) berapa banyak sisi Q_n
Berikan argumen/alasan!

Penyelesaian

Graf kubus Q_n memiliki 2^n titik dan 2^{n-1}.n sisi.
Penjelasan:
Q_1 (graf berupa segmen garis) memiliki 2 titik dan 1 sisi.
Q_2 (graf berupa bidang persegi panjang) memiliki 4 titik dan 4 sisi.
Q_3 (graf berupa kubus yang direpresentasikan dalam bidang) memiliki 8 titik dan 12 sisi. Selanjutnya, Anda akan memperoleh bahwa graf kubus Q_n memiliki 2^n titik dan 2^{n-1} \times n sisi.

[collapse]

Soal Nomor 5
Buatlah contoh graf yang dual diri.

Penyelesaian


(Sumber: Wolfram MathWorld)

[collapse]

Soal Nomor 6
Perhatikan graf H berikut.

a) Buatlah jalan tertutup dengan panjang 7.
b) Carilah trail yang bukan sirkuit dengan panjang 6.
c) Carilah jalan tertutup yang bukan trail.

Penyelesaian

Contoh jalan tertutup dengan panjang 7 adalah (u~a~v~e~w~f~x~b~u~a~v~e~w~d~u)
Contoh trail yang bukan sirkuit dengan panjang 6 adalah (u~b~x~g~x~f~w~c~u~d~w~e~v)
Contoh jalan tertutup yang bukan trail adalah (u~b~x~b~u)

[collapse]

Ayo Beri Rating Postingan Ini

Soal dan Pembahasan – Keterhubungan Graf

 
             Setelah kita mempelajari mengenai soal dan pembahasan Teori Dasar Graf dan Graf Isomorfik dan Subgraf, sekarang kita siap untuk mempelajari soal-soal berikut mengenai graf.
            Berikut ini merupakan contoh soal beserta penyelesaiannya mengenai definisi dan terminologi graf lanjutan, yang meliputi jalan (walk), lintasan (path), sikel (cycle). sirkuit (circuit), jalur (trail), jembatan (bridge/cut set), termasuk juga mengenai graf Euler, graf Hamilton, konektivitas graf, matriks keterhubungan langsung (adjacency matrix), matriks keterkaitan (incidency matrix), Algoritma Fleury, beserta teorema-teorema yang terkait dengannya.  Jangan lupa juga untuk belajar istilah/kosa kata mengenai graf di sini.

Soal Nomor 1
Perhatikan graf G berikut.

Carilah:
a) Sebuah jalan tertutup dengan panjang 9
b) Sebuah trail terbuka dengan panjang 9
c) Sebuah trail tertutup dengan panjang 7
d) Sebuah lintasan (path) dari simpul a ke n
e) Panjang sikel terpanjang dalam G
f) Panjang lintasan (path) terpanjang dalam G
g) Lilitan (girth) dalam G
h) Sebuah graf bagian bukan rentang

Penyelesaian

(Jawaban a) Contoh jalan tertutup dengan panjang 9 adalah jalan dengan barisan titik i~c~d~e~m~l~d~k~c~i
(Jawaban b) Contoh trail terbuka dengan panjang 9 adalah jalan dengan barisan titik a~g~b~h~j~i~c~k~d~e
(Jawaban c) Contoh trail tertutup dengan panjang 7 adalah jalan dengan barisan titik c~d~e~m~l~d~k~c
(Jawaban d) Contoh lintasan (path) dari a ke n adalah jalan dengan barisan titik a~g~b~i~c~d~e~n
(Jawaban e) Panjang sikel terpanjang dalam G adalah 4. Salah satu sikel yang panjangnya demikian adalah jalan dengan barisan titik g~b~i~j~g.
(Jawaban f) Panjang lintasan (path) terpanjang dalam G adalah 12.Salah satu lintasan yang panjangnya demikian adalah jalan dengan barisan titik a~g~b~h~j~i~c~k~d~l~m~e~n
(Jawaban g) Lilitan (girth) adalah panjang sikel terpendek dalam suatu graf. Lilitan pada graf G di atas adalah 3 (contoh: jalan i~c~k)
(Jawaban h) Graf bagian bukan rentang adalah graf bagian yang tidak memuat seluruh titik pada graf induknya. Contohnya sebagai berikut di mana titik selain e, f, m, n dihapus.


[collapse]

Soal Nomor 2
Gambarkan sebuah graf yang terdiri dari
a) 5 titik, tanpa sikel, dan terhubung
b) 6 titik, reguler-2, dan terdiri dari 2 komponen

Penyelesaian

(Jawaban a) Lihat video berikut.

(Jawaban b) Graf berikut memuat 6 titik (s, t, u, x, y, z), reguler-2 (setiap titik berderajat 2), dan terdiri dari 2 komponen.

[collapse]

Soal Nomor 3
Buktikan teorema berikut.
“Setiap jalan (u, v) dalam suatu graf memuat sebuah path (u, v)

Penyelesaian

Misalkan W sebuah jalan dalam graf G, dengan W = (u, v). Jika W tertutup, maka jelas W memuat path (trivial = hanya terdiri dari satu titik), karena u = v, sehingga path (P) = u. Jika u \neq v, maka kita misalkan jalan W di G adalah sebagai berikut.
u = v_0, v_1, v_2, v_3, \cdots, v_{n-1}, v_n = v
Apabila tidak ada titik di G pada jalan W yang dilalui lebih dari satu kali (tidak ada titik yang sama pada jalan itu), maka W sendiri adalah path (u, v).
Sebaliknya, bila tidak demikian, dengan kata lain terdapat titik di G pada jalan W yang dilalui lebih dari satu kali, maka ada i, j anggota bilangan bulat positif berbeda dengan i < j sedemikian sehingga berlaku u_i = u_j.
Jika jalan u_i, u_{i+1}, \cdots, u_{j-1} dihapus dari W, maka diperoleh suatu jalan baru, sebut saja W_1 dari titik u ke v (ini hanya pemisalan) yang mempunyai beberapa titik (minimal 1) pada W. Jika tidak ada pengulangan titik pada jalan W_1, maka W_1 adalah path (u, v).
Jika tidak demikian, ulangi prosedur penghapusan seperti di atas sampai diperoleh hasil akhir berupa jalan (u, v) yang juga adalah path (u, v) (terbukti)

[collapse]

Soal Nomor 4
Dengan menggunakan teorema pada soal nomor 3 di atas, tentukan sebuah path dari v_1 ke v_5 jika jalan W dari graf G berikut.
v_1, e_1, v_2, e_5, v_3, e_{10}, v_3, e_5, v_2, e_3, v_5

Penyelesaian Belum Tersedia
[collapse]

Soal Nomor 5
Misalkan G suatu graf yang dipresentasikan seperti gambar berikut.

Nyatakanlah matriks keterhubungan langsung dan matriks keterkaitan dari graf di atas.

Penyelesaian

Misalkan A(G) menyatakan matriks keterhubungan langsung (adjacency matrix) dari graf G, maka A(G) dapat dinyatakan sebagai berikut.
A(G) = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 2 \\ 0 & 1 & 0 & 1 \\ 1 & 2 & 1 & 0 \end{bmatrix}
(a_{ij} menyatakan banyaknya sisi yang menghubungkan titik i dan titik j, misalnya a_{24} berarti banyak sisi yang menghubungkan titik 2 dan 4, yaitu ada 2 sisi)
Selanjutnya, misalkan I(G) menyatakan matriks keterkaitan (incidency matrix) dari graf G, maka I(G) dapat dinyatakan sebagai berikut.
A(G) dapat dinyatakan sebagai berikut.
I(G) = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} & a_{15} & a_{16} \\ a_{21} & a_{22} & a_{23} & a_{24} & a_{25} & a_{26} \\ a_{31} & a_{32} & a_{33} & a_{34} & a_{35} & a_{36} \\ a_{41} & a_{42} & a_{43} & a_{44} & a_{45} & a_{46} \end{bmatrix}
I(G) = \begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}

(a_{ij} menyatakan keterkaitan titik i pada sisi j. Misalkan a_{43} bernilai 1 menyatakan karena sisi 3 terkait dengan titik 4).

[collapse]

Soal Nomor 6
Gambarkan graf dengan matriks keterhubungan langsung sebagai berikut.
a. \begin{bmatrix} 0 & 1 & 0 & 2 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 0 &0&0&0&2\\2&1&0&0&1\\1&1&2&1&0 \end{bmatrix}

b. \begin{bmatrix} 0 & 1 & 0 & 1 &1 \\ 1 & 0 &0&1&1 \\ 0 &0&0&0&0\\ 1&1&0&0&1\\ 1&1&0&1&0 \end{bmatrix}

Penyelesaian

(Jawaban a) Bentuk graf yang sesuai dengan matriks keterhubungan langsung itu adalah sebagai berikut.

Penjelasan:
Entri baris 1 kolom 1 = 0, berarti tidak ada sisi loop pada titik 1.
Entri baris 1 kolom 2 = 1, artinya ada 1 sisi yang menghubungkan titik 1 dan 2. 
Entri baris 1 kolom 3 = 0, artinya tidak ada sisi yang menghubungkan titik 1 dan 3.
Entri baris 1 kolom 4 = 2, artinya ada 2 sisi yang menghubungkan titik 1 dan 4, dan seterusnya.
(Jawaban b) Bentuk graf yang sesuai dengan matriks keterhubungan langsung itu adalah sebagai berikut.


Tips! Entri pada baris pertama menyatakan keterhubungan titik 1 pada titik lain sesuai dengan kolom matriksnya. Begitu juga entri pada baris kedua, yang menyatakan keterhubungan titik 2 pada titik lain sesuai dengan kolom matriksnya, dan seterusnya. Karena matriksnya simetris (transposnya sama), maka jika Anda tinjau dari entri kolomnya juga bisa menggunakan prinsip yang sama.

[collapse]

Soal Nomor 7
Gambarkan graf dengan matriks keterkaitan berikut.
\begin{bmatrix} 1&1&1&1&0&0&0&0 \\ 1&1&0&0&1&1&0&0 \\ 0&0&0&0&0&0&0&0\\ 0&0&0&1&0&1&1&1\\ 0&0&1&0&1&0&1&1 \end{bmatrix}

Penyelesaian

Pada matriks keterkaitan, banyak kolom menyatakan banyaknya sisi pada graf (ada 8 kolom berarti ada 8 sisi), sedangkan banyak baris menyatakan banyak titiknya (ada 5 baris berarti ada 5 titik). Untuk menggambar graf yang dimaksud, tinjau kolom per kolom.
Misalnya pada kolom pertama, baris 1 dan baris 2 bernilai 1, artinya titik 1 dan titik 2 terhubung oleh satu sisi. Pada kolom kedua, baris 1 dan 2 juga bernilai 1, artinya titik 1 dan titik 2 terhubung oleh satu sisi lagi (berarti sisi rangkap), dan seterusnya. Perhatikan bahwa pada entri pada baris ke-3 semuanya bernilai 0, yang berarti tidak ada sisi yang terkait dengan titik 3 (titik 3 di sini disebut sebagai titik terpencil (isolated vertex))

[collapse]

Soal Nomor 8
Berilah contoh setiap graf berikut dengan paling banyak 6 titik.
a) Graf Hamilton yang bukan Euler.
b) Graf Euler yang bukan Hamilton.

Penyelesaian

Graf Hamilton adalah graf yang memuat sikel Hamilton. Sikel Hamilton sendiri adalah jalan tertutup yang semua sisi dan titik internalnya berbeda serta melalui seluruh titik pada graf tersebut. Sedangkan graf Euler adalah graf yang memuat sirkuit Euler, yaitu jalan tertutup yang semua sisinya berbeda dan setiap sisi dilalui tepat 1 kali. Contoh yang diberikan berikut merupakan salah satunya. Silakan Anda coba buat graf yang lain.

Graf G_1 di atas mengandung sikel Hamilton dengan barisan titik
a~b~c~d~e~f~h~g~a
Jelas bahwa jalan tersebut tertutup (kembali pada titik semula), melalui semua titik pada graf, dan titik internalnya berbeda (hanya dilalui 1 kali). Oleh karena itu, graf G_1 disebut graf Hamilton. Tetapi, bukan graf Euler karena ada sisi yang tidak dilaluinya, yaitu sisi be, cf, dan fg.

(Jawaban b) Graf di atas tergolong graf Euler (karena mengandung sirkuit Euler a~b~c~d~e, tetapi bukan graf Hamilton sebab titik f tidak dilaluinya (tidak mengandung sikel Hamilton).

[collapse]

Soal Nomor 9
Tunjukkan bahwa setiap sikel pada graf bipartisi mempunyai panjang genap.

Penyelesaian

Perhatian! Sikel adalah jalan tertutup yang memuat sisi yang berbeda.
Misalkan diberikan graf bipartisi G. Andaikan graf ini memiliki setidaknya 1 sikel ganjil sehingga partisi himpunan titiknya dapat ditulis sebagai V_1 = \{v_1, v_3, v_5, \cdots\} dan V_2 = \{v_2, v_4, v_6, \cdots\}. Karena sikelnya memiliki panjang ganjil, maka jalan yang dapat terjadi adalah v_1~v_2~v_3~\cdots~v_{2n+1} untuk suatu n bilangan bulat positif. Jelas bahwa v_1 dan v_{2n+1} (ganjil) berada dalam himpunan partisi yang sama, yaitu V_1. Akibatnya graf tersebut bukan graf bipartisi (karena “terpaksa” harus dibuat sisi yang menghubungkan kedua titik itu agar menjadi jalan yang tertutup). Jadi, pengandaian diingkari. Terbukti bahwa graf bipartisi memiliki sikel dengan panjang genap.

[collapse]

Soal Nomor 10
Berapa banyak path (s, x) pada graf berikut?

Penyelesaian

Lintasan (path) adalah jalan yang memuat titik yang berbeda. Hanya ada 4 path yang dapat ditemukan dalam jalan (s, x), yaitu
s~v~w~x
s~t~u~v~w~x
s~v~w~z~y~x
s~t~u~v~w~z~y~x

[collapse]

Soal Nomor 11
Berilah 3 contoh graf yang komplemen diri (self complementary).

Penyelesaian


Graf yang komplemen diri adalah graf yang komplemennya sama dengan isomorfiknya. G^c sendiri merupakan notasi untuk menyatakan komplemen dari graf G. Berikut ini adalah 3 contoh graf yang komplemen diri. Contoh terakhir diambil dari Math Stack Exchange.




[collapse]

Soal Nomor 12
Buktikan bahwa graf yang komplemen diri mempunyai banyak titik sama dengan 4k atau 4k + 1 untuk suatu bilangan bulat positif k

Penyelesaian

Ingat bahwa graf lengkap/komplit dengan n titik memiliki \dfrac{1}{2}n(n-1) sisi. Untuk graf yang komplemen diri, banyak sisinya adalah setengah dari banyaknya sisi pada graf lengkap, yaitu \dfrac{1}{4}n(n-1). Agar diperoleh n bulat, maka dapat dituliskan 4|n(n-1), yang mengimplikasikan bahwa n = 4k atau n = 4k + 1 untuk suatu bilangan bulat positif k.

[collapse]

Soal Nomor 13
Tuliskan matriks keterhubungan langsung dan matriks keterkaitan dari graf berikut.

Penyelesaian

Matriks keterhubungan dari graf G di atas adalah sebagai berikut.
\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\  0 & 0 & 1 & 0 & 0& 1 & 0 & 0 \\  0 & 0 & 0 & 1 & 1 & 0 &0 & 0 \\  1 & 0 & 0 & 0 &0 & 0&0&1 \\\ 0 & 1 &0&0&0&0&1&0 \end{pmatrix}
Matriks keterkaitan dari graf G di atas adalah

Ordo matriks di atas adalah 8 \times 12 yang menunjukkan bahwa graf itu memuat 8 titik dan 12 sisi.
Matriks keterhubungan langsung dari graf H di atas adalah sebagai berikut.
\begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 2 \\ 1 & 1 & 2 & 0 \end{pmatrix}
Sedangkan matriks keterkaitannya adalah sebagai berikut.
\begin{pmatrix} 1 & 1 & 1 & 2 & 2 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}
Ordo matriks di atas adalah 4 \times 9. Banyak barisnya 4 menunjukkan bahwa jumlah titik di graf itu adalah 4, sedangkan 9 kolomnya menyatakan bahwa graf itu memuat 9 sisi. Perhatikan bahwa angka 2 pada entri di baris pertama (titik 1) matriks itu menunjukkan bahwa sisi loop mengait pada titik 1.

[collapse]

Soal Nomor 14
Tunjukkan bahwa salah satu di antara graf atau komplemennya pasti terhubung.

Penyelesaian

Misalkan G graf tak terhubung. Akan ditunjukkan G^c terhubung. Misalkan v dan w titik pada graf G. Jika vw bukan sisi di G, maka vw pasti sisi di G^c, dan berarti kita punya lintasan dari v ke w di G^c. Di lain sisi, bila vw adalah sisi di G, maka ini berarti titik v dan w berada dalam satu komponen di G. Karena G tak terhubung, maka kita bisa menemukan titik lain, sebut saja u, yang terletak di komponen lainnya sedemikian sehingga uv maupun uw bukan sisi di G. Dengan kata lain, uv dan uw adalah sisi di G^c dan vuw membentuk lintasan (path). Ini menunjukkan bahwa sembarang dua titik di G^c memiliki lintasan yang menghubungkan mereka. Dapat disimpulkan bahwa G^c pasti terhubung.

[collapse]

Soal Nomor 15
Misallan G graf bipartisi. Tunjukkan bahwa matriks keterhubungan langsung dari G dapat ditulis dalam bentuk

di mana O, P, dan Q adalah submatriks; O submatriks yang setiap unsurnya 0 (nol), sedangkan P adalah transpose dari Q.

Penyelesaian Belum Tersedia

[collapse]

Soal Nomor 16
Misalkan G graf sederhana dengan n titik dan untuk setiap titik v di G, berlaku
d(v) \ge \dfrac{1}{2}(n-1)
Buktikan bahwa G terhubung.

Penyelesaian

Misalkan G adalah graf sederhana dengan n titik. Andaikan bahwa G tak terhubung, misalnya terdiri dari setidaknya 2 komponen. Masing-masing komponen graf setidaknya memiliki 1 titik dan berdasarkan hipotesis (minimal\dfrac{1}{2}(n-1) titik), banyak titik pada masing-masing komponen adalah
1 + \dfrac{1}{2}(n-1) = \dfrac{1}{2}(n+1)
Jadi, jumlah titik pada graf G adalah
\dfrac{1}{2}(n+1) +  \dfrac{1}{2}(n+1) = n + 1
Ini kontradiksi dengan asumsi awal bahwa graf G memiliki n titik. Jadi, pengandaian diingkari. Terbukti bahwa graf G haruslah terhubung.

[collapse]

Soal Nomor 17
Tentukan \chi(G_1) (baca: chi G_1) dan \lambda(G_1) (baca: lambda G_1) dari graf G_1.

Penyelesaian

\chi(G_1) menyatakan banyak minimum titik-titik di G_1 yang jika dihilangkan akan menghasilkan graf tak terhubung atau graf trivial. Hilangkan satu titik, misalnya titik a, sehingga grafnya hanya memuat titik b dan c serta sisi bc (masih graf terhubung). Hilangkan satu titik lagi, misalnya titik b, sehingga hanya tersisa titik c. Graf tersebut menjadi graf trivial. Sesuai definisi, maka \chi(G_1) = 2 (karena titik yang dihilangkan sebanyak 2).
\lambda(G_1) menyatakan banyak minimum sisi-sisi di G_1 yang jika dihilangkan akan menghasilkan graf tak terhubung atau graf trivial. Hilangkan salah satu sisi, misalnya sisi ab, berarti G_1 masih memuat titik a, b, dan c serta sisi ac dan bc (graf terhubung). Hilangkan salah satu sisi lagi, misalnya sisi ac, sehingga graf tersebut hanya memuat titik a, b, dan c serta sisi bc. Jelas bahwa graf menjadi tak terhubung lagi. Berarti, penghilangan sisinya paling sedikit adalah 2 atau ditulis \lambda(G_1) = 2.

[collapse]

Soal Nomor 18
Tentukan \chi(G_1) (baca: chi G_1) dan \lambda(G_1) (baca: lambda G_1) dari graf-graf berikut.
 

Penyelesaian

Sebut graf pada bagian atas dan bawah berturut-turut adalah G_1 dan G_2. Sama seperti soal sebelumnya,
\lambda(G_1) = 1
\lambda(G_2) = 2 (hilangkan 2 sisi yang mengait titik di bagian ujung)
\chi(G_1) = 1
\chi(G_2) = 2 (hilangkan 2 titik dengan sisi yang mengait titik ujung)

[collapse]

Soal Nomor 19 (Soal ON-MIPA PT Seleksi Wilayah)
Suatu sisi e di graf G dikatakan suatu cut edge jika jumlah komponen dari G\e lebih dari jumlah komponen dari G. Buktikan bahwa, suatu sisi e adalah cut edge di G jika dan hanya jika e tidak termuat di setiap lingkaran di G.

Penyelesaian Belum Tersedia
[collapse]
Ayo Beri Rating Postingan Ini

Soal Latihan dan Penyelesaian – Teori Dasar Graf (Graph Basic Theory)


          Berikut ini adalah beberapa soal mengenai teori dasar graf, yang sangat cocok bagi Anda yang baru saja mengenal materi graf. Beberapa soal diambil dari bahan ajar dosen dan sisanya diambil dari referensi lain terkait. Soal juga disertai penyelesaian, tetapi ada beberapa yang belum disertai (mungkin Anda bisa menyelesaikannya di kolom komentar). Bagi Anda yang ingin mempelajari kosa kata atau istilah graf, silakan klik sini

Soal Nomor 1
Gambarkan graf dengan 5 titik dan 8 sisi serta
a) sederhana
b) memuat loop dan sisi rangkap
c) tidak sederhana dan memuat sisi rangkap

Penyelesaian
[collapse]

a) Contoh graf sesuai dengan syarat yang diberikan bisa dilihat di gambar berikut. Lanjutkan membaca “Soal Latihan dan Penyelesaian – Teori Dasar Graf (Graph Basic Theory)”

Ayo Beri Rating Postingan Ini