PROSIDING
ISBN : 978‐979‐16353‐3‐2
A.1 SPECTRUM PADA GRAF STAR (
) DAN GRAF BIPARTISI KOMPLIT (
DENGAN
)
Oleh Imam Fahcruddin Mahasiswa Jurusan Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri (UIN) Maulana Malik Ibrahim Malang Jln. Gajayana 50 Malang ABSTRAK Misalkan , , …, adalah nilai – nilai eigen berbeda dari matrik adjacent graf G dan adalah banyaknya basis untuk ruang vektor eigen masing – masing , maka matrik berordo (2 x n) yang memuat , , …, pada pada baris kedua disebut spectrum graf G baris pertama dan dan dinotasikan dengan Spec . Pada makalah ini akan dibahas spectrum graf star ( ) dan graf bipartisi komplit ( ) dengan m,n bilangan asli. KATA KUNCI: spectrum, graf bipartisi komplit, graf star, nilai eigen, vektor eigen. Graf G adalah pasangan (V, E) dengan V adalah himpunan tidak kosong dan berhingga dari objek‐objek yang disebut titik, dan E adalah himpunan (mungkin kosong) pasangan takberurutan dari titik‐titik berbeda di V yang disebut sisi. Banyaknya unsur di V disebut order dari G dan dilambangkan dengan p(G), dan banyaknya unsur di E disebut ukuran dari G dan dilambangkan dengan q(G). Jika yang dibicarakan hanya satu graf, maka order dan ukuran dari graf tersebut masing‐masing ditulis p dan q. [1]
Sisi e = (u, v) dikatakan menghubungkan titik u dan v. Jika e = (u, v) adalah sisi di
graf G, maka u dan v disebut terhubung langsung (adjacent), v dan e serta u dan e disebut terkait langsung (incident), dan u, v disebut ujung dari e. Derajat dari titik v di graf G, ditulis degG v, adalah banyaknya sisi di G yang terkait langsung dengan v. Titik yang berderajat satu disebut titik ujung. Untuk selanjutnya, sisi e = (u, v) akan ditulis e = uv.
Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
1
PROSIDING
ISBN : 978‐979‐16353‐3‐2
Graf bipartisi (bipartite graph) adalah graf yang himpunan titiknya dapat
dipisahkan menjadi dua himpunan tak kosong X dan Y sehingga masing‐masing sisi dari graf tersebut menghubungkan satu titik di X dan satu titik di Y; X dan Y disebut himpunan partisi. Graf bipartisi komplit (complete bipartite graph) adalah graf bipartisi dengan himpunan partisi X dan Y sehingga masing‐masing titik di X dihubungkan dengan masing‐masing titik di Y oleh tepat satu sisi. Jika |X| = m dan |Y| = n, maka graf bipartisi tersebut dinyatakan dengan K(m,n). Graf Star adalah graf bipartisi komplit yang berbentuk K(1,n) yang ditulis dengan Sn .[2] Misalkan A(G) adalah matrik n x n, A(G) dikatakan sebagai matrik adjacent dari graf G apabila elemennya terdiri dari aij = 1 jika vi dan vj adjacenct, 0 untuk yang lainya. [3,7] Berikut ini adalah beberapa contoh dari graf bipartisi komplit dan graf star beserta matrik adjacent dari graf tersebut.
v2
u1
v3
v1
v2
v3
v1
u1 u2 (a) K2.3 (d) S4
u1
v2
v3
u2
u3
(b) K3,3 (c) S3
Misalkan A adalah sebuah matriks adjacent dari graf G, maka suatu vektor tak nol x pada
disebut vektor eigen (eigen vektor) dari A jika Ax adalah suatu kelipatan
skalar dari x; yakni,
untuk skalar sebarang . Skalar disebut nilai eigen
(eigen value) dari A, dan x disebut sebagai vektor eigen dari A yang bersesuaian dengan . Untuk memperoleh nilai eigen dari sebuah matrik n x n, kita menuliskan kembali
dengan
Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
2
PROSIDING
.
ISBN : 978‐979‐16353‐3‐2
(1)
Agar menjadi nilai eigen, harus terdapat satu solusi taknol dari persamaan (1). Persamaan (1) akan memiliki solusi taknol jika dan hanya jika .
(2)
Persamaan (2) disebut persamaan karakteristik dari matrik A, skalar‐skalar yang memenuhi persamaan ini adalah nilai – nilai eigen dari A. [4,5]
Misalkan
,
, …,
adalah nilai – nilai eigen berbeda dari matrik adjacent
graf G dan
adalah banyaknya basis untuk ruang vektor eigen
masing – masing
, maka matrik berordo (2 x n) yang memuat
baris pertama dan
,
, …,
pada
pada baris kedua disebut spectrum graf G
dan dinotasikan dengan Spec
[6]. Jadi, spectrum graf G dapat ditulis
Spec
Pada makalah ini dibahas bentuk umum spectrum graf star ( ) dan graf bipartisi komplit (
) dengan
. Bentuk umum spectrum dinyatakan
sebagai teorema dan disertai buktinya. Dengan makalah ini, dapat diketahui pula penerapan konsep aljabar linier pada teori graf serta penemuan pola – pola tertentu khususnya spectrum suatu graf. PEMBAHASAN
Pembahasan bentuk umum spectrum dari graf bipartisi komplit (
graf star ( ) dengan
) dan
disajikan dalam teorema berikut beserta buktinya.
Teorema Misal adalah graf star dengan Spec
, maka spectrum adalah
Bukti Misalkan
adalah matrik adjacent dari graf star
Pertama akan ditentukan nilai eigen dari
, maka
, dengan persamaan
Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
3
PROSIDING
ISBN : 978‐979‐16353‐3‐2
Melalui operasi baris matrik
direduksi menjadi matrik segitiga atas
diperoleh, ⎛ −λ ⎜ ⎜ 0 ⎜ ⎜ ⎜ ⎜ 0 ⎜ ⎜ ⎜ 0 ⎜ ⎜ ⎜ ⎜ 0 ⎜ ⎜ ⎜ ⎜ M ⎜ ⎜ ⎜ ⎜⎜ 0 ⎝
1
1
1
1
(−1)(−λ )(λ 2 − 1)
1
1
1
λ2
λ λ 1 − − ( )( ) ( λ 2 − 2 )
λ
λ
0
(λ
0
2
)
(λ
−1
λ
)
−1
2
( −1)( −λ ) ( λ
0
(λ
2
−2
−3
2
)
)
λ
(λ
2
(λ
2
K K
)
K
)
K
−1
λ −2
( −1)( −λ ) ( λ
2
−4
)
0
0
K
M
M
K
0
O
0
0
0
K
0
(λ
2
−3
)
O
⎞ ⎟ ⎟ ⎟ λ ⎟ λ ⎟ ⎟ λ 2 −1 ⎟ ⎟ λ ⎟ ⎟ λ2 − 2 ⎟ ⎟ ⎟ M ⎟ ⎟ ⎟ λ ⎟ 2 λ − ( n − 2) ⎟ ⎟ ( −1)( −λ ) λ 2 − n ⎟ λ 2 − ( n − 1) ⎠⎟⎟ 1
1
(
)
(
)
(
(
)
(
)
)
tidak lain adalah hasil perkalian diagonal matrik segitiga atas tersebut. Jadi
Sehingga diperoleh nilai eigen
atau
.
Selanjutnya akan ditentukan basis untuk ruang vektor eigen yang bersesuain dengan . Untuk
diperoleh
dengan
Didapatkan persamaan ‐ persamaan,
… (i)
… (ii)
Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
4
PROSIDING
ISBN : 978‐979‐16353‐3‐2
Sehingga vektor eigennya adalah
Jadi basis pada matrik diatas adalah Untuk ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
n
, vektor eigennya diperoleh dengan ; 1
1
K K
1
n
0
1
0
M
M
n O O O
1
0
K
0
1 ⎞ ⎛ x1 ⎞ ⎛ 0 ⎞ ⎟⎜ ⎟ ⎜ ⎟ 0 ⎟ ⎜ x2 ⎟ ⎜ 0 ⎟ ⎟ M ⎟ ⎜ x3 ⎟ = ⎜ 0 ⎟ ⎜ ⎟ ⎜ ⎟ 0 ⎟⎜ M ⎟ ⎜ M ⎟ ⎟⎜ ⎟ ⎜ ⎟ n ⎟⎠ ⎝ xn ⎠ ⎝ 0 ⎠
Didapatkan persamaan ‐ persamaan, untuk k = 2, 3, …, n Sehingga vektor eigennya adalah
Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
5
PROSIDING
ISBN : 978‐979‐16353‐3‐2
dengan
Jadi basis pada matrik diatas adalah
.
Dengan cara yang sama dapat diperoleh Spec
. Jadi, terbukti bahwa
Berikut ini contoh spectrum dari graf dan dengan menggunakan teorema diatas. v7 v6 v5 v6 v8 v4 v5 v 7
v8
S7
v9
v3
v1
v1 v2
S9
Spec
v3
v10
v2
v4
Spec
Teorema Misal
adalah graf bipartisi komplit dengan
, maka spectrum
adalah Spec
Bukti Misalkan
adalah matrik adjacent dari graf bipartisi komplit
.
Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
6
PROSIDING
ISBN : 978‐979‐16353‐3‐2
dimana = 0 dengan i = 1, 2, 3, …, m dan j = 1, 2, 3, …, m = 1 dengan k = 1, 2, 3, …, n dan l = 1, 2, 3, …, n dengan persamaan Akan ditentukan nilai eigen Melalui operasi baris matrik diperoleh, ⎛ −λ ⎜ ⎜ 0 ⎜ 0 ⎜ ⎜ M ⎜ 0 ⎜ ⎜ ⎜ 0 ⎜ ⎜ ⎜ 0 ⎜ ⎜ ⎜ ⎜ 0 ⎜ ⎜ ⎜ M ⎜ ⎜ ⎜ ⎜ 0 ⎜ ⎝
0 −λ O M 0
K 0 K 0 −λ O M 0 O 0 K 0 −λ
0
0 0
0
K
0
.
direduksi menjadi matrik segitiga atas
1 1
1 1
1 1
1 M
1 M
1 M
K K K M
1
1
1
1
( −1)( λ ) ( λ 2 − m )
mλ
mλ
λ
λ
λ2
2
2
( −1)( λ ) ( λ 2 − 2m )
K
mλ λ −m
0
0
0
K
0
0
0
0
0
O
0
M
M
M
M
M
K
0
O
0
0
0
0
0
0
K
0
(λ
2
−m
)
(
2
K
)
( −1)( λ ) ( λ 2 − 3m )
(λ
2
− 2m
)
O
⎞ ⎟ ⎟ ⎟ 1 ⎟ M ⎟ ⎟ 1 ⎟ ⎟ mλ ⎟ 2 λ ⎟ ⎟ mλ ⎟ ⎟ λ2 − m ⎟ ⎟ ⎟ M ⎟ ⎟ mλ ⎟ λ 2 − m ( n − 2) ⎟ ⎟ ( −1)( λ ) λ 2 − mn ⎟⎟ λ 2 − m ( n − 1) ⎟⎠ 1 1
(
)
(
(
)
(
)
tidak lain adalah hasil perkalian diagonal matrik segitiga atas
tersebut. Sehingga diperoleh nilai eigen
atau
Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
.
7
)
PROSIDING
ISBN : 978‐979‐16353‐3‐2
Selanjutnya akan ditentukan basis untuk ruang vektor eigen yang bersesuain dengan . Untuk diperoleh dengan
Didapatkan persamaan ‐ persamaan, … (i) …(ii) Persamaan (i) dan (ii) dapat kita tulis dan
Sehingga vektor eigennya adalah
Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
8
PROSIDING
ISBN : 978‐979‐16353‐3‐2
Jadi basis pada matrik diatas adalah Misalkan
⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
, vektor eigennya diperoleh dengan ;
mn
0
K
0
1
1
1
K
0 M
mn K M O
0 M
1 M
1 M
1 M
K O
0
0
K
mn
1
1
1
K
1
1
K
1
mn
0
0
K
1
1
K
1
0
mn
0
K
1 M
1 M
K O
1 M
0 0
0 O
mn O O 0
1
1
K
1
0
L
0
0
1 ⎞ x ⎟⎛ 1 ⎞ ⎛0⎞ 1 ⎟⎜ x ⎟ ⎜0⎟ ⎟⎜ 2 ⎟ ⎜ ⎟ 1 ⎟ ⎜M ⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜ ⎟ 1 ⎟ ⎜ xm −1 ⎟ ⎜ 0 ⎟ ⎟ 0 ⎟ ⎜ xm ⎟ = ⎜ 0 ⎟ ⎟ ⎜ ⎟ ⎟⎜ y ⎜ ⎟ ⎜0⎟ 1 0 ⎟ ⎜ ⎟ M ⎟ ⎜0⎟ ⎟ ⎜ ⎟ M ⎟⎜ ⎜ yn −1 ⎟ ⎜M ⎟ ⎟ 0 ⎜ ⎟ ⎜ y ⎟⎟ ⎜ 0 ⎟ ⎝ ⎠ mn ⎟⎠ ⎝ n ⎠
Didapatkan persamaan ‐ persamaan pertama, Dapat ditulis dengan Persamaan – persamaan kedua, Dapat ditulis dengan Akhirnya didapatkan vektor eigennya adalah
Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
9
PROSIDING
ISBN : 978‐979‐16353‐3‐2
sehingga didapatkan
dan dengan cara yang sama dapat diperoleh
Berdasarkan pernyataan diatas, maka terbukti bahwa
Spec Kesimpulan
Berdasarkan pembahasan diatas dapat disimpulkan bahwa spectrum dari graf bipartisi komplit
dengan
adalah
Spec dan graf star
dengan
adalah
Spec
Disarankan kepada pembaca untuk menentukan spectrum graf lainya misalnya graf roda, graf kipas, dan graf buku. Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
10
PROSIDING
ISBN : 978‐979‐16353‐3‐2
DAFTAR PUSTAKA [1] Chartrand, G. & Lesniak, L. 1986. Graf and Digraf 2nd Edition. California: Wadsworth, Inc. (4) [2] Bondy, J.A. & Murty, U.S.R., 1976. Graf Theory with Applications. London: The Macmillan Press Ltd. (1‐4) [3] Evans, R, James. 1992. Optimization Algorithms for Networks and Graphs. New York: Marcel Dekker, INC. (28) [4] Anton, Howard. & Rorres, Chris. 2004. Aljabar Linier Elementer Versi Aplikasi Jilid 1. Jakarta: Erlangga. (384‐387) [5] Meyer, D, Carl. 2009. Matrix Analysis and Applied Linier Algebra. Siam Organization. (490‐492) [6] Biggs, Norman. 1974. Algebraic Graph Theory. London: Cambridge University Press. (9,50) [7] Harary, Frank. 1969. Graph Theory. Canada: Addison‐Wesley Publishing Company, Inc. (150)Theory. America: California State University at Fresno Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pendidikan Matematika FMIPA UNY, 5 Desember 2009
11
