Soal Matematika Informatif (Graf)

1.  Apakah graf pada gambar di bawah mempunyai sirkuit Euler? Jelaskan!

A

B

Jawab:

Untuk mengetahui apakah graf A di atas memiliki sirkuit Euler, kita dapat menggunakan suatu teorema yang menyatakan “Jika pseudograf G terhubung dan derajat setiap titiknya mempunyai derajat genap, maka G mempunyai sebuah sirkuit Euler” Untuk itu kita periksa bahwa A terhubung dan derajat setiap titiknya genap. Pertama kita beri label setiap titik dan sisi pada graf A sebagai berikut:

A

Graf A terhubung karena terdapat sebuah lintasan dari titik x dan y jika diketahui sembarang titik x dan y. Dan jika kita periksa sebagai berikut:

a ke b lintasannya (a, e1, b) ; a ke c lintasannya (a, e1, b, e2, c) ;  a ke d lintasannya (a, e12,d) ; a ke e lintasannya (a, e11, e) ; a ke f  lintasannya (a, e11, e, e10, f) ; b ke c lintasannya (b, e2, c) ; b ke d lintasannya (b, e4, d) ; b ke e lintasannya (b, e4, d, e8,e) ; b ke f lintasannya (b, e6, f) ; c ke lintasannya (c, e7, f, e9, d) ; c ke e lintasannya (c, e5, e) ; c ke f  lintasannya (c, e7, f) ; d ke e lintasannya (d, e8, e) ; d ke f lintasannya (d, e9, f) ; e ke f lintasannya (e, e10, f) ; sehingga dengan demikian  A terhubung.

d(a) = d(b) = d(c) = d(d) = d(e) = d(f) = 4 ini artinya setiap setiap titik pada graf A berderajat genap.

Karena derajat setiap titik adalah genap, menurut teorema tersebut di atas maka A mempunyai sebuah sirkuit Euler. 

Jadi graf A di atas mempunyai  Sirkuit Euler-nya, dan sirkuit Euler-nya yaitu:

                        (c, a, b, f, c, e, a, d, e, f, d, b, c)

2.  Dept. IF mempunyai 6 kelompok kerja yang setiap bulannya masing-masing selalu mengadakan rapat satu kali. Keenam kelompok kerja dengan masing-masing anggotanya adalah: K₁ = {Amir, Budi, Yanti}, K₂ = {Budi, Hasan, Tommy}, K3 = {Amir, Tommy, Yanti}, K₄ = {Hasan, Tommy, Yanti}, K₅ = {Amir, Budi}, K₆ = {Budi, Tommy,Yanti}.

Berapa 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 lalu (sisi menyatakan apa, simpul menyatakan apa) tentukan jumlah waktu rapat ini.  

Jawab :

Simpul          : menyatakan kelompok

Sisi                : menyatakan adanya anggota kelompok yang sama

Jika ada sisi yang menghubungkan 2 kelompok berarti kelompok tersebut tidak boleh rapat pada waktu yang sama.

Dapat dilihat gambar graf yang terbentuk. Untuk mencari jumlah minimum waktu rapat yang harus disediakan kita dapat menggunakan cara yang sama seperti mencari bilangan kromatis dari graf tersebut. Setiap warna yang berbeda mewakili satu waktu rapat yang dibutuhkan.

Bilangan kromatis graf tersebut adalah 5. maka waktu rapat yang harus disediakan adalah 5.

 

1 waktu untuk K1

1 waktu untuk K2

1 waktu untuk K3

1 waktu untuk K4 dan K5

1 waktu untuk K6

3.  Himpunan garis yang menghubungkan tiap node / vertex disebut ...

Jawaban :

Edge

 4.  

 Total bobot dari spanning tree tersebut adalah … (gambar 3)

Penjelasan :

Terlihat bahwa spanning tree tersebut mempunyai total bobot 2 + 3 + 4 + 4 + 4 + 4 + 3 = 24

 5.  Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 16 buah sisi dan tiap simpul berderajat sama dan tiap simpul berderajat ≥ 4 ?
Jawaban: Tiap simpul berderajat sama -> graf teratur.

