3 Desy Norma - SPECTRUM DETOUR GRAF n-PARTISI KOMPLIT
SPECTRUM DETOUR GRAF n-PARTISI KOMPLIT
Desy Norma Puspita Dewi
Jurusan Matematika UIN Maulana Malik Ibrahim Malang
e-mail:phyta_23@yahoo.co.id
ABSTRAK
Matriks detour dari graf G adalah matriks yang elemen ke-(i,j) merupakan panjang lintasan
terpanjang antara titik �� ke titik �� di G. Himpunan nilai eigen matriks detour dari graf terhubung
langsung G adalah spectrum detour. Spectrum detour dari graf G biasanya dinotasikan dengan ������
�.. Dalam artikel ini, hanya menentukan spectrum detour graf n-partisi komplit
��,���,���,…,����, dan graf 3-
partisi komplit
��,�,��. Dalam menentukan spectrum detour graf tersebut dengan cara menggambar pola
grafnya, mencari matriks detournya, setelah itu dicari nilai eigen dan vektor eigen dari matriks tersebut,
sehingga diperoleh pola (konjektur) spectrum detour, kemudian merumuskan konjektur sebagai teorema
yang dilengkapi dengan bukti-bukti.
Kata kunci: Graf n-Partisi Komplit, Matriks Detour, dan Spectrum,
ABSTRACT
The detour matrices of a graph is for its (i,j) entry the length of the longest path between vertices �� to �� of G. Set of detour matrices eigenvalues of a connected graph G are detour spectrum. Detour
spectrum of G, denoted by ������
�. In this article, only determination of detour spectrum of complete n-
partition graph
��,���,���,…,����, and complete 3-partition graph
��,�,��. Determination of spectrum
detour graph are picturing model graph, then finding detour matrices, after that finded eigenvalues and
eigenvectors from that matrices, with the result that detour spectrum obtained model of detour spectrum,
end then formulate the model as theorem with its prove.
Keywords: Complete n- Partitions Graph, Detour Matrices, and Spectrum
PENDAHULUAN
Graf G adalah pasangan (V(G),E(G)) dengan
V(G) adalah himpunan tidak kosong dan
berhingga dari objek-objek yang disebut titik
(vertex), dan E(G) adalah himpunan (mungkin
kosong) pasangan tak berurutan dari titik-titik
berbeda di V(G) yang disebut sisi (edge).
Misalkan terdapat suatu graf G, dari suatu
graf tersebut dibentuk matriks adjacency atau
matriks keterhubungan. Matriks adjacency
merupakan matriks simetri. Matriks adjacency
dapat dirubah menjadi matriks detour, yang
unsur-unsur ke--(i,j) merupakan panjang lintas-
an terpanjang antara titik i dan j. Setelah
dibentuk menjadi matriks detour, maka dapat
dicari nilai eigen dan vektor eigen dari matriks
tersebut.
Biasanya spectrum graf dibentuk dari nilai
eigen dari matriks terhubung langsung. Dalam
pengertian, nilai eigen dari graf G dinotasikan
dengan �� , i = 1,2,…,n dan spectrum ditulis
dengan spec(G). Matriks detour didefinisikan
DD=DD(G) dari G sehingga unsur ke (i,j) adalah
panjang lintasan terpanjang antara titik i dan j.
Nilai eigen dari DD(G) disebut DD-nilai eigen dari
G dan membentuk DD-spectrum dari G,
dinotasikan dengan spec�� G�. Karena matriks
detour simetris, semua nilai eigen µ , i = 1,2,…,n
adalah real dan dapat diberi label µ� ! µ� ! " !µ#. Jika µ $ ! µ % ! " ! µ & adalah nilai eigen
dari matriks detour, maka DD-spectrum dapat
ditulis sebagai ������
� ' (µ $)� µ %)� …… µ &)*+
di mana m- menyatakan banyaknya basis untuk
ruang vektor eigen m . dan m1 / m2 / " / m� 'n. (Ayyaswamy dan Balachandran, 2010:250).
KAJIAN TEORI
1. Graf
Definisi 1
Graf G adalah pasangan himpunan (V,E)
dengan V adalah himpunan tidak kosong
dan berhingga dari obyek-obyek yang
disebut sebagai titik dan E adalah
himpunan (mungkin kosong) pasangan tak
berurutan dari titik-titik berbeda di G yang
disebut sebagai sisi (Chartrand dan
Lesniak, 1986:4).
Desy Norma Puspita Dewi
14 Volume 2 No. 1 November 2011
Sehingga jika
' 1
�, 2
��, maka 1
� ' 3�1, �2, … , ��4 dan 2
� ' 3�1, �2, … ,��4, dimana �� 5 1
�, 6 ' 1,2, … , 9 disebut
titik (vertex) dan �� 5 2
�, : ' 1,2, … , )
disebut sisi (edge).
2. Adjacent dan Incident
Sisi � ' ;� dikatakan menghubungkan
titik ; dan �. Jika � ' ;� adalah sisi di graf
,
maka ; dan � disebut terhubung langsung
(adjacent). � dan � serta ; dan � disebut
terkait langsung (incident). Titik ; dan �
disebut ujung dari �. Dua sisi berbeda �1 dan �2 disebut terhubung langsung jika terkait
langsung pada titik yang sama. Untuk
selanjutnya sisi � ' ;, �� ditulis � ' ;�
(Abdussakir, dkk, 2009:6).
3. Graf Komplit
Definisi 2
Graf komplit (complete graph) adalah graf
dengan dua titik yang berbeda saling
terhubung langsung (adjacent). Graf
komplit dengan 9 titik dinyatakan dengan �� (Chartrand dan Lesniak, 1986:9).
Definisi 3
Graf G dikatakan partisi n-komplit jika G
adalah graf partisi-n dengan himpunan
partisi 11, 12, … , 1� sehingga jika ; < 1�
dan � < 1�, 6 < :, maka ;� < 2
�. Maka
graf ini dinotasikan dengan �=1,=2,…,=>
(Abdussakir, dkk. 2009:23).
4. Graf Terhubung
Definisi 4
Misalkan
graf. Misalkan ; dan � adalah
titik pada
. Jalan (trail) ;� pada
yang
dinotasikan ? adalah barisan berhingga
yang berganti ?: ; ' �0, �1, �1, �2, �2, … ,��, �� ' � antara titik dan sisi yang diawali
dan diakhiri dengan titik dengan �� ' ��A1�� adalah sisi di
untuk 6 ' 1,2, … , 9. �0 disebut titik awal dan ��
disebut titik akhir. Titik �0, �1, �2, … , ��
disebut titik internal, dan 9 menyatakan
panjang dari ?. Jika �0 < ��, maka W
disebut jalan terbuka. Jika �0 ' �� maka W
disebut jalan tertutup. Jalan yang tidak
mempunyai sisi disebut jalan trivial
(Abdussakir, dkk. 2009:49).
5. Nilai Eigen dan Vector Eigen
Definisi 5
Misalkan A sebuah matrik n × n. Bilangan �
disebut nilai eigen (eigenvalue) dari A jika
terdapat vektor tidak nol � 5 B�
sedemikian sehingga Ax = �x . Kemudian
vektor x disebut vektor eigen (eigenvector)
dari A yang berpasangan ke nilai eigen �
(Jain & Gunawardena, 2004:151).
6. Spectrum Graf
Misalkan terdapat suatu graf G, dari
suatu graf tersebut dibentuk matriks
adjacency atau matriks keterhubungan.
Matriks adjacency merupakan matriks simetri.
Matriks adjacency dapat dirubah menjadi
matriks detour, yang unsur-unsur ke-(i,j)
merupakan panjang lintasan terpanjang
antara titik i dan j. Setelah dibentuk menjadi
matriks detour, maka dapat dicari nilai eigen
dan vektor eigen dari matriks tersebut.
Misalkan G graf berorder p dan A
matriks keterhubungan dari graf G. Suatu
vektor tak nol x disebut vektor eigen (eigen
vector) dari A jika CD adalah suatu kelipatan
skalar dari x, yakni CD ' �D, untuk sebarang
skalar �. Skalar � disebut nilai eigen (eigen
value) dari A, dan x disebut sebagai vektor
eigen dari A yang bersesuaian dengan �.
Untuk menentukan nilai eigen dari matriks A,
persamaan CD ' �ED�D ditulis kembali dalam
bentuk C F �E�D ' 0,
dengan I matriks identitas berordo
p. Persamaan ini akan mempunyai solusi tak
nol jika dan hanya jika G�H C F �E�D ' 0
Persamaan G�H C F �E� ' 0 akan menghasil-
kan persamaan polinomial dalam variabel �
dan disebut persamaan karakteristik dari
matriks A. Skalar-skalar � yang memenuhi
persamaan karakteristik ini tidak lain adalah
nilai-nilai eigen dari matriks A.
Misalkan �1, �2, … , �� adalah nilai eigen
berbeda dari A, dengan �1, �2, … , ��, dan
misalkan )�1, )�2, … , )�� adalah banyaknya
basis untuk ruang vektor eigen masing-
masing I� , maka matriks berordo 2 J 9� yang
memuat �1, �2, … , �� pada baris pertama dan )�1, )�2, … , )�� pada baris kedua disebut
spectrum graf G, dan dinotasikan dengan ����
�. Jadi spectrum graf G dapat ditulis
dengan ����
� ' ( ��)�� ��)�� …… ��)��+
(Abdussakir, dkk, 2009:82-83).
7. Graf dalam Matriks Detour
Matriks detour didefinisikan DD =
DD(G) dari G sehingga unsur atau entry (i,j)
adalah panjang lintasan terpanjang antara
titik i dan j. Nilai eigen dari DD(G) disebut DD-
nilai eigen dari G dan membentuk DD-
spectrum dari G, yang dinotasikan dengan ������
�. Selama matriks detour simetris,
semua nilai eigen K� , i = 1, 2, …, n adalah real
dan dapat diberi label K1 ! K2 ! " ! K�.
Jika K�1 ! K�2 ! " ! K�L adalah nilai eigen
dari matriks detour, maka DD-spectrum dapat
ditulis sebagai
Spectrum Detour Graf n-Partisi Komplit
Jurnal CAUCHY – ISSN: 2086-0382 15
������
� ' (µ $)� µ %)� …… µ &)*+
di mana )� menunjukkan banyaknya basis
untuk ruang vektor eigen dalam K�M dan
tentunya )1 / )2 / … / )* ' 9.
(Ayyaswamy dan Balachandran, 2010)
PEMBAHASAN
1. Spectrum Detour dari Graf n-Partisi
Komplit
��,���,���,…,����
Pembahasan spectrum detour dari graf
n- partisi komplit
��,���,���,…,����, dibatasi
pada 9 ! 2, ) ! 1 dan 9, ) 5 N.
1.1 Spectrum Detour Graf 3-Partisi Komplit OP,Q,R
������
��,S,T� ' U64 F81 8 Y
1.2 Spectrum Detour Graf 4-Partisi Komplit OP,Q,R,Z
������
��,S,T,[� ' U169 F131 13 Y
1.3 Spectrum Detour Graf 5-Partisi Komplit OP,Q,R,Z,^
������
��,S,T,[� ' U361 F191 19 Y
1.4 Spectrum Detour Graf 6-Partisi Komplit OP,Q,R,Z,^,_
������
��,S,T,[� ' U676 F261 26 Y
Teorema 1:
Jika
��,��1,��2,…���� adalah graf n-partisi
komplit dengan 9 ! 2, ) ! 1; 9, ) 5 N dan � ' 9 / 9 / 1� / 9 / 2� / " / 9 / )�, maka: ������
��,��1,��2,…����' ( � F 1�2 F � F 1�
1 � F 1� +
dimana ������
��,��1,��2,…���� adalah spectrum
detour dari graf n-partisi komplit dan 9 bilangan
asli.
Bukti:
Misalkan bb
��,��1,��2,…���� adalah matrik
detour adjacent dari
��,��1,��2,…����, maka bb
��,��1,��2,…����
'
cd
dd
e 0 � F 1 � F 1 … � F 1� F 1 0 � F 1 … � F 1� F 1 � F 1 0 … � F 1f f f g f� F 1 � F 1 � F 1 … 0 hi
ii
j
Dari matriks detour adjacent di atas, maka akan
dicari nilai eigennya dengan menentukan
det k�E F bb
��,��1,��2,…����l ' 0
mmλ cdd
de1 0 0 … 00 1 0 … 00 0 1 … 0f f f g f0 0 0 … 1hi
iij F
cd
dd
e 0 � F 1 � F 1 … � F 1� F 1 0 � F 1 … � F 1� F 1 � F 1 0 … � F 1f f f g f� F 1 � F 1 � F 1 … 0 hi
ii
j
mm ' 0
mm
λ F � F 1� F � F 1� … F � F 1�F � F 1� λ F � F 1� … F � F 1�F � F 1� F � F 1� λ … F � F 1�f f f g fF � F 1� F � F 1� F � F 1� … λ m
m ' 0
Kita kalikan matriks di atas dengan 1A =A1�,
sehingga diperoleh
m
m
m
λF � F 1� 1 1 … 1
1 λF � F 1� 1 … 1
1 1 λF � F 1� … 1f f f g f1 1 1 … λF � F 1�m
m
m
' 0
Dimisalkan �p ' k q=A1l, maka
mm
Fλp 1 1 … 11 Fλp 1 … 11 1 Fλp … 1f f f g f1 1 1 … Fλp
mm ' 0
Melalui operasi basis elementer, matriks
det k�E F bb
��,��1,��2,…����l direduksi menja-
di matriks segitiga atas, sehingga diperoleh
m
m
mFλ
p 1 1 … 10 Akrs%A�lrs 1 … 10 0 Akrs%A�l
rsA��rsA� … 1f f f g f0 0 1 … Akrs%A tA�� tA��
rsA tA���%lrsA tA�� tA�� m
m
m
' 0
Sehingga det k�E F bb
��,��1,��2,…����l tidak
lain adalah hasil perkalian diagonal matriks
segitiga atas tersebut, sehingga diperoleh det kλI F DD
K#,#��,#��,…#�z�l'
λp F p F 1�� λp / 1�tA�
Karena det kλE F bb
��,��1,��2,…����l ' 0, maka
λp F p F 1�� λp / 1�tA� ' 0
Sehingga didapat nilai eigen �p ' � F 1� atau λp ' F1, karena λp ' rA tA�� maka nilai eigennya
diperoleh � ' � F 1� atau � ' F1
r tA�� ' p F 1� r tA�� ' F1 λ ' p F 1�� λ ' F p F 1�
Sedangkan untuk vektor eigennya, yaitu CD ' �D ' 0
Desy Norma Puspita Dewi
16 Volume 2 No. 1 November 2011
( )
'
1
'
2
'
1
'
01 1 1
01 1 1
01 1 1
01 1 1
p
p
x
x
x
x
λ
λ
λ
λ
−
−
−
=−
−
⋯
⋯
⋯
⋮⋮⋮ ⋮ ⋮ ⋱ ⋮
⋯
Kemudian, akan dibuktikan bahwa untuk λ ' n F 1�� akan didapatkan banyaknya basis
vektor eigen adalah 1.
Untuk λ ' F p F 1� akan didapatkan
( )
( )
( )
( )
( )
( )
( )
( )
( )
2
2
1
2
2
1
2
1
1 1 1
1
1 0
1 1 1
1 0
01
1 1 1
1
0
1
1 1 1
1
p
p
p
p
xp
xp
xp
p
x
p
p
−
−
− −
−
− −
=−
− −
−
− −
⋯
⋯
⋯
⋮⋮
⋮ ⋮ ⋮ ⋱ ⋮
⋯
( )
( )
( )
( )
( )
1
2
1
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
p
p
xp
xp
xp
p x
−
− −
− −
− − =
− −
⋯
⋯
⋯
⋮ ⋮ ⋮ ⋱ ⋮ ⋮⋮
⋯
Dengan mereduksi matriks di atas menjadi
bentuk eselon tereduksi baris, aka didapatkan
( )
1
2
1
1 0 0 1 0
0 1 0 1 0
0 0 1 1 0
0 0 0 0 0
p
p
x
x
x
x
−
−
−
=−
⋯
⋯
⋯
⋮ ⋮ ⋮ ⋱ ⋮ ⋮⋮
⋯
Kemudian didapat D1 ' D=, D2 ' D=, … , D=A1 ' D=
Sehingga diperoleh D1 ' D2 ' " ' D=A1 ' D=.
Misal D= ' � maka vektor eigennya adalah
( )
1
2
1
1
1
1
1
1
p
p
x s
x s
S S
x s
sx
−
= = =
⋮ ⋮ ⋮
Jadi didapatkan banyaknya basis ruang eigen
untuk λ ' p F 1�� adalah 1.
Untuk λ ' F p F 1� akan didapatkan
( )
( )
( )
( )
( )
( )
( )
( )
( )
1
2
1
1
1 1 1
1
1 0
1 1 1
1 0
01
1 1 1
1
0
1
1 1 1
1
p
p
p
p
xp
xp
xp
p
x
p
p
−
− −
− −
− − − − =− − − −
− −
− −
⋯
⋯
⋯
⋮⋮
⋮ ⋮ ⋮ ⋱ ⋮
⋯
( )
1
2
1
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
p
p
x
x
x
x
−
=
⋯
⋯
⋯
⋮ ⋮ ⋮ ⋱ ⋮ ⋮⋮
⋯
Dengan mereduksi matriks di atas menjadi
bentuk eselon tereduksi baris, maka didapatkan
( )
1
2
1
1 1 1 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
p
p
x
x
x
x
−
=
⋯
⋯
⋯
⋮ ⋮ ⋮ ⋱ ⋮ ⋮⋮
⋯
Kemudian didapat D1 / D2 / " / D =A1� / D= ' 0
Sehingga diperoleh D1 ' FD2 F " F D =A1� F D=.
Maka vektor eigennya adalah
( )
( )
( )
2 11
2
2 1
1
2
pp
p
p
p
p
x x xx
x x
S x
x
x x
−
−
−
− − −
= =
⋯
⋮
⋮
Jadi didapatkan banyaknya basis ruang eigen
untuk � ' F � F 1� adalah � F 1�.
Jadi terbukti bahwa ������
��,��1,��2,…���� ' ( � F 1�2 F � F 1�
1 � F 1� +.
2. Spectrum Detour dari Graf 3-Partisi
Komplit 2,2,nK
Pembahasan spectrum detour dari graf
3- partisi komplit 2,2,nK
dibatasi pada 9 ! 5.
2.1 Spectrum Detour Graf 3-Partisi Komplit OP,P,Z
( )2,2,5 25 1029 25 1029 6 8
1 1 3 4
DDspec K
+ − − −
=
2.2 Spectrum Detour Graf 3-Partisi Komplit OP,P,^
( )2 ,2 ,6 29 129 7 29 1297 6 8
1 1 3 5
DDspec K
+ − − −
=
2.3 Spectrum Detour Graf 3-Partisi Komplit OP,P,_
( )2,2,7 33 1597 33 1597 6 8
1 1 3 6
DDspec K
+ − − −
=
2.4 Spectrum Detour Graf 3-Partisi Komplit OP,P,{
( )2,2,8 37 1929 33 1929 6 8
1 1 3 7
DDspec K
+ − − −
=
2.5 Spectrum Detour Graf 3-Partisi Komplit OP,P,|
( )2,2,9 41 2293 41 2293 6 8
1 1 3 8
DDspec K
+ − − −
=
2.6 Spectrum Detour Graf 3-Partisi Komplit OP,P,}~
( )2,2,10 45 2689 45 2689 6 8
1 1 3 9
DDspec K
+ − − −
=
Spectrum Detour Graf n-Partisi Komplit
Jurnal CAUCHY – ISSN: 2086-0382 17
Berdasarkan hasil spectrum detour dari
graf 3-partisi komplit ��,�,�� di atas, dapat
diperoleh dugaan sementara bahwa bentuk
umum dari spectrum detour adalah:
( ) ( ) ( )
2 2
2,2,
(2 2 2 1) (2 2 2 1)16 220 793 16 220 793 6 8
1 1 3 1
DD n
n n n n
spec K
n
n n n n+ + + + + + + − + + + + − −=
−
Dengan 5n ≥ dan n adalah bilangan asli.
PENUTUP
Kesimpulan
Berdasarkan pembahasan mengenai
spectrum detour dari graf n-partisi komplit,
diperoleh kesimpulan: (a). Untuk graf n-partisi
komplit ��,���,���,…,���� dengan 9 ! 2, ) !1; 9, ) 5 N dan � ' 9 / 9 / 1� / 9 / 2� / " / 9 / )�, maka
( ) ( ) ( )
( )
2
, 1 , 2 ,
1 1
1 1
D D n n n n m
p p
s p e c K
p
+ + … +
− − −
=
− ,
(b). Untuk graf 3-partisi komplit ��,�,�� dengan 9 ! 2, 9 5 N
( ) ( ) ( )
2 2
2,2,
(2 2 2 1) (2 2 2 1)16 220 793 16 220 793 6 8
1 1 3 1
DD n
n n n n
spec K
n
n n n n+ + + + + + + − + + + + − −=
−
Saran
Pada artikel ini, penulis hanya
memfokuskan pada spectrum detour yang
digambarkan oleh dua bentuk graf n-partisi
komplit yaitu graf n-partisi komplit ��,���,���,…,���� dan graf 3-partisi komplit
��,�,��. Pada bentuk graf 3-partisi komplit ��,�,��
masih merupakan konjektur, sehingga
perlu diselidiki lebih lanjut. Karena masih
banyaknya bentuk dari graf ini, maka untuk
penulisan skripsi selanjutnya diteliti pada graf
lain.
DAFTAR PUSTAKA
[1] Abdussakir, dkk. 2009. Teory Graf : Topik
Dasar untuk Tugas Akhir/Skripsi. Malang:
UIN-Malang Press.
[2] Chartrand, G and Lesniak, L. 1986. Graph
and Digraph: Second Edition California: A
Division Wadsworth
[3] Ayyaswamy, S.K. dan Balachandran, S.
(2010). “On Detour Spectra of Some Graphs”.
World Academy of Science, Enggineering and
Technology.
(www.waset.org/journals/waset/v67/v67-
88.pdf. diakses 2 Februari 2011).
[4] Jain, S. K. 2004. Linear Algebra; An
Interactive Approach. Australia: Thomson
Learning.