Pewarnaan Graf

Posted on

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)

= { v1 , v2 , … , vn }

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

= {e1 , e2 , … , en }

Contoh


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}

Pada G2, sisi e3 = (1, 3) dan sisi e4 = (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.

 

 

 

 

 

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s