Matematika Diskrit : Terminologi Graf

📋 Daftar Isi

Ketetanggan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

Tinjau graf G₁ :

Simpul 1 bertetangga dengan simpul 2 dan 3
Simpul 1 tidak bertetangga dengan simpul 4

Bersisian (Incidency)

Untuk sembarang sisi e = (v_j, v_k) dikatakan :

e bersisian dengan simpul v_j
e bersisian dengan simpul v_k

Tinjau graf G₁:

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

Simpul Terpencil (Isolated Vertex)

Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.

Tinjau graf G₃:

Simpul 5 adalah simpul terpencil.

Graf Kosong (Null graph atau Empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong (N_n).

Graf N₅ :

Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.

Notasi: d(v)

Tinjau graf G₁:

d(1) = d(4) = 2
d(2) = d(3) = 3

Tinjau graf G₂:

d(1) = 3 → bersisian dengan sisi ganda
d(3) = 4 → bersisian dengan sisi gelang (loop)

Tinjau graf G₃:

d(5) = 0 → simpul terpencil
d(4) = 1 → simpul anting-anting (pendant vertex)

Pada graf berarah,

d_in(v) = derajat-masuk (in-degree)

= jumlah busur yang masuk ke simpul v

d_out(v) = derajat-keluar (out-degree)

= jumlah busur yang keluar dari simpul v

d(v) = d_in(v) + d_out(v)

Tinjau graf G₄:

d_in(1) = 2; d_out(1) = 1

d_in(2) = 2; d_out(2) = 3

d_in(3) = 2; d_out(3) = 1

d_in(4) = 1; d_out(3) = 2

Lemma Jabat Tangan

Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graf tersebut.

Dengan kata lain, jika G = (V, E), maka

\[ \sum_{v=V}d(v)=2|E| \]

Tinjau graf G₁: d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10 = 2 × jumlah sisi = 2 × 5

Tinjau graf G₂: d(1) + d(2) + d(3) = 3 + 3 + 4 = 10 = 2 × jumlah sisi = 2 × 5

Tinjau graf G₃: d(1) + d(2) + d(3) + d(4) + d(5) = 2 + 2 + 3 + 1 + 0 = 8 = 2 × jumlah sisi = 2 × 4

Akibat dari lemma (corollary):

Untuk sembarang graf G, banyaknya simpul berderajat ganjil selalu genap

Contoh

Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah:

2, 3, 1, 1, 2
2, 3, 3, 4, 4

Penyelesaian:

Tidak dapat, karena jumlah derajat semua simpulnya ganjil (2 + 3 + 1 + 1 + 2 = 9).
Dapat, karena jumlah derajat semua simpulnya genap (2 + 3 + 3 + 4 + 4 = 16).

Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v₀ ke simpul tujuan v_n di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v₀, e₁, v₁, e₂, v₂,… , v_{n –1}, e_n, v_nsedemikian sehingga e₁ = (v₀, v₁), e₂ = (v₁, v₂), … , e_n = (v_n-1, v_n) adalah sisi-sisi dari graf G.

Tinjau graf G₁:

Lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).

Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G₁memiliki panjang 3.

Siklus (Cycle) atau Sirkuit (Circuit)

Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.

Tinjau graf G₁:

1, 2, 3, 1 adalah sebuah sirkuit.

Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G₁ memiliki panjang 3.

Terhubung (Connected)

Dua buah simpul v₁ dan simpul v₂ disebut terhubung jika terdapat lintasan dari v₁ ke v₂.

G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul v_i dan v_j dalam himpunan V terdapat lintasan dari v_i ke v_j.

Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).

Contoh graf tak-terhubung:

Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G diperoleh dengan menghilangkan arahnya).

Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.

Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly coonected).

Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.