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 sanggup menuntaskan makalah dengan judul ”KOMPONENT DAN KOMPLEMET GRAF”.
Dalam penyusunannya, penulis memperoleh banyak proteksi dari aneka macam pihak, alasannya itu penulis mengucapkan terima kasih yang sebesar-besarnya kepada guru pembina yang telah menawarkan dukungan, kasih, dan dogma yang begitu besar. Dari sanalah semua kesuksesan ini berawal, semoga semua ini sanggup menawarkan 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 alasannya itu, penulis mengharapkan kritik dan saran yang membangun semoga skripsi ini sanggup lebih baik lagi. Akhir kata penulis berharap semoga makalah ini bermanfaat bagi semua pembaca.
Lhokseumawe, Maret 2014
Penyusun
KOMPONEN & KOMPLEMEN GRAF
Sejarah Graf
Penemu graf yaitu L. Euler ( Leonhard Euler ). Graf ditemukan disebuah jembatan Königsberg (tahun1736). Di kota Königsberg (sebelah timur negara bab Prussia, Jerman), yang kini berjulukan kota Kaliningrad, terdapat sungai Pregal yg mengalir mengintari pulau Kneiphof kemudian bercabang menjadi dua buah anak sungai. Ada 7 buah jembatan yg menghubungkan daratan yg dibelah oleh sungai tersebut. Sejarah Graf : problem 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 menyampaikan bahwa V dihentikan 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) yaitu daratan ( titik - titik yg dihubungkan oleh jembatan ), yang dinyatakan sebagai titik (noktah).
- Sisi (Edge) yaitu jembatan yang dinyatakan sebagai garis.
- Garis Paralel yaitu 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 pola 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 pola yaitu graf tak-sederhana.
Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf sanggup digolongkan menjadi dua jenis:
1. Graf berhingga (limited graph)
Graf berhingga yaitu 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 pola a,b,dan c yaitu 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 yaitu genap, yaitu dua kali jumlah sisi pada graf tersebut. Dengan kata lain, bila G = (V, E), maka :
Tinjau graf G1: d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10
= 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G2: d(1) + d(2) + d(3) = 3 + 3 + 4 = 10
= 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G3: 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 bila derajat masing-masing simpul adalah:
(a) 2, 3, 1, 1, 2
(b) 2, 3, 3, 4, 4
Penyelesaian:
(a) tidak dapat, alasannya jumlah derajat semua simpulnya ganjil
(2 + 3 + 1 + 1 + 2 = 9).
(b) dapat, alasannya 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) yaitu sisi-sisi dari graf G.
Tinjau graf G1: lintasan 1, 2, 4, 3 yaitu lintasan dengan barisan sisi (1,2), (2,4), (4,3).
Panjang lintasan yaitu jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G1 memiliki panjang 3.
KOMPONEN GRAF
Komponen graf yaitu 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 suplemen ganjil.
mempunyai 2 komponen , sedangkan graf pada gambar (b). mempunyai 1 komponen . selanjutnya komponen graf dengan cacah simpul ganjil disebut suplemen ganjil. Komplemen Graf
Komplemen suatu graf G dinotasikan dg Ĝ dengan n titik yaitu suatu graf sederhana dengan
1) Titik –titik Ĝ sama dg titik G jadi V(G)=V(Ĝ)
2) Garis –garis Ĝ yaitu suplemen 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 Ĝ)
0 Response to "Kompnen Dan Komplement Graf"
Posting Komentar