Jurnal Graf [PDF]

Citation preview

SUBGRAF DAN GRAF KHUSUS Dian Pratama1, Marina Afriyanty2, Ratna Dewi Sari2, Stevanus Trionanda4 1,2,3,4



Jurusan Pendidikan Matematika, FKIP UMRAH



jejak (trail). Jejak yang semua simpul



1. Walk (Jalan) Walk adalah urutan tak nol W =



awal dan simpul akhirnya berlainan



v0e1v1e2, … e1vi … ekvk, sedemikian



disebut jejak tertutup. Trail u – v



sehingga 1 ≤ I ≤ k, ujung dari e1 adalah



adalah jalan u – v yang semua sisinya



vi-1 dan vi . v0 : simpul awal (simpul



berbeda dan boleh mengulang titik



asal)



(Chartrand dan Lesniak, 1986: 26).



vk : simpul akhir



3. Path (Lintasan)



vi : 1 ≤ I ≤ k adalah simpul internal Panjang



sebuah



jalan



adalah



banyaknya sisi dalam jalan tersebut.



Jika



simpul-simpul



dari



V0e1V1e2V2, … e1V1 … ek … Vk dari jalan w berlainan, maka w disebut



Sebuah jalan (walk) u – v di graf G



lintasan



adalah barisan berhingga (tak kosong)



dinamakan



siklus.



siklus



banyaknya



simpul



n,



W : u = v0, e1, v1, e2, v2, …, en, vn = v



(path).



Lintasan



tertutup dengan



dinotasikan



dengan Cn.



yang berselang seling antara titik dan



Lintasan (path) adalah trayek



sisi antara titik dan sisi, yang dimulai



tanpa rusuk dan simpul berulang.



dari titik u dan diakhiri dengan titik v



Sebagai contoh perhatikan Gambar 15,



sedemikian hingga untuk 0 < i ≤ n,



L = (v1,e1,v2,e6,v3,e4,v4) merupakan



maka ei = vi-1vi adalah sisi di G. v0



sebuah lintasan (path) pada graf G,



disebut titik awal, vn disebut titik akhir,



karena tidak memuat simpul dan rusuk



v1, v2, ..., vn-1 disebut titik internal, dan



berulang.



n



menyatakan



panjang



dari



W



(Chartrand dan Lesniak, 1986:26). 2. Trail (Jejak) Jika semua sisi pada sebuah jalan berlainan, maka jalan tersebut di sebut



Walk : uavfyfvgyhwbv



Penyelesaian:



Trail : wcxdyhwbvgy Path : xcwhyeuav Graf terhubung (connected graph) & graf



tidak



terhubung



a.



Graf terhubung



b.



Graf tidak terhubung karena tidak ada walk dari v5 ke v4



(disconnected



graph)



c.



Graf tidak terhubung karena tidak ada



Suatu graf disebut sebagai graf terhubung



walk dari v2 ke v3. Hati-hati terhadap



apabila



visualisasi



untuk



setiap



pasang



simpul u dan v di



dalam



himpunan V terdapat



lintasan



dari u ke v yang juga harus berarti ada



graf



yang



tampaknya



terhubung, padahal sebenarnya tidak. Perhatikan bahwa graf (c)



berbeda



dengan graf Gambar 27. v1



lintasan dari v ke u.



e1



v2 e2



e4 v 5



Jika tidak, maka G disebut graph takv4



terhubung (disconnected graph)



e3



v3



Teorema 4 Misalkan G adalah suatu graf, Dua titik v dan w dalam G dikatakan terhubung bila dan hanya bila ada walk dari v ke w



Misalkan G adalah graf terhubung. G adalah sirkuit Euler bila dan hanya bila



Graf G dikatakan terhubung bila dan hanya bila setiap 2 titik dalam G



semua titik dalam G mempunyai derajat genap.



terhubung.



Bukti



Graf G dikatakan tidak terhubung bila



Akan dibuktikan implikasi dari kiri ke



dan hanya bila ada 2 titik dalam G yang



kanan



tidak terhubung. Misalkan G adalah graf terhubung yang Contoh 14



merupakan sirkuit Euler.



Manakah di antara graf pada Gambar 26



Ambil sembarang titik v  V(G). Karena



yang merupakan graf terhubung?



G adalah sirkuit Euler, maka titik v harus



v



v e 3 e 2e 2 3 1 v v e 4



1



