TEORI GRAF DAN TEORI BAHASA AUTOMATA

Soal Teori Graf dan Teori Bahasa Automata

1. Berapa  jumlah rusuk yang dimiliki  oleh masing-masing graf ini  :

a.       Graf  null = N₉

b.      Graf Lengkap = K₆

c.       Graf Bipartit Lengkap = K_4,8

d.      Graf Gabungan (Union) = K_1,3 dan W₄

2. Suatu rumah dihuni oleh  9 orang mahasiswa masing-masing bernama Aras, Dendi, Pian, Irfan, Herlan, Luthfi, Syahril, Rifki dan Asep. Diketahui Aras, Dendi dan Pian saling bersepupu dan juga adalah sepupu dari Asep dari Pihak Bapa, sedangkan asep sepupuan dengan luthfi dan syahril. Irfan, Herlan  juga merupakan sepupu Asep dari pihak ibu.  Ketika ditelusuri, ternyata Aras dan Herlan juga sepupuan. Coba gambarkan graf kekeluargaan dari ke 9 orang tersebut.
3. Misalkan V(G) = (1, 2, 3, 4, 5) dan E(G) = (12, 13, 15, 23) Gambar graf G
4. Buatlah pemetaan satu-satu dari himpunan titik graf siklus dengan 4 titik (C₄) ke himpunan graf bipartite lengkap K₂₂. Selanjutnya tentukan apakah graf C₄ dan K₂₂ isomorf ?
5. Buktikan bahwa sebuah graf akan terhubung 2 sisi jika dan hanya jika setiap simpulnya yang berbeda dihubungkan oleh sedikitnya dua lintasan yang tidak memiliki rusuk Bersama.

**===Jawaban===**

     1.  a. Graf null N₉ tidak memiliki rusuk dikarenakan graf null himpunan dari rusuknya kosong /             null

  b. Graf lengkap K₆  memiliki jumlah rusuk sebanyak 15, dikarenakan hasil dari rumus n (n–1)/2       dimana n adalah nilai dari simpul

  c. Graf bipartit lengkap K_4,8 Memiliki jumlah ruduk sebanyak 11

  d. Graf gabungan (union) dari K_1,3 dan W₄ meliki jumlah rusuk sebanyak 10

    2. Hubungan kekeluargaan dari 9 orang mahasiswa dapat dimodelkan ke dalam graf dengan cara:    nyatakan orang sebagai titik dan dua titik bertetangga jika dua orang yang dinyatakan sebagai   dua titik tersebut adalah bersepupu. Maka V(G) = (Aras, Dendi, Pian, Lutfi, Syahril, Asep,   Herlan, Irfan, Rifki) dan E(G) = (Aras Dendi, Dendi Pian, Pian Aras, Asep Lutfi, Lutfi Syahril,   Syahril Asep, Irfan Herlan, Aras Herlan, Asep Aras, Asep Dendi, Asep Pian, Asep Herlan,     Asep Irfan)

 Gambar grafnya sebagai berikut :

   3. Berikut gambar dari graf tersebut :

  4. Tidak isomorph, berikut gambar graf tersebut :

 

  5. Berikut gambar pembuktiannya :