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)

= { v1 , v2 , โ€ฆ , vn }

E = himpunan sisi (edges) yang menghubungkan sepasang simpul

= {e1 , e2 , โ€ฆ , en }


Contoh 1

Pada gambar 2,

G1 adalah graf dengan

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

G2 adalah graf dengan

V = { 1, 2, 3, 4 }

E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) } = {e1, e2, e3, e4, e5, e6, e7}

G3 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) } = {e1, e2, e3, e4, e5, e6, e7, e8}

Pada G2, sisi e3 = (1, 3) dan sisi e4 = (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 G3, sisi e8 = (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. G1 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). G2 dan G3 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, (vj, vk) โ‰  (vk, vj) โ†’ dua busur yang berbeda.

Untuk busur (vj, vk), vj (simpul asal) dan vk (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

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up