Isomorfisme pada Graph, representasi graph pada matriks, pohon, pohon biner, dan pohon

BAB I

PEMBAHASAN

A.      Isomorfisme pada graph

Dua graph G dan H dikatakan isomorfik, ditulis G = H, jika :

(i)                 Terdapat korespondensi satu-satu antara V(G) dan E(G);

(ii)               Jumlah sisi dan titiknya harus sama.

(iii)             Jumlah sikel pada pada kedua graph harus sama.

(iv)             Kedua graph harus memiliki derajat yang sama.

Banyaknya sisi yang menghubungkan dua titik di H yang berkorespondensi dengan titik u dan titik v. Misalnya pada gambar 1.8, graph G₁, isomorfik dengan graph G₂ lewat korespondensi berikut : a↔t, b↔s, c↔r, d↔q, e↔p, f↔u. Sedangkan grap G₃ tidak isomorfik dengan grap G₁ maupun G₂, karena grap G₃memuat sikel dengan panjang 3, yaitu ( x, z, m, x), tetapi di grap G₁ maupun di grap G₂  tidak ada sikel dengan panjang 3.

b

f

e

d

c

a

Gambar  1.8

u

p

q

t

s

r

n

m

z

x

k

 

Sebagai akibat dari definisi di atas, diperoleh pernyataan berikut. Jika G dan H dua grap isomorfik, maka  dan  = . Tetapi, konversi pernyataan tersebut tidak benar.

B.       Representasi Graph dalam Matriks

Selain dengan gambar, sebuah graph dapat disajikan dalam bentuk matriks. Ada dua jenis matriks yang akan digunakan, yaitu matriks berhubungan langsung (adjacency matriks) dan matriks keterkaitan (incidence matrix).

Misalkan G sebuah graph dengan V(G) = {V_1, V₂ ,....,V_n}. Matriks berhubungan langsung graph G adalah matriks bujur sangkar A(G) = (a_ij) berordo n x n yang baris-baris dan kolom-kolomnya dilabel dengan label titik-titik graph G sedemikian hingga elemen a_ij menyatakan banyaknya sisi G yang menghubungkan titik v_i dan v_j

V1

V2

V3

V4

e1e4

e2

e3

e5

e4

e7

e6

 

Perhatikan bahwa A(G) adalah matriks simetris dan unsur-unsurnya bilangan bulat non negatif. Jika G tidak memiliki gelung, maka setiap unsur A(G) yang terletak di diagonal utama adalah nol. Kalau G graph sederhana, maka unsur-unsur A(G) nol atau satu. Jika diberikan sebuah matriks simetris A berordo n x n dan unsur-unsurnya bilangan bulat non negatif, maka pasti ada graph G dengan n titik dan matriks berhubungan langsung A(G) = A.

Perhatikan bahwa derajat titik graph G diperoleh dengan menjumlahkan semua unsur A yang terletak di baris yang bersesuaian dengan titik tersebut, setelah unsur pada diagonal utama di baris itu dikalikan dua. Misalnya,

Secara umum diperoleh yang berikut. Jika A = (a_ij) matriks berhubungan-langsung graph G, maka

Jika matriks A(G) = A dikalikan dengan dirinya sendiri, diperoleh

Perhatikan unsur A² yang terletak di baris ke-i dan kolom ke-j menyatakan banyaknya jalan (v_i,v_j) di graph G dengan panjang 2. Misalnya unsur A² yang terletak di baris ke-1 dan kolom ke-4 adalah 3. Jadi ada 3 jalan (v_1,v₄) di graph G dengan panjang 2, yaitu : (v_1, e₃, v₃, e₆, v₄), (v₁, e₃, v₃, e₇, v₄), (v₁, e₃, v₃, e₈, v₄). Ada 5 jalan-(v₁,v₁) di graph G dengan panjang 2, yaitu (v₁, e₁, v₂, e₁, v₁), (v₁, e₁, v₂, e₂, v₁), (v₁, e₂, v₂, e₁, v₁), (v₁, e₂, v₂, e₂, v₁), (v₁, e₃, v₃, e₃, v₁). Begitu juga terdapat 3 jalan (v₃, v₂) di graph G dengan panjang 2, yaitu : (v₃, e₃, v₁, e₁, v₂), (v₃, e₃, v₁, e₂, v₂), (v₃, e₅, v₃, e₄, v₂). Generalisasi dari observasi ini diberikan pada teorema berikut.

