Pewarnaan Graf

Sejarah Graf

• Masalah jembatan Konigsberg (tahun 1736)
• Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?

• Graf yang merepresentasikan jembatan Konigsberg:
• Simpul (vertex) à menyatakan daratan
• Busur (edge)    à menyatakan jembatan

 

• Euler mengungkapkan bahwa tidak mungkin seseorang berjalan melewati tepat satu kali masing-masing jembatan dan kembali lagi ke tempat semula.
• Hal ini disebabkan pada graf model jembatan Königsberg itu tidak semua simpul berderajat genap

Definisi Graf

• Graf G didefinisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G = (V, E), yang dalam hal ini:
• V = himpunan simpul-simpul (vertices)

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

• E = himpunan busur/sisi (edges) yang menghubungkan sepasang simpul

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

Contoh

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₇}

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

Jenis-Jenis Graf

1. Graf sederhana (simple graph)

Graf yang tidak mengandung gelang maupun sisi-ganda

1. Graf tak-sederhana (unsimple-graph).
   

Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph)

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 dan tidak memiliki sisi ganda.

 

Untuk lebih jelasnya silahkan download link berikut ini:

 

 

Terimakasih atas perhatiannya.

 

Untuk materi sebelumnya tentang Kriptografi, silahkan Klik Disini.

Untuk materi selanjutnya tentang Short Path, silahkan Klik Disini.