Teori Graf (graph–included tree)

Dasar-Dasar Graph Representation (Representasi Graf)

Graf merupakan struktur matematis yang mewakili hubungan berpasangan antar objek. Graf merupakan struktur alur yang mewakili hubungan antar objek. Untuk lebih jelasnya, silakan amati visualisasi pada dua komponen dasar berikut:

• Node: Berikut ini adalah komponen yang paling penting dalam graf. Node merupakan entitas yang hubungannya direpresentasikan dengan edge. Jika sebuah graf terdiri dari 2 node, $A$ serta sebuah edge tanpa arah di antaranya, maka hal tersebut merepresentasikan hubungan bi-direksional antara node dan edge.
• Edge: Edge merupakan komponen yang digunakan untuk merepresentasikan hubungan antara beragam node di dalam graf. Edge di antara dua node menunjukkan hubungan satu arah atau dua arah antar node.

Jenis node

• Root node: Root node adalah ancestor semua node dalam graf. Root node tidak memiliki ancestor. Setiap graf berisi hanya satu root node. Pada umumnya, penelusuran graf harus dimulai dari dari root node.
• Leaf node: Dalam graf, leaf node mewakili node yang tidak memiliki suksesor. Node ini hanya memiliki node ancestor. Dengan kata lain, leaf node mungkin memiliki beberapa incoming edge tapi mereka sama sekali tidak memiliki outgoing edge.

Jenis graf

• Undirected (tanpa arah): Undirected graph adalah graf yang semua edge miliknya bersifat bi-directional. Dengan kata lain edge, tersebut tidak memiliki arah tertentu.

• Directed: Directed graph adalah graf yang semua edge miliknya bersifat uni-directional, dengan kata lain edge tersebut menuju ke arah tertentu.

• Weighted: Dalam weighted graf, setiap edge memiliki weight (bobot atau biaya). Perhatikan graf berisi 4 node yang ditunjukkan pada diagram di bawah ini. Sebagaimana yang dapat Anda lihat, setiap edge memiliki weight/bobot/biaya yang ditetapkan padanya. Jika Anda ingin berpindah dari vertex 1 ke vertex 3 Anda dapat menggunakan salah satu jalur berikut:
  • 1 -> 2 -> 3
  • 1 -> 3
  • 1 -> 4 -> 3
  Maka dari itu biaya total dari masing-masing jalur adalah sebagai berikut
  – Biaya total dari 1 -> 2 -> 3 akan sebesar (1 + 2), atau 3 unit
  – Biaya total dari 1 -> 3 sebesar 1 unit
  – Biaya total dari 1 -> 4 -> 3 akan sebesar (3 + 2) yaitu 5 unit

• Cyclic: Graf dikatakann cyclic jika graf tersusun dari jalur yang dimulai dari suatu vertex dan berakhir di vertex yang sama. Path tersebut disebut cycle. Istilah acyclic graph merujuk pada graf yang tidak memiliki cycle.Tree merupakan undirected graph yang dua verteks hanya dihubungkan hanya oleh satu path. Tree adalah acyclic graph dan memiliki N – 1 edge di mana N merupakan jumlah verteks. Setiap node di dalam graph mungkin memiliki satu atau beberapa parent node. Namun pada tree, setiap node (kecuali root node) hanya terdiri dari satu parent nodeCatatan: Root node tidak memiliki parent.Tree tidak dapat memiliki cycle atau self loop, namun hal yang sama tidak berlaku ke graf.

Representasi Graf

Anda dapat merepresentasikan graf dalam banyak cara. Cara yang paling umum untuk merepresentasikan graf adalah sebagai berikut:

Adjacency matrix

Adjacency matrix adalah binary matriks VxV dari A. Elemen $A_{i,j}$

adalah 1 jika terdapat edge dari vertex i ke vertex j selain kondisi tersebut $A_{i,j}$

 adalah 0.

Catatan: Matriks binary adalah matriks yang sel miliknya hanya dapat memiliki salah satu dari dua nilai yang mungkin – 0 atau 1.

Adjacency matrix juga dapat dimodifikasi untuk weighted graph. Sehingga alih-alih menyimpan 0 atau 1 dalam $A_{i,j}$

, weight atau bobot edge akan disimpan.

Dalam sebuah undirected graph, jika $A_{i,j}$

= 1, maka $A_{j,i}$ = 1.Dalam directed graph, jika $A_{i,j}$ = 1, maka $A_{j,i}$

mungkin bernilai 1 atau mungkin tidak bernilai 1.

Adjacency matrix memberikan constant time access (akses waktu konstan) (O(1) ) untuk menentukan apakah terdapat edge antara dua node. Kompleksitas waktu adjacency matrix adalah O($V^2$).

Adjacency matrix untuk graf berikut ini adalah :
i/j : 1 2 3 4
1 : 0 1 0 1
2 : 1 0 1 0
3 : 0 1 0 1
4 : 1 0 1 0

Adjacency matrix untuk graf berikut ini adalah:

i/j: 1 2 3 4
1 : 0 1 0 0
2 : 0 0 0 1
3 : 1 0 0 1
4 : 0 1 0 0

Amati directed graph yang diberikan di atas. Mari kita membuat graf dengan adjacency matrix dan tampilkan semua edge yang ada di dalam graf.

Semoga Bermanfaat