Spektrum Graf

SPEKTRUM GRAF
( DEFENISI 2.2 dan 2.4, PREPOSISI 2.3)
Oleh:
MELDA YANTI (1520432016)
MERDIAN KHAIRAD (1520432017)
ROBI ALMI (15204320)
Dosen Pembimbing:
DR. LYRA YULIANTI
JURUSAN PASCASARJANA MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS ANDALAS PADANG
2016
Spektrum Graf
DEFENISI 2.2
Spektrum graf G adalah himpunan dari suatu nilai karakteristik dari A dan m
adalah multiplisitas dari
0 1 ... s 1
. Misalkan A(G) memiliki nilai-nilai eigen berbeda
(0 )
masing m
( s 1 )
(1 )
,m
dengan multiplisitas masing-
,,m
. Spektrum dari graf G, dinotasikan dengan Spec G, dapat dituliskan
dalam bentuk berikut ini.
0
1 ....
s 1
m 0 m 1 .... m s 1
Spec G =
Berikut ini diberikan contoh penentuan spektrum dari suatu graf segitiga K 3. Matriks
V3
V1
V2
Gambar 2.1: K 3
ketetanggaan dari K3 adalah
0 1 1
1 0 1
1 1 0
A(K3) = A =
det (A-
) = 0\
0 1 1 0 0

det 1 0 1 0 0 0
1 1 0 0 0
1
1
det 1 1 0
1
1
1
1 1
1
(3 1 1) ( ) 0
3 2 3 0
3 3 2 0
( 2)( 1) 2 0
Dengan demikian spectrum dari K3 adalah
2 1
1 2

Spec K 3
Biasanya, suatu nilai karakteristik dari matriks ketetanggaan A = A(G) disebut sebagai nilai karakteristik
dari graf G. Demikian juga dengan polinom karakteristik dari A(G) biasanya disebut sebagai polinom
karakteristik dari graf G yang dinotasikan dengan X(G;
Misalkan
).
V n
graf sederhana dengan
. Misalkan juga polinom karakteristik dari
x ; n c1n 1 c 2 n 2 ... c n
.
Preposisi 2.3
adalah
Proposisi 2.3. Koefisien-koefisien polinom karakteristik dari graf
memenuhi
c1 0
1.
c2
2.
adalah banyaknya sisi pada graf
c 2 E ( )
yakni
c3
3.
adalah dua kali banyaknya segitiga pada graf
Bukti. 1. Misalkan A() = An_n adalah matriks ketetanggan graf . Karena adalah graf
sederhana, maka semua entri diagonal utama pada matriks A() barnilai 0. Akibatnya,
semua submatriks utama dari A yang berukuran 1_1 berupa matriks nol sehingga julmlah
determinan semua matriks utama berukuran 1 _ 1 tersebut adalah 0. Oleh karena itu,
c1 = E1 (A) = 0.
2. Perhatikan bahwa submatriks 2 utama dari A yang berukuran 2_2 hanya akan berbentuk
400
00
3
5 atau
2
401
10
3
5. Misalkan submatriks utama
2
400
00
3
5 dan
2
401
10
3
5 pada A
masing-masing sebanyak p dan q buah. Diperoleh,

