Matematika Diskrit : Representasi Graf dalam Matriks

📋 Daftar Isi

Matriks Ketetanggaan (Adjacency Matrix)

Misalkan G adalah graf tak berarah dengan titik-titik v₁, v₂,…,v_n (n berhingga).

Matriks ketetanggaan yang sesuai dengan graf G adalah matriks A = (a_ij) dengan a_ij = jumlah garis yang menghubungkan titik v_i dengan v_j

A = [aij],

1, jika simpul i dan j bertetangga(/∑grs)

a_ij = {

0, jika simpul i dan j tidak bertetangga

Graf direpresentasikan dengan cara menyatakannya dalam jumlah garis yang menghubungkan titik-titiknya. Jumlah baris (dan kolom) matriks ketetanggaan sama dengan jumlah titik dalam graf.

Contoh :

Matriks ketetanggaan nol-satu tidak dapat digunakan untuk merepresentasikan graf yang mempunyai sisi ganda.

Beberapa hal yang menjadi catatan dalam merepresentasikan graf dalam matrik ketetanggaan:

Matriks ketetanggan untuk graf sederhana dan tidak berarah merupakan matriks simetris.

Graf tidak mempunyai loop jika dan hanya jika semua elemen diagonal utamanya = 0. Loop pada vi bersesuaian dengan a_ii = 1

Matriks ketetanggaan dapat dipakai untuk mendeteksi graf yang tidak terhubung secara mudah.

Derajat tiap simpul i:

Untuk graf tak-berarah

\[ d(v_{i}) \space = \space \sum_{j=1}^{n}a_{ij} \space = \sum_{i=1}^{n}a_{ij} \]

Untuk graf berarah

\[ d_{in}(v_{j}) \space = \space jumlah \space nilai \space pada \space kolom \space j \space = \space \sum_{i=1}^{n}a_{ij} \]

\[ d_{out}(v_{i}) \space = \space jumlah \space nilai \space pada \space kolom \space i \space = \space \sum_{j=1}^{n}a_{ij} \]

Derajat graf G = jumlah semua komponen matriks

\[ \sum_{i} \sum_{j} a_{ij} \]

Graf G adalah graf Bipartite (Km,n) jika dan hanya jika matriks ketetanggaannya berbentuk

\[ \begin{pmatrix} O & 1_{m} \\ 1_{n} & O \\ \end{pmatrix} \]

dengan O= matriks 0

1_m = matriks m x n semua elemen = 1

1_n = matriks n x m semua elemen = 1

G graf lengkap jika dan hanya jika semua elemen dalam diagonal utama = 0, semua elemen di luar diagonal utama = 1.

Matriks ketetanggaan untuk graf berbobot

Matriks ketetanggaan dapat dipakai untuk menghitung banyaknya kemungkinan walk dengan panjang tertentu antara 2 titik.

Misalkan A = (a_ij) matriks ketetanggaan graf G.

Aⁿ = A×A×A …×A (sebanyak n kali). Banyaknya kemungkinan path dengan panjang n dari titik v_i ke v_j adalah elemen a_ij pada matriks Aⁿ (=a_ijⁿ)

Matriks Biner (Incidency Matrix)

Misalkan G adalah graf tanpa loop dengan n titik v₁, v₂, …,v_n dan k garis e₁, e₂, … e_k.

Matriks yang sesuai adalah matriks berukuran n × k yang elemennya adalah:

A = [a_ij],

1, jika simpul i bersisian dengan sisi j

a_ij = {
0, jika simpul i tidak bersisian dengan sisi j

Derajat titik v_i = jumlah semua elemen pada baris ke-i

Derajat total = jumlah semua elemen dari matriks

Matriks biner dapat dipakai untuk menyatakan graf secara tepat. Setiap garis berhubungan dengan 2 titik. Maka dalam matriks biner, setiap kolom mempunyai tepat 2 elemen 1, sisanya elemen 0.

Jumlah elemen pada baris ke-i= derajat titik v_i. Derajat total graf G= jumlah semua elemen matriks.

Jika semua elemen pada beris ke-i = 0, maka titik v_i adalah titik terasing. Dua kolom yang semua elemennya sama menyatakan garis yang parallel atau sisi ganda.