*    * Jumlah sisi pada graf teratur berderajat r adalah e = nr/2. Jadi, n = 2e/r = (2)(16)/r = 32/r.
* Untuk r = 4, jumlah simpul yang dapat dibuat adalah maksimum, yaitu n = 32/4 = 8.
* Untuk r yang lain (r > 4 dan r merupakan pembagi bilangan bulat dari 32):
r = 8 -> n = 32/8 = 4 -> tidak mungkin membuat graf sederhana.
r = 16 -> n = 32/16 = 2 -> tidak mungkin membuat graf sederhana.
* Jadi, jumlah simpul yang dapat dibuat adalah 8 buah (maksimum dan minimum).

      

     6.  Pada gambar dibawah, tentukan Derajat dari graf G, Jika order dari G = n, size dari G = e, dan banyak komponen = k, berapa Rank dari graf G? Berapa jarak maksimum atau diameter dalam graf G?

       a. Derajat dari Graf G :

Dik: Banyak ruas = 10

Derajat Graf(G) = 2 * banyak ruas

= 2 * 10

= 20

2. Cara mencari Rank dari graf tersebut adalah:

Dik : n = 7

k = 1

Rank (G) = n – k

= 7 – 1

= 6

3.  Jarak maksimum pada graf tersebut adalah 3 yaitu dari A ke G, B ke G, C ke G ataupun sebaliknya

 7.  Jika diberikan sembarang simple graf, sebagai berikut:G = (V, E); V = {1, 2, 3, 4, 5, 6}; E = {13, 14, 15, 16, 23, 24, 26, 35, 36, 46, 56} Apakah graf G tersebut merupakan graf planar? 

Jawab :

 

G = z(V, E); V = {1, 2, 3, 4, 5, 6}; E = {13, 14, 15, 16, 23, 24, 26, 35, 36, 46, 56}Dari himpunan graf dan ga mbar d iperoleh:V = 6; E = 11; dan F = 7 sehingga V – E + F = 2 (terbukti)

8.  ( Lanjutan dari soal no 7 )Sebutkan 3 bentuk graf yang bukan merupakan graf planar (setiap graf hanya bolehdisebutkan dengan istilah yang Anda kenal, bukan dalam bentuk representasi graf: himpunangraf, matriks adjacent, ilustrasi graf).

Jawab :

K5,K3,3, dan graf tidak terkoneksi.

 9. Gambarlah sebuah graf sederhana yang dapat di bentuk dari 4 titik {a,b,c,d} dan 2 garis.

Jawab :

 Sebuah garis dalam graf sederhana selalu berhubungan dengan 2 titik.Oleh karena ada 4 titik,maka ada C(4,2) = 6 garis yang mungkin di buat. Yaitu garis – garis dengan titik ujung {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}.

Dari keenam garis yang mungkin tersebut,selanjutnya dipilih 2 garis diantaranya.jadi ada C(6.2) = 15 buah graf yang mungkin di bentuk dari 4 buah titik dan 2 buah garis.

10. Carilah Pohon rentang dari setiap graf –graf pada gambar di bawah inidengan menghapus jalur – jalur dalam sikel

Jawab :

a. 

Kita hapus jalur ab untuk merusak sikel a,b,d,a dan jalur bc untuk merusak sikel b,c,e,b

b. 

Kita hapus jalur db untuk merusak sikel a,b,d,a dan jalur be untuk merusak sikel b,c,e,b

c. 

Kita hapus jalur ad untuk merusak sikel a, b, d, a dan jalur ce untuk merusak sikel b, c, e, b

d. 

Kita hapus jalur ab untuk merusak sikel a,b,d,a dan jalur ec untuk merusak sikel b,c,e,b

e. 

Kita hapus jalur ab untuk merusak sikel a,b,d,a dan jalur be untuk merusak sikel b,c,e,b

f. 

Kita hapus jalur bd untuk merusak sikel a,b,d,a dan jalur ec untuk merusak sikel b,c,e,b

 g.  

Kita hapus jalur ad untuk merusak sikel a,b,d,a dan jalur bc untuk merusak sikel b,c,e,b

 h. 

Kita hapus jalur bd untuk merusak sikel a,b,d,a dan jalur bc untuk merusak sikel b,c,e,b

 i. 

Kita hapus jalur bd untuk merusak sikel a,b,d,a dan jalur bc untuk merusak sikel b,c,e,b