( a



4



v e v v 2e 4e 6 2 e v 4 1 5 v e3 v 3 1 ( 5 b



v



e e



v



( c



(paling



sedikit



sekali)



dalam



perjalanan kelilingnya. Ini berarti ada garis v



v



dilalui



(sebutlah e1) dari titik lain (misalkan w)



Pada masalah 7 jembatan Konigsberg yang



yang menuju ke v dalam perjalanannya.



dinyatakan dalam graf pada Gambar 24,



G merupakan sirkuit Euler, sehingga perjalanan tidak boleh berhenti pada v. Jadi,



setelah



perjalanan



sampai



harus



pada



titik



dilanjutkan



v,



dengan



mengunjungi titik lain (misalnkan titik x).



Titik A, B, C dan D mempunyai derajat ganjil



sehingga



menurut



kontraposisi



terorema 4, berarti grafnya bukanlah sirkuit Euler. Subgraf



Dalam mengunjungi titik x, perjalanan



Bondy & Murty, (1976) menyatakan



harus melalui garis e2  e1. (jikalau titik v



bahwa suatu graf H dikatakan subgraf dari



adalah titik awal perjalanan, berarti titik x



graf G apabila setiap anggota dari H



adalah titik pertama yang dikunjungi



merupakan bagian dari graf G (H C G).



dalam perjalanan tersebut). Hal ini dilihat



Dengan ketentuan harus memenuhi syarat:



pada Gambar 28.



1. simpulnya H merupakan bagian dari simpul di G, V(H) C V(G); dan



Jadi, setiap ada garis ei yang menuju titik v dalam



perjalanannya,



garis



yang



2. sisi dari H merupakan bagian dari sisi di G, E(H) C E(G).



berhubungan dengan v harus muncul berpasangan (masuk ke v dan keluar dari v).



Akibatnya,



derajat



v



merupakan



kelipatan 2, atau derajat v adalah genap. x e2 w



Ketika H C G tetapi H ≠ G, maka H disebut subgraf tepat atau proper subgraph dari G yang disimbolkan H C G. Ketika subgraf H C G dimana V(H) = V(G) maka graf H disebut subgraf rentang atau spanning subgraph dari graf G.



e1



Subgraf didapatkan dengan cara



v



Karena v adalah titik sembarang dalam G



menghapus beberapa simpul (vertices) dan



maka berarti bahwa setiap titik dalam G



sisi (edges) yang terhubung dengan titik



mempunyai derajat genap.



tersebut dan dapat juga didapatkan dengan



Kontraposisi teorema 4 adalah:



cara menghapus beberapa loop dari sebuah graf tanpa menghilangkan simpulnya hal ini



“Jika ada titik dalam G yang berderajat



akan



ganjil, maka G bukanlah sirkuit Euler”.



spanning subgraph.



Kenyataan digunakan untuk menyelidiki



Contoh:



graf yang bukan sirkuit Euler.



membuat



subgraf



rentang



atau



simpul lainnya pada graf tersebut. Notasinya (Kn), dengan n adalah banyaknya simpul. Banyaknya sisi



n pada (Kn) adalah   .  2 Graf G



Subgraf Rentang dari G



3.



Graf G dikatakan graf teratur dalam derajat p jika semua simpul pada graf G berderajat P. Graf lengkap disebut graf teratur, dengan jumlah sisi pada graf tersebut dalam derajat p adalah



np . 2



Subgraf H (G – V(3)) 4.



Graf



lingkaran



(cycles)



memiliki



jumlah simpul yang berderajar 2. 5.



Graf roda (wheels) diperoleh dengan menambahkan 1 buah simpul pada graf lingkaran, dan menghubungkan



Subgraf H (G – E(1-2,2-3, 3-4))



simpul baru tersebut dengan semua simpul pada graf tersebut. 6.



GRAF KHUSUS



Suatu graf G disebut graf bipartit jika himpunan simpulnya dapat dipisah



Suatu graf disebut graf khusus karena graf



menjadi dua partisi V1 dan V2,



tersebut memiliki ciri-ciri tertentu yang



sedemikian sehingga tiap sisi di G



mudah dikenali (Prof. Hasmawati, M.Si,



menghubungkan sebuah simpul di V1



2015). Beberapa jenis graf khusus adalah



ke sebuah simpul di V2. Notasinya



sebagai berikut:



G(V1,V2).



1.



Graf nol, yaitu graf yang himpunan



Apabila setiap simpul di V1 berajasen



sisinya merupakan himpunan kosong.



dengan semua simpul di V2, maka



Notasinya (Nn), yang dalam hal ini n



G(V1,V2)



adalah jumlah simpul.



lengkap, ditulis sebagai Kr,s dimana



Graf G disebut graf lengkap jika tiap



r  V1 dan s  V2 .



2.



simpulnya



ajasen



dengan



semua



disebut



graf



bipartit



7.



Jika G adalah graf sederhana, kita dapat membuat komplemen dari G dengan mengambil himpunan simpul pada G dan menghubungkan 2 simpul dengan sebuah sisi jika mereka tidak dihubungkan dalam G.



8.



Sebuah graf G isomorfik dengan Graf H jika terdapat pemetaan satu-satu f demikian sehingga f menjadi ajasensi.



DAFTAR PUSTAKA Bondy, J. A., & Murty, U. S. R. (1976). Graph Theory With Applications. New York: Elseiver Science Publishing co., inc. http://elearning.amikom.ac.id/index.php/d ownload/materi/999104-SI03811/2010/01/20100106_Graf_Kul.pdf /d6baf65e0b240ce177cf70da146c8d c8 https://docs.google.com/viewer?docex=1& url=http://etheses.uinmalang.ac.id/6393/1/04510046.pdf Prof. Hasmawati, M.Si. (2015). Bahan Ajar Teori Graf. Universitas Hasanuddin. Diambi ldari http://repostory.unhas.ac.id/bitstream /handle/123456789/17074/BAHAN %20AJAR-4-apload%20Repostoryjanuari%202016.pdf?sequence=1