Matematika2: Graf

Sifat-sifat Pohon (Graf Tree)

Sifat-sifat Pohon (Graf Tree)

· Teorema. Misalkan G = ( V , E ) adalah graf tak-berarah sederhana dan jumlah simpulnya n . Maka, semua pernyataan di bawah ini ...

Baca selengkapnya »

· Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit  · Hutan (forest) adalah - kumpulan pohon yang saling lepas, atau - graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon.  · Pohon mempunyai bilangan kromatis = 2.

Pohon (Graf Tree)

· Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit · Hutan ( forest ) adalah - kumpulan pohon ya...

Baca selengkapnya »

Terminologi Graf

1. Ketetanggaan (Adjacent) Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung. Tinjau graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3, simpul 1 tidak bertetangga dengan simpul 4. 2. Bersisian (Incidency) Untuk sembarang sisi e = (vj, vk) dikatakan e bersisian dengan simpul vj , atau e bersisian dengan simpul vk Tinjau graf G1: sisi (2, 3) bersisian dengan simpul 2 dan simpul 3, sisi (2, 4) bersisian dengan simpul 2 dan simpul 4, tetapi sisi (1, 2) tidak bersisian dengan simpul 4. 3. Simpul Terpencil (Isolated Vertex) Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya. Tinjau graf G1: simpul 5 adalah simpul terpencil. 4. Graf Kosong (null graph atau empty graph) Graf yang himpunan sisinya merupakan himpunan kosong (Nn). Graf N5 : 5. Derajat (Degree) Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut. Notasi: d(v) Tinjau graf G1: d(1) = d(4) = 2 d(2) = d(3) = 3 Tinjau graf G3: d(5) = 0  simpul terpencil d(4) = 1  simpul anting-anting (pendant vertex) Tinjau graf G2: d(1) = 3  bersisian dengan sisi ganda d(2) = 4  bersisian dengan sisi gelang (loop) Pada graf berarah, 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 d(v) = din(v) + dout(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 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

Terminologi Graf

1. Ketetanggaan (Adjacent) Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung. Tinjau graf G1 : simpul 1 bertetangga den...

Baca selengkapnya »

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. 2. Graf tak-sederhana (unsimple-graph). Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). 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 tak-berhingga. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis: 1. Graf tak-berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. 2. Graf berarah (directed graph atau digraph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.

Jenis-Jenis Graf

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis: 1. Graf sederhana (simple graph). ...

Baca selengkapnya »

Graf

· Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. · Gambar di bawah ini sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah. · Sejarah Graf: masalah jembatan K<span style="font-size:16.0pt;mso-bidi-font-size:10.0pt;font-family:"Courier New"; mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"; mso-bidi-font-family:"Times New Roman";mso-char-type:symbol;mso-symbol-font-family: "Courier New"">önigsberg (tahun 1736)  · Graf yang merepresentasikan jembatan K<span style="font-size:16.0pt;mso-bidi-font-size:10.0pt;font-family:"Courier New"; mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"; mso-bidi-font-family:"Times New Roman";mso-char-type:symbol;mso-symbol-font-family: "Courier New";mso-bidi-font-weight:bold">önigsberg: Simpul (vertex) <span style="font-size:16.0pt;mso-bidi-font-size:10.0pt;font-family:Wingdings; mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"; mso-char-type:symbol;mso-symbol-font-family:Wingdings;mso-bidi-font-weight: bold">à menyatakan daratan Sisi (edge) <span style="font-size:16.0pt; mso-bidi-font-size:10.0pt;font-family:Wingdings;mso-ascii-font-family:"Times New Roman"; mso-hansi-font-family:"Times New Roman";mso-char-type:symbol;mso-symbol-font-family: Wingdings;mso-bidi-font-weight:bold">à menyatakan jembatan  Definisi Graf Graf G = (V, E), yang dalam hal ini: V = himpunan tidak-kosong dari simpul-simpul (vertices) = { v1 , v2 , ... , vn } E = himpunan sisi (edges) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en }

Graf

· Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. · Gambar di bawa...

Baca selengkapnya »

Matematika2

Sifat-sifat Pohon (Graf Tree)

Pohon (Graf Tree)

Terminologi Graf

Jenis-Jenis Graf

Graf

Entri Populer

Arsip Blog

Komentar