Kompnen dan Komplement Graf

                                                      Kata  Pengantar

Assalamu’alaikum warahmatullahi wabarakatuh. Alhamdulillahirabbilalamin, banyak nikmat yang Allah berikan, tetapi sedikit sekali yang kita ingat. Segala puji hanya layak untuk Allah Tuhan seru sekalian alam atas segala berkat, rahmat, taufik, serta hidayah-Nya yang tiada terkira besarnya, sehingga penulis dapat menyelesaikan makalah dengan judul ”KOMPONENT DAN KOMPLEMET GRAF”.

Dalam penyusunannya, penulis memperoleh banyak bantuan dari berbagai pihak, karena itu penulis mengucapkan terima kasih yang sebesar-besarnya kepada guru pembina yang telah memberikan dukungan, kasih, dan kepercayaan yang begitu besar. Dari sanalah semua kesuksesan ini berawal, semoga semua ini bisa memberikan sedikit kebahagiaan dan menuntun pada langkah yang lebih baik lagi.

Meskipun penulis berharap isi dari makalah ini bebas dari kekurangan dan kesalahan, namun selalu ada yang kurang. Oleh karena itu, penulis mengharapkan kritik dan saran yang membangun agar skripsi ini dapat lebih baik lagi. Akhir kata penulis berharap agar makalah ini bermanfaat bagi semua pembaca.

                                                                   Lhokseumawe, Maret 2014

                                                                                Penyusun

KOMPONEN & KOMPLEMEN GRAF

Sejarah Graf

         Penemu graf adalah L. Euler ( Leonhard Euler ). Graf ditemukan disebuah jembatan Königsberg (tahun1736). Di kota Königsberg (sebelah timur negara bagian Prussia, Jerman), yang sekarang bernama kota Kaliningrad, terdapat sungai Pregal yg mengalir mengintari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai. Ada 7 buah jembatan yg menghubungkan daratan yg dibelah oleh sungai tersebut. Sejarah Graf : masalah jembatan Königsberg (tahun 1736)

Graf yang merepresentasikan jembatan Königsberg:

                        Simpul (vertex)            = menyatakan daratan

            Sisi (edge)                  =  menyatakan jembatan

Definisi Graf

        Graf merupakan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V,   E), yang dalam hal ini:

V  = himpunan tidak - kosong dari simpul-simpul (vertices) = { v1 , v2 , ... , vn }, dan

E  = himpunan sisi (edges) yang mnghubungkan sepasang simpul = {e1 , e2 , ... , en }

        Definisi diatas mengatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong.

Jadi sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada.

Unsur  - Unsur dari Graf

• Simpul (Vertex) adalah daratan ( titik - titik yg dihubungkan oleh jembatan ), yang dinyatakan sebagai titik (noktah). 
• Sisi (Edge) adalah jembatan yang dinyatakan sebagai garis.
• Garis Paralel adalah pada G_2, sisi E₃ = (1,3) dan sisi E₄ = (1,3) dinamakan sisi ganda.

Jenis - Jenis Graf

        Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:

1. Graf sederhana (simple graph).

Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. G1 pada contoh graf sederhana.

2. Graf tak-sederhana (unsimple-graph).

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada contoh adalah graf tak-sederhana.

        Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan  menjadi dua jenis:

1. Graf berhingga (limited graph)

      Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.

2. Graf tak-berhingga (unlimited graph)

    Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf takberhingga.

         Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas dua jenis:

1. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf     pada contoh a,b,dan c adalah graf tak-berarah.

2. Graf berarah (directed graph atau digraph)

    Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.

     Pada graf berarah notasi : d(v)

            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

        Lemma Jabat Tangan. Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali  jumlah sisi pada graf tersebut. Dengan kata lain, jika G = (V, E), maka :

Tinjau graf G₁:  d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10

                                                               = 2 ´ jumlah sisi = 2 ´ 5

Tinjau graf G₂:  d(1) + d(2) + d(3) = 3 + 3 + 4 = 10

                                           = 2 ´ jumlah sisi = 2 ´ 5

Tinjau graf G₃:  d(1) + d(2) + d(3) + d(4) + d(5) = 2 + 2 + 3 + 1 + 0 = 8

                                                                                                        = 2 ´ jumlah sisi = 2 ´ 4

Contoh :

Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing  simpul adalah:

            (a) 2, 3, 1, 1, 2

            (b) 2, 3, 3, 4, 4

Penyelesaian:  

     (a)    tidak dapat, karena jumlah derajat semua simpulnya ganjil

 (2 + 3 + 1 + 1 + 2 = 9).

(b) dapat, karena jumlah derajat semua simpulnya genap

       (2 + 3 + 3 + 4 + 4 = 16).

Lintasan yang panjangnya n dari simpul awal v₀ ke simpul tujuan v_n di dalam graf 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 graf G.

            Tinjau graf G₁: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).

Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G₁ memiliki panjang 3.

KOMPONEN GRAF

Komponen graf adalah suatu subgraf  terhubung  yang tidak termuat  pada subgraf lainya.       

Graf pada gambar (a).  mempunyai 2 komponen , sedangkan graf pada gambar (b).  mempunyai 1 komponen . selanjutnya komponen graf dengan cacah simpul ganjil disebut komplemen ganjil.

Komplemen Graf

Komplemen suatu graf G dinotasikan dg Ĝ dengan n titik adalah suatu graf sederhana dengan

1)      Titik –titik Ĝ sama dg titik G jadi  V(G)=V(Ĝ)

2)      Garis –garis Ĝ adalah komplemen garis-garis G terhadap graf lengkapnya (K_n)

        E(Ĝ)= K_n) – E(G)

      berarti  titi-titik yg dihubungkan dg garis dalam G tidak terhubung dalam Ĝ dan sebaliknya titik-titik yg terhubung dalam G menjadi tdk terhubung dalam Ĝ(dg kata laingaris yg ada pada G tidak ada pada Ĝ)

Artikel Terkait