Matematika Diskrit : Definisi dan Jenis-Jenis Graf

Definisi

Suatu graf G terdiri dari 2 himpunan, yaitu himpunan titik-titik tidak kosong (V(G)) dan himpunan garis-garis (E(G)).

Graf G = (V, E), yang dalam hal ini:

V = himpunan tidak-kosong dari simpul-simpul (vertices)

= { v₁ , v₂ , … , v_n }

E = himpunan sisi (edges) yang menghubungkan sepasang simpul

= {e₁ , e₂ , … , e_n }

---

Contoh 1

Pada gambar 2,

G₁ adalah graf dengan

V = { 1, 2, 3, 4 } E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }

G₂ adalah graf dengan

V = { 1, 2, 3, 4 }

E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) } = {e₁, e₂, e₃, e₄, e₅, e₆, e₇}

G₃ adalah graf dengan

V = { 1, 2, 3, 4 }

E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) } = {e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈}

Pada G₂, sisi e₃ = (1, 3) dan sisi e₄ = (1, 3) dinamakan sisi-ganda/garis paralel (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.

Pada G₃, sisi e₈ = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.

---

Jenis-Jenis Graf

Berdasarkan Sisi Ganda

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

Graf sederhana (simple graph)

Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G₁ pada gambar 2 adalah contoh graf sederhana.

Graf tak-sederhana (unsimple-graph)

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G₂ dan G₃ pada gambar 2 adalah contoh graf tak-sederhana.

Ada dua macam graf tak sederhana:

1. Graf ganda→graf yang mengandung sisi ganda
2. Graf semu→ graf yang mengandung gelang (graf semu lebih umum)

Jumlah simpul pada graf disebut kardinalitas graf → n = |V|

Jumlah sisi → m = |E|

---

Berdasarkan Jumlah Simpul

Berdasarkan jumlah simpul dalam graf, dapat dibedakan menjadi:

1. Graf berhingga → graf dengan jumlah simpul berhingga , n
2. Graf tak berhingga → graf dengan jumlah simpul tak berhingga

---

Berdasaran Orientasi Arah pada Sisi

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

Graf tak-berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada gambar 2 adalah graf tak-berarah.

Graf berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada gambar 3 adalah graf berarah.

Dalam graf berarah, (v_j, v_k) ≠ (v_k, v_j) → dua busur yang berbeda.

Untuk busur (v_j, v_k), v_j (simpul asal) dan v_k (simpul terminal)

---

Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Graf, daftar lengkapnya adalah sebagai berikut.

---

Tonton juga video pilihan dari kami berikut ini