Teorema Cayley dan Teorema Matriks Pohon

Hasmawati

Jurusan Matematika Universitas Hasanuddin (UNHAS)

Jalan Perintis Kemerdekaan KM.10 Makassar 90245 hasma_ba@yahoo.com

Abstract

Subgraf H disebut subgraf perentang dari graf G apabila V(H) = V(G). Subgraf perentang yang merupakan

pohon disebut pohon perentang. Menghitung banyaknya pohon perentang dari sembarang graf terhubung dapat

dilakukan dengan menggunakan Teorema Matriks pohon. Sedangkan banyaknya pohon berlabel yang tidak

isomorfik dapat dilakukan dengan menggunakan Teorema Cayley. Dalam makalah ini, dibahas kaitan antara

Teorema Cayley dengan Teorema Matriks Pohon.

Keywords : Subgraf perentang, Enumerasi, Teorema Cayley, Teorema Matriks Pohon

1. Pendahuluan

Graf adalah pasangan himpunan (V,E) dengan V adalah himpunan tidak kosong yang anggotanya disebut titik dan E adalah himpunan yang anggotanya merupakan pasangan dari anggota-anggota himpunan V. Himpunan V disebut himpunan titik dan himpunan E disebut himpunan sisi. apabila suatu grraf dinotasikan dengan G, maka G = (V,E). Dalam hal ini V = V(G) dan E = E(G. Jika sisi e = uv E(G), maka titik u dikatakan bertetangga dengan titik v, juga sebazliknya, dan sisi e dikatakan terkait dengan titik u dan titik v. Selanjutnya, jika uv dan uv = vu untuk setiap u, v V(G), maka graf G disebut graf sederhana. Graf yang dibicarakan dalam makalah ini adalah graf sederhana dan berhingga.

Graf F=(V',E') disebut subgraf dari G jika V'V(G) dan E’ E(G). Apabila V' = V(G), maka subgraf F disebut subgraf perentang. Selanjutnya, apabila subgraf perentang tersebut merupakan pohon, maka subgraf tersebut dikatakan pohon perentang. Misalkan S V(G). Penulisan G[S] menyatakan subgraf maksimal dari G dengan himpunan titik S, yang disebut subgraf terinduksi dari G.

Graf-graf yang memiliki ciri-ciri tertentu pada umumnya telah memiliki definisi dan nama tertentu. Graf-graf dengan ciri-ciri tertentu tersebut sangat banyak, namun dalam makalah ini disajikan hanya beberapa jenis diantaranya lintasan, siklus, pohon dan graf lengkap. Lintasan adalah graf yang titik-titik dan sisinya dapat diurutkan dengan label v1, e1, v2, e2, ..., vn-1, en-1, vn dimana ei= vivi+1. Graf yang hanya terdiri atas satu lintasan dengan n titik disebut graf lintasan berorde n, dan dinotasikan Pn. Misalkan Pn adalah suatu lintasan dengan V(Pn)= {v1, v2, ..., vn}. Didefenisikan siklus Cn adalah graf dengan V(Cn) = V(Pn) dan E(Cn) = E(Pn)+v1vn. Suatu graf disebut graf terhubung apabila setiap dua titik pada graf tersebut termuat pada suatu lintasan. Selanjutnya, graf terhubung yang tidak memuat siklus disebut graf pohon. Graf pohon dengan n titik disebut pohon berorde n dan dinotasikan Tn. Apabila setiap dua titik pada suatu graf adalah bertetangga, maka graf tersebut disebut graf lengkap. Graf lengkap dengan n titik dinotasikan Kn. Dua graf G1 dan G2 disebut isomorf jika terdapat pemetaan dari V(G1) ke V(G2) sedemikian sehingga jika (v) (w)E(G2), maka vwE(G1). Jika tidak demikian, maka G1 dan G2

dikatakan tidak isomorf. Suatu hal yang menarik adalah banyaknya pohon perentang dari suatu graf lengkap

Kn. Kombinasi pelenyapan sisi-sisi pada graf lengkap menghasilkan banyak pohon perentang yang berbeda satu dengan lainnya. Dalam makalah ini, akan diperlihatkan bahwa satu pohon perentang dari graf lengkap berorde p berkorespondensi satu-satu dengan suatu pohon berlabel berorde p, sehingga banyaknya pohon berlabel berbeda orde p sama dengan banyaknya pohon perentang dari graf lengkap berorde p.

Dalam artikel SIAM Review volume 9 pada tahun 1967, Harary, F., menuliskan teorema Caylay dan buktinya. Teorema tersebut dapat dijadikan formula untuk menghitung banyaknya pohon berlabel yang berbeda. Chartrand dan Lesniak dalam buku Graphs & Digraphs (1996), menuliskan suatu teorema yang dapat digunakan untuk menghitung banyaknya pohon perentang berbeda dari suatu graf berlabel. Teorema tersebut dikenal dengan nama Teorema Matriks Pohon.

2. Matriks Graf

Pada graf dikenal dua macam matriks yakni matrik ketetanggaan dan matriks keterkaitan. Matriks ketetanggaan menyatakan kaitan antara titik dengan titik, sedangkan matriks keterkaitan menyatakan kaitan antara titik dengan sisi.

Definisi 2.1. Matriks KetetanggaanMatriks keteangaan A = (aij) dari suatu graf berlabel G dengan n titik adalah matriks berukuran nxn, dengan

a i , j={1 ; jika v i bertetangga dengan v j ,0 ; untuk hal lain.

Definisi 2.2 Matriks KeterkaitanMatriks keteangaan B = (bij) dari suatu graf berlabel G dengan m titik dan n sisi adalah matriks berukuran mxn, dengan

b i , j={1 ; jika v i te rkait dengan x j ,0 ; untuk hal lain.

Setiap sisi pada suatu graf adalah penghubung dua titik. Itulah sebabnya, setiap kolom pada matriks keterkaitan selalu terdapat dua angka satu. Berikut ini adalah sifat graf G dan matriks keterkaitan graf G apabila salah satu dari dua angka satu pada matriks kerterkaitan G diubah menjadi -1.

Teorema 2.1 Misalkan G adalah graf berlabel dengan matriks keterkaitan B. Matriks Emxm adalah matriks yang diperoleh dari B dengan mengganti salah satu dari dua angka 1 pada setiap kolomnya dengan -1. Jika G memiliki m titik dan m sisi serta memuat siklus, maka det(Emxm)=0.

Teprema 2.2

Misalkan G adalah graf berlabel yang memiliki N=M+1 titik dan M sisi. Graf G merupakan graf pohon jika hanya jika nilai det(EMxM) yang diperoleh dari matriks ENxM

dengan menghilangkan baris ke M+1 adalah 1 atau -1.

3. Pembahasan

Sebagaimana telah diuraikan pada pendahuluan bahwa Teorema Cayley dapat digunakan untuk menghitung banyaknya pohon berlabel dengan p titik yang tidak isomorf, sedangkan Teorema Mtriks Pohon dapat digunakan untuk menghitung banyaknya pohon perentang dari suatu graf terhubung berlabel. Berikut ini akan dikaji kaitan antara Teorema Cayley dengan Teorema Matriks Pohon.

Teorema 3.1 Teorema Matriks Pohon

Misalkan G adalah graf berlabel dengan matriks ketetanggaan A. M adalah matriks yang diperoleh dari –A dengan mengganti unsur diagonal ke-i dengan derajat vi. Nilai semua kofaktor dari matriks M adalah sama dan sama dengan banyaknya pohon perentang dari graf G.”

Bukti:

1. Kita akan memulai pembuktian ini dengan membuat matriks baru E=(eij) dari G, yang diperoleh dari matriks keterkaitan B dengan mengganti salah satu angka 1 pada setiap kolomnya dengan -1. Elemen dari baris ke-i dan kolom ke-j dari EET adalah (e11, e12,

…., eiq) (ej1ej2ejq )= eilejl + ei2ej2 + …. + eiqejq, yang jumlahnya sama dengan derajat vi jika vi

= vj, -1 jika vi bertetangga dengan vj, dan 0 untuk hal yang lain, sehingga EET = M.2. Pandanglah suatu submatriks dari E yang memuat n-1 kolom. Submmatriks berorde n

×(n-1) ini bersesuaian dengan suatu subgraf perentang H dari graf terhubung G yang memiliki n-1 sisi. Apabila sembarang baris dari submatriks tersebut dilenyapkan, misalnya baris ke-k, maka diperoleh suatu matriks bujursangkar F yang berode (n-1)× (n-1). Jika subgraf perentang H tidak isomorf dengan suatu pohon, berarti subgraf H memiliki siklus , sebab H memiliki n titk dan n-1 sisi. Menurut Teorema 2.1, |detF|= 0. Jika subgraf perentang H merupakan pohon, menurut Teorema 2.2, |det FT|= 1.

3. Untuk mengakhiri pembuktian Teorema Matriks Pohon ini, kita akan menggunakan Teorema Binet - Cauchy . Teorema Binet-Cauchy mengatakan bahwa “Jika A dan B adalah dua matriks yang berode r×m dan m×r, misalkan ∆ adalah matriks diagonal m×m dengan entri ei untuk baris ke i kolom ke i. Untuk setiap subset S berukuran r yang termuat dalam {1, 2, …, m}, terdapat As dan Bs yang masing-masing merupakan submatriks dari A dan B yang berukuran r×r yang terdiri atas kolom-kolom matriks A dan baris-baris matriks B, indeksnya dinyatakan oleh elemen-elemen S. Maka:

det(A∆B)= ∑s

det (As) det (Bs) ∏ iϵ S ei

Untuk ∆=I , maka det(AIB)= det(AB)=∑ det (As)det (Bs). Jika r m maka determinan pada teorema ini adalah determinan perkalian dua matriks bujursangkar.”

Suatu graf terhubung dengan titik v1, v2, …, v3, …, vm, dan sisi x1, x2, …, xn ; m=n. Sehingga matriks E dari graf tersebut adalah berode m×n. Dari matriks EM×N, kita membuat submatriks E1 yang berode m×(m-1). Jika salah satu baris dari E1

dilenyapkan, diperoleh matriks bujur sangkar F yang berode (m-1)×(m-1). Jika salah satu baris dari E1 dilenyapkan, diperoleh matriks bujursangkar F yang berode (m-1)×(m-1).

Untuk Teorema Binet-Chaucy: AS = F, sedangkan BS = FT. Dengan mengingat bahwa penghilangan salah satu baris dan kolom pada matriks M adalah bersesuaian dengan FFT. Berarti sebarang kofaktor dari M sama dengan det(FFT).

Menurut Binet-Cauchy: det(FFT)= det(F). det(FT). Hal ini menunjukkan bahwa jumlah hasil perkalian dari semua determinan utama F dan FT sama dengan nilai faktor elemen utama dari M sedang F bersesuaian dengan pohon perentang dari G, jika |det F| = 1. Dengan demikian, jumlah hasil perkalian dari semua determinan utama F dan FT adalah jumlah beberapa angka 1 yang menyatakan jumlah pohon perentang dari graf G. Jadi terbukti bahwa banyaknya pohon perentang dari G sama dengan nilai sebarang kofaktor dari M.

Contoh 3.1Kita akan menghitung banyaknya pohon perentang dari graf G pada Gambar 3.1 dengan menggunakan teorema Matriks Pohon. Pertama-tama yang akan dilakukan adalah menentukan matriks ketetanggaan A untuk graf G. Selanjutnya, menentukan matriks M dengan cara memberikan tanda mines (-) pada setiap elemn-elemen matriks ketetanggaan A dan mengganti angka nol pada kolom diagonal ke-i dengan derajat titik vi.

v4

v2

v1

x1

x2

x4

v3

x3

G:

Gambar 3.1 Graf G

Berikut adalah matriks ketetanggaan A dari graf G.

v1 v2 v3 v4 x1 x2 x3 x4

A =

v1

v2

v3

v4

[0 1 0 01 0 1 100

11

0 11 0

] B =

v1

v2

v3

v4

[1 0 0 01 1 0 100

10

1 01 1

]

Matriks M yang diperoleh dari –A dengan mengganti unsur diagonal ke-i dengan derajat vi adalah

v1 v2 v3 v4

M =

v1

v2

v3

v4

[ 1 −1 0 0−1 3 −1 −100

−1−1

2 −1−1 2

] Menurut Teorema 3.1, bahwa semua kofaktor dari matriks M adalah sama, yang nilainya sama dengan banyaknya pohonp erentang dari G. Berikut ini adaalah salah satu kofaktor matriks M.

1 0 0Kofator dari elemen 2,2, pada matriks M adalah 0 2 -1 = 3

0 -1 2

Jadi banyaknya pohon perentang dari graf G adalah 3.

Secara geometri ketiga pohon perentang dari graf G tersebut diperoleh dengan menghilangkan sisi x2, x3, dan x4. Bentuk ketiga pohon perentang itu adalah sebagai berikut.

T1:

v4

v1

x1x2

x4 v2

v3

v4

v1

x1x2

x3 v2

v3T3:

v4

v1

x1

x3

x4 v2

v3T2:

G2: G3:

1

2 3

4 1

2 3

4

G1:

Gambar 3.3

Gambar.3.2

Selanjutnya, kita akan membahas masalah pohon berlabel yang berbeda (tidak isomorf). Sebagai contoh pohon berlabel yang memiliki 4 titik, dengan label berturut-turut v1, v2, v3, dan v4 seperti pada Gambar 3.3 berikut.

Keterangan. Titik 3 dan titik 4 pada graf G1 bertetangga, sedangkan titik 3 dan titik 4 pada graf G2 tidak bertetangga. Jadi G1 dan G2 adalah dua graf berlabel berorde 4 yang berbeda (tidak isomorf). Demikian pula untuk graf G1 dan graf G3 juga berbeda karena titik 2 dan titik 3 pada graf G1 bertetangga, sedangkan pada graf G3 kedua titik tersebut tidak bertetangga. Hal serupa juga terjadi pada graf G3

dan graf G2. Titik 3 dan titik 4 pada graf G2 tidak bertetangga, sedangkan pada graf G3 kedua titik tersebut bertetangga.

Pembahasan berikut adalah mengenai kaitan antara pohon berlabel dengan pohon perentang dari suatu graf lengkap. Diberikan graf lengkap berorde 4 dengan label titik 1, 2, 3, dan 4, seperti pada Gambar 3.4.

1

2 3

4

2 3

K4 :

1 4Gambar 3.4

Apabila sisi 14, 13, dan 24 dilenyapkan diperoleh subpohon perentang yang serupa dengan pohon berlabel G1. Dan apabila sisi 13, 24, dan 34 dilenyapkan diperoleh subpohon perentang yang sama G2. Demikian juga apabila kombinasi sisi-sisi lain dilenyapkan, akan diperoleh suatu subpohon perentang yang berkorespondensi atau sama dengan suatu pohon berlabel dengan 4 titik. Jadi setiap subpohon perentang dari graf lengkap berorde p berkorespondensi satu-satu dengan suatu pohon berlabel berorde p.

Teorema 3.2 . Teorema Caylay

Banyaknya pohon berlabel yang berbeda dengan p titik simpul adalah pp-2.

Bukti.Di atas telah dijelaskan bahwa setiap pohon perentang dari suatu graf lengkap berorde p berkorespondensi satu-satu dengan suatu pohon berloabel berorde p. Karena itu teorema Caylay (Teorema 3.2) dapat dibuktikan dengan menggunakan Teorema Matriks Pohon yakni graf G adalah graf lengkap atau G = Kp..

Matriks ketetanggaan graf lengkap Kp adalah graf berorde p x p yang semua elemen-elemnnya 1 kecuali elemen diagonal ke-i yang bernilai 0, seperti berikut.

Apxp= [0 1 1 … 11 0 1 … 11⋮1

1⋮1

0⋮1

………

1⋮0]

Selanjutnya, dibentuk matriks M dari martiks –A yang elemen diagonal ke-i diganti dengan derajat titik ke-i atau vi, yakni seperti berikut:

Mpxp= [p−1 −1 −1 … −1−1 p−1 p−1 … −1−1⋮

−1

−1⋮

−1

p−1⋮

−1

………

−1⋮

p−1]

Kofaktor sembarang elemen-elemen dari matriks M adalah determinan matriks berorde p-1 x p-1. Misalkan kofaktor elemen 1.1, yaitu determinan matriks berprde p-1 x p-1 yang semua elemen-elemen diagonalnya adalah p-1 dan lainnya adalah -1. Dengan menggunakan salah satu metode dalam mencari determinan, sebutlah itu metode Gauss,

maka diperoleh matriks segitiga bawah atau segitiga atas yang elemen-elemen diagonalnya adalah p, kecuali elemen baris pertama adalah 1, yang berarti elemen diagonal pertama adalah 1. Dengan demikian, banyaknya elemen diagonal yang bernilai p adalah p-2, sehingga diperoleh nilai determinan sebanyak pp-2.

4. Daftar Pustaka

1. Chartrand,G. Dan Lesniak, L., Graphs & Digraphs, Chapman & Hall/CRC, Third Edition (1996) 64-67.

2. Harary, F., Graph and matrices, SIAM Review 9 (1967) 83-90.