Selain dengan matriks berhubungan langsung sebuah graph dapat pula disajikan dalam matriks keterkaitan. Misalkan graph G mempunyai n buah titik: v₁, v₂, ..., v_n dan t buah sisi: e₁, e₂, ..., e_n. Matriks keterkaitan (incidence matrix) graph G adalah matriks M(G) = (m_ij) berordo n x t yang baris-barisnya di label dengan label titik-titik G dan kolom-kolomnya dilabel dengan label sisi-sisi G.

V1

V2

V3

V4

e1e4

e2

e3

e5

e4

e7

e6

Contoh :

C.  Graph Pohon

            Pada bagian ini kita bicarakan graph khusus yang disebut pohon (Tree). Graph terhubung dan tidak memuat sikel disebut pohon.

Ciri-ciri pohon:

1.      Graph yang tidak memuat sikel.

2.      Dua buah graph yang terhubung oleh sebuah sisi.

Gambar-gambar pohon:

                                                              

               G                                 H                                I                                 J                     

D.  Pohon Binair

            Pada bagian ini akan dibahas salah satu kelas pohon yang banyak terapannya yaitu pohon binair. Misalkan T sebuah pohon dan V sebuah titik. Jika V berderajat tidak lebih dari dua dan titik T yang lain tidak lebih dari tiga, maka T disebut pohon binair dengan akar titik V. Pohon binair T berakar di titik V dikatakan pohon binair lengkap jika derajat titik V adalah dua atau nol dan setiap titik yang lain berderajat satu atau tiga. Selanjutnya, titik yang berderajat satudisebut titik terminal dan titik yang lain disebut titik internal. Sebagai contoh, erhatikan graph pada Gambar 2.   adalah pohon binair dengan titik akar . Titik-titik dan  adalah titik-titik internal, sedangkan titik-titik dan  adalah titik-titik terminal. Pohon adalah pohon binair dengan akar titik , titik internal , dan titik terminal  dan . Pohon  adalah pohon binair dengan akar . Karena titik akar berderajat dua dan setiap titik yang lain di   berderajat satu atau tiga, maka  adalah pohon binair lengkap. Perhatikan bahwa pohon binair  ataupun  tidak lengkap. Pohon binair tidak lengkap karena titik interval   berderajat dua, sedangkan pohon binair   tidak lengkap karena titik akarnya berderajat satu.             

V1

V3

V44

V5

V2442

V6

Pohon   adalah pohon binair  dengan titik akar . Titik-titik dan  adalah titik-titik internal, sedangkan titik-titik dan  adalah titik-titik terminal.

 

U1

U4

U3

U2

T₁

Pohon adalah pohon binair dengan akar titik , titik internal , dan titik terminal  dan .

 

T₂

W2

W1

W3

W7

W6

W9

W8

W5

W4

Pohon  adalah pohon binair dengan akar . Karena titik akar berderajat dua dan setiap titik yang lain di   berderajat satu atau tiga, maka  adalah pohon binair lengkap.

 

                       

                        T₃

Keterangan : T₁ pohon binair tak lengkap dengan akar V₁

                      T₂ pohon binair tak lengkap dengan akar U₁

                      T₃ pohon binair lengkap dengan akar  W₁        

Sebagai akibat teorema jabat tangan dan definisi pohon binair lengkap, maka banyaknya titik pohon binar lengkap selalu bilangan ganjil dan selisih antara banyaknya titik terminal dan banyaknya titik titik internal adalah satu.lengkap dengan n titik.

E. Hutan (forest)

Hutan adalah :

- kumpulan pohon yang saling lepas, atau

- graf tidak terhubung yang tidak mengandung sirkuit.

Setiap komponen di dalam graf terhubung tersebut adalah pohon.

 

Hutan yang terdiri dari lima buah pohon.

                                                       

DAFTAR PUSTAKA

Budayasa,  Ketut.2007.  Teori Graph dan aplikasinya. Surabaya: Unesa university press.

Http://informatika.stei.itb.ac.id/rinaldi.munir/Matdis/2007-2008/MalakahF2153-0708-039.pdf|27Maret2013|.