Metode Graf Matematika Diskrit

Dapatkah melalui tiap jembatan tepat sekali dan kembali lagi ke tempat sebelumnya?

Graf yang merepresentasikan jembatan Konigsberg:

Simpul (vertex) -> menyatakan daratan
Busur (edge) -> menyatakan

Jembatan

Euler mengutarakan bahwa tidak mungkin seorang berjalan melalui tepat satu kali masing-masing jembatan dan balik lagi ke arah tempat sebelumnya.

Perihal ini karena pada graf model

jembatan Königsberg itu tidak seluruhnya simpul berderajat genap.

Pengertian Graf

Graf G diartikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G = (V, E), yang dalam masalah ini:

V = himpunan simpul-simpul (vertices)

E = himpunan busur/segi (edges) yang menyambungkan sepasang simpul =

Contohnya :

Macam - macam jenis Graf

1. Graf sederhana (simple graph)

Graf yang tidak memiliki kandungan gelang atau sisi-ganda.

2. Graf tidak-sederhana (unsimple-graph).

Graf yang memiliki kandungan sisi ganda atau gelang diberi nama graf tidak-sederhana(unsimple graph)

3. Graf tak-berarah (undirected graph)

Graf yang sisinya tidak memiliki tujuan arah disebut graf tak-berarah.

4. Graf berarah (directed graph atau digraph)

Graf yang tiap sisinya diberi tujuan arah dan tidak mempunyaisisi ganda.

Terminologi Graf

1. Ketetanggaan (Adjacent)

Dua buah simpul disebutkan bertetangga jika keduanya tersambung langsung.

Contoh :

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

Contoh :

Tinjau graf G1 :

sisi (2, 3) bersisian dengan simpul 2 dan simpul 3
sisi (1, 2) tidak bersisian dengan simpul 4.

3. Simpul Terpencil (Isolated Vertex)

Simpul terasing adalah simpul yang tidak memiliki sisi yang bersisian dengannya.

Contoh:

Tinjau graf G3 :

simpul 5 adalah simpul terpencil.

4. Graf Kosong (null graph atau empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong (Nn).

5. Derajat (Degree)

Derajat satu simpul ialah jumlah sisi yang bersisian dengan simpul itu.

Notasi: d(v)

Tinjau graf G1 :

d(1) = d(4) = 2

d(2) = d(3) = 3

Derajat Graf Berarah

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 di suatu graf ialah genap, yakni dua kali jumlah busur pada graf itu.

Dalam kata lain, bila G = (V, E), karena itu:

Pewarnaan Graf

Sebuah pewarnaan dari graph G ialah sebuah pemetaan beberapa warna ke simpul-simpul dari G sebegitu sampai simpul relasinya (yang bertetangga) memiliki warna warna yang lain.
Bilangan kromatik dari G ialah jumlah warna minimal yang dibutuhkan untuk memberi warna graph G, disimbolkan dgn χ(G) (chi G)

Algoritma Welch Powel

Urutkan simpul-simpul G dalam derajat yang menurun. Posisi ini kemungkinan tidak unik karena beberapa simpul memiliki derajat sama.
Gunakan satu warna untuk memberi warna simpul pertama (yang memiliki derajat paling tinggi) dan simpul-simpul lain (dalam posisi yang berurutan) yang tidak bertetangga dengan simpul pertama.
Mulai lagi dengan dengan simbul dengan derajat paling tinggi dan ulang proses pewarnaan simpul yang tidak berwarna sebelumnya dengan memakai warna kedua.
Terus ulangi dengan tambahan warna sampai semua simpul sudah diwarnai.