c2 = E2(A) = p
______
00
00
______
+q
______
01
10
______
= p:0 + q(1) = q:
Tetapi, submatriks
2
401
10
3
5 merupakan representasi dari pasangan titik yang bertetangga
yakni sebuah sisi pada graf . Dengan demikian, banyaknya sisi pada graf adalah
E() = q. Lebih jauh, diperoleh c2 = (q) = q = E():
3. Submatriks utama A yang berukuran 3_3 merupakan salah satu dari bentuk
2
6664
000
000
000
3
7775
,
2
6664
010
100
000
3
7775
,
2
6664
001
000
100
3
7775
,
2
6664
000
001
010
3
7775
,
2
6664
011
100
100
3
7775
,
2
6664
001
001
110
3
7775
,
2
6664
010
101
010
3
7775
atau
2
6664
011
101
110
3
7775
. Perhatikan bahwa
_________
011
101
110
_________
= 2 dan determinan dari submatriks utama
b2entuk lainnya bernilai nol. Misalkan submatriks utama ukuran 3 _ 3 yang berbentuk
6664
011
101
110
3
7775
ada sebanyak p buah sedangkan total banyak dari submatriks utama 3 _ 3
selain itu adalah q buah. Akibatnya, E3(A) = p(2) + q(0) = 2p. Tetapi, submatriks
utama
2
6664
011
101
110
3
7775
merupakan representasi dari 3 buah titik yang saling bertetangga
BAB 2. SPEKTRUM GRAF 21
yakni sebuh segitiga pada graf . Dengan demikian,
c3 = (E3) = 2p = 2 banyak segitiga pada graf :
Gambar 2.2: graf G
Contoh 2.4. Matriks ketetanggaan dari graf G adalah A = A(G) =
2
6666664
0101
1011
0101
1110
3
7777775
.
Adapun polinom karakteristik dari graf G merupakan polinom karakteristik dari matriks
A yakni _ (G; _) = _4 5_2 4_. Koe_sien dari _3 adalah 0, banyaknya sisi adalah 5,
dan banyaknya segitiga adalah 2.
Ternyata bebrrapa koe_sien dari polinom karakteristik suatu graf memberikan informasi mengenai graf tersebut dalam hal banyak sisi dan banyak segitiga walaupun draf
tersebut tidak digambarkan secara visual.
2.2 Aljabar Ketetanggaan

Misalkan A adalah suatu matriks persegi berukuran n_n atas C. Dide_nisikan himpunan
polinom dengan variabel berupa matriks A dan koe_sien bilangan kompleks yakni
C[A] =
n
a0 + a1A + _ _ _ + akAkjai 2 C; k _ 0; k 2 Z
o
:
BAB 2. SPEKTRUM GRAF 22
Dide_nisikan operasi penjumlahan, perkalian, dan aksi skalar oleh C pada C[A] sebagai
berikut.
+ : C[A] _ C[A] ! C[A]
(p(A); q(A)) 7! p(A) + q(A);
_ : C[A] _ C[A] ! C[A]
(p(A); q(A)) 7! p(A)q(A);
_ : C _ C[A] ! C[A]
(c; q(A)) 7! cq(A);
dimana untuk setiap c 2 C, p(A); q(A) 2 C[A] dengan p(A) = p0 + p1A + _ _ _ dan q(A) =
q0 + q1A + _ _ _ hampir semua pi; qj 2 C, i; j 2 Z bernilai nol memenuhi aturan :
p(A) + q(A) = r0 + r1A + _ _ _
dengan ri = pi + qi; 8i 2 Z,
p(A)q(A) = r0 + r1A + _ _ _
dengan ri = piq0 + pi1q1 + _ _ _ + p1qi1; 8i 2 Z,
cq(A) = r0 + r1A + _ _ _
dengan ri = cqi; 8i 2 Z,
dan untuk setiap w 2 C dan matriks A = (aij) perkalian wA dide_nisikan dengan baik
komponen demi komponen, yakni wA = (bij) dengan bij = waij .

Spektrum Graf

Diunggah oleh

Hak Cipta:

Format Tersedia

Spektrum Graf

Diunggah oleh

Informasi Dokumen

Hak Cipta

Format Tersedia

Bagikan dokumen Ini

Bagikan atau Tanam Dokumen

Opsi Berbagi

Apakah menurut Anda dokumen ini bermanfaat?

Apakah konten ini tidak pantas?

Hak Cipta:

Format Tersedia

Spektrum Graf

Diunggah oleh

Hak Cipta:

Format Tersedia

SPEKTRUM GRAF

( DEFENISI 2.2 dan 2.4, PREPOSISI 2.3)

JURUSAN PASCASARJANA MATEMATIKA

adalah multiplisitas dari

dengan multiplisitas masing-

. Spektrum dari graf G, dinotasikan dengan Spec G, dapat dituliskan

dalam bentuk berikut ini.

ketetanggaan dari K3 adalah

Dengan demikian spectrum dari K3 adalah

karakteristik dari graf G yang dinotasikan dengan X(G;

. Misalkan juga polinom karakteristik dari

Proposisi 2.3. Koefisien-koefisien polinom karakteristik dari graf

adalah banyaknya sisi pada graf

adalah dua kali banyaknya segitiga pada graf

masing-masing sebanyak p dan q buah. Diperoleh,

2.2 Aljabar Ketetanggaan

Anda mungkin juga menyukai