.breadcrumbs{padding:0 5px 5px 0;margin:0 0 5px;font-size:11px;border-bottom:1px dotted #ccc;font-weight:normal}
Latest Movie :

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 G2, sisi E3 = (1,3) dan sisi E4 = (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)
            din(v) = derajat-masuk (in-degree)
          = jumlah busur yang masuk ke simpul  v

            dout(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 G1d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10
                                                               = 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G2d(1) + d(2) + d(3) = 3 + 3 + 4 = 10
                                           = 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G3d(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 v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,... , vn –1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah sisi-sisi dari graf G.
            Tinjau graf G1: 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 G1 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 (Kn)
        E(Ĝ)= Kn) – 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
Share this article :

Poskan Komentar

 
Support : Creating Website | Johny Template | Mas Template
Copyright © 2011. Blog lussy Chandra - All Rights Reserved
Template Created by Creating Website Published by Mas Template
Proudly powered by Blogger