Graph problem

DASAR-DASAR TEORI GRAPH

Graph ialah kelompok dari node (simpul) dan garis dimana pasangan-pasangan node tersebut dihubungkan oleh segmen garis (busur).  Node ini biasa disebut simpul (verteks) dan segmen garis disebut ruas (edge).

Simpul dan ruas dalam graph dapat diperluas dengan penambahan informasi.  Sebagai contoh, simpul bisa diberi nomor atau label dan ruas dapat diberi nilai juga.  Perluasan dengan pemberian informasi ini sangat berguna dalam penggunaan graph untuk banyak aplikasi komputer. 

Dalam kehidupan sehari-hari banyak persoalan yang dimodelkan dengan graph.  Graph dipakai untuk membantu memecahkan masalah.  Dari model graph yang dibuat, suatu masalah dapat dipahami agar menjadi lebih mudah, dengan kata lain graph adalah sebuah alat untuk mempermudah pekerjaan (jembatan penghubung).  Untuk kemudian diturunkan metode pemecahannya.

JENIS-JENIS GRAPH

Setelah menjelaskan tentang pengertian graph, kita akan membahas persoalan jenis-jenis graph. Untuk jenis-jenis graph terdapat 3 pengelompokan secara umumnya, ialah : 

1.      Berdasarkan ada tidaknya gelang (bulatan)

Untuk jenis ini kemudian ada 2 pengelompokan lagi, ialah :

• Graph sederhana (Simple Graph)

Graph yang tidak mengandung bulatan maupun sisi-ganda dinamakan graf sederhana.

• Graph tak-sederhana  (unsimple-graf/multigraf)

Graph yang mengandung ruas ganda (cabang) dinamakan graf tak-sederhana 

2.      Berdasarkan jumlah simpul (Cabang)

Pada pembagian jenis graph untuk simpul atau percabangan dibagi menjadi 2 bagian, ialah :

• Graph Terbatas (limited graph)

Graph yang jumlah simpulnya bernilai n, atau bisa diketahui.

• Graf  Tak Terbatas (unlimited graph)

Graph yang jumlah simpulnya tak terbatas. 

3.      Berdasarkan  arah pada sisi (Pola percabangan)

Untuk masalah ini, graph mempunyai 2 variasi arah percabangan (pola) dalam penghubungan sebuah simpul, ialah :

• Graf berarah (directed graph)

• Graph tak-berarah (undirected graph)

Pembahasan mengenai masalah jenis-jenis graph mungkin hanya sampai disana, karena sampai saat ini baru ada itu saja. Mungkin kedepannya akan ada lagi teori graph yang muncul.

TERMINOLOGI GRAPH

Terminologi Graph dibagi menjadi 7 bagian rancangan, ialah : 

1.      Subgraph dan Komplemen Subgraph 

2.      Subgraph yang Direntang (Spanning Subgraph)

3.      Derajat (Degree)

4.      Ketetanggaan (Adjacent)

5.      Bersisian (Incidency)

6.      Simpul Terpencil (Isolated Vertex)

7.      Graph Kosong (null graf atau empty graph)

OPERASI GRAF

1.      Gabungan G1 ∪ G2 adalah graph dgn himpunan ruasnya E1 ∪ E2.

2.      Irisan G1 ∩ G2 adalah graph degan himpunan ruasnya E1 ∩ E2.

3.      Selisih G1 - G2 adalah graph degan himpunan ruasnya E1 - E2.

4.      Selisih G2 – G1 adalah graph degan himpunan ruasnya E2 - E1.

5.      Penjumlahan ring G1 ⊕ G2 adalah graph degan himpunan ruasnya (E1 ∪ E2) - (E1 ∩ E2) atau (E1 - E2) ∪ (E2 - E1).

PENGHAPUSAN (DELETION)

1.      Penghapusan Simpul

2.      Penghapusan Ruas

 Sumber :  http://rifki_kosasih.staff.gunadarma.ac.id/Downloads/files/37568/Bab+1+-+Dasar+Teori+Graf.pdf