II.
TINJAUAN PUSTAKA
Pada bab ini akan dijelaskan beberapa konsep dasar teori graf dan dimensi partisi pada suatu graf sebagai landasan teori pada penelitian ini.
2.1 Konsep Dasar Graf
Pada bagian ini akan dijelaskan beberapa konsep dasar dari graf yang diambil dari )
Deo (1989). Graf G adalah himpunan terurut menyatakan himpunan titik ( vertex) {
} dari
) menyatakan himpunan sisi ( edge) { dari
). Banyaknya himpunan titik
dihubungkan oleh sisi sedangkan titik juga sisi
dan
maka
)), dengan dengan
)
, dan
} yakni pasangan tak terurut ) disebut orde dari graf . Jika
dan
)
dan
dikatakan bertetangga (adjacent),
dikatakan menempel (incident) dengan sisi
dikatakan menempel dengan titik
dan
, demikian
. Himpunan tetangga
(neigborhood) dari suatu titik v, dinotasikan dengan N(v) adalah himpunan titiktitik yang bertetangga dengan v. v1 e4 e7
e1
v3
e5
e2
e3 v2
v5 e6
v4
Gambar 2. Contoh graf dengan 5 titik dan 7 sisi
6
)
Pada Gambar 2, graf ( V, E ) dengan )
{
sedangkan titik
}. Titik dan
dan titik
)
{
} dan
bertetangga dengan titik
menempel dengan ,
{
. Sebaliknya, sisi
,
, dan
menempel pada
}.
Derajat suatu titik v pada graf G adalah banyaknya sisi yang menempel pada titik v, dinotasikan dengan d(v). Daun (pendant vertex) adalah titik yang berderajat 1. Pada Gambar 2,
)
,
)
,
)
,
)
dan
adalah
daun karena berderajat satu.
Loop adalah sisi yang memiliki titik awal dan titik akhir yang sama. Sisi paralel adalah sisi yang memiliki dua titik ujung yang sama. Graf yang tidak mempunyai sisi ganda dan loop disebut graf sederhana. Graf pada Gambar 2 bukan merupakan graf sederhana karena pada graf tersebut terdapat loop yaitu di titik .
Pada graf terhubung G, jarak diantara dua titik
dan
adalah panjang lintasan ). Istilah lain
terpendek diantara kedua titik tersebut, dinotasikan dengan
yang sering muncul pada pembahasan graf adalah jalan (walk), lintasan (path) sirkuit (circuit) dan siklus (cycle). Jalan (walk) adalah barisan berhingga dari titik dan sisi dimulai dan diakhiri sedemikian sehingga setiap sisi menempel dengan titik sebelum dan sesudahnya. Contoh jalan berdasarkan Gambar 2 adalah .
Lintasan
(path) adalah jalan yang melewati titik yang berbeda-beda. Graf G dikatakan graf
7
terhubung jika terdapat lintasan yang menghubungkan setiap dua titik yang berbeda. Lintasan berdasarkan graf pada Gambar 2 adalah . Sirkuit (circuit) adalah lintasan tertutup (closed path), yaitu lintasan yang memiliki titik awal dan titik akhir yang sama. Sirkuit dibedakan menjadi dua macam, yaitu sirkuit genap dan sirkuit ganjil. Sirkuit genap adalah sirkuit dengan banyaknya titik genap, dan sirkuit ganjil adalah sirkuit dengan banyaknya titik ganjil. Contoh sirkuit berdasarkan pada Gambar 2 adalah
. Siklus (cycle) adalah jalan tertutup
(walk) yang semua titiknya berbeda. Contoh siklus berdasarkan pada Gambar 2 adalah
Dari Chartrand dkk. (2000) pewarnaan graf adalah kasus khusus dari pelabelan graf. Pelabelan di sini maksudnya yaitu memberikan warna pada titik-titik batas tertentu. Ada tiga macam pewarnaan graf, yaitu: Pertama, pewarnaan titik yaitu memberikan warna berbeda pada setiap titik yang bertetangga sehingga tidak ada dua titik yang bertetangga mempunyai warna yang sama. 4
3 1
2
Gambar 3. Contoh pewarnaan titik dengan 4 titik dan 5 sisi
8
Kedua, pewarnaan sisi yaitu memberikan warna berbeda pada sisi yang bertetangga sehingga tidak ada dua sisi yang bertetangga mempunyai warna yang sama.
3 2 1
Gambar 4. Contoh pewarnaan sisi dengan 4 titik dan 5 sisi
Ketiga, pewarnaan bidang yaitu memberikan warna pada bidang sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama. 5
1 4
2 3
Gambar 5. Pewarnaan pada bidang dengan 5 titik dan 8 sisi
Lemma 2.1.1 (Deo 1989) Jumlah derajat semua titik pada graf G adalah genap, yaitu dua kali jumlah sisi pada graf tersebut, maka: ∑
)
)
9
Sebagai contoh pada Gambar 2 yaitu jumlah derajat seluruh titik pada graf tersebut adalah
)
)
)
)=
= 14 sama
dengan dua kali jumlah sisi.
Teorema 2.1.2 (Deo 1989) Untuk sembarang graf G, banyaknya titik yang berderajat ganjil selalu genap.
Bukti : Misalkan Vgenap dan Vganjil masing – masing adalah himpunan titik yang berderajat genap dan berderajat ganjil pada G(V,E). Persamaan (1) dapat ditulis sebagai berikut : ∑
Karena
)
∑
( ) untuk setiap
( )
,
∑
)
)
maka suku pertama dari ruas kanan
persamaan harus bernilai genap. Ruas kiri persamaan (2) juga harus bernilai genap. Nilai genap pada ruas kiri hanya benar bila suku kedua dari ruas kanan juga harus genap. Karena di dalam
) untuk setiap
, maka banyaknya titik
harus genap agar jumlah seluruh derajatnya bernilai genap.
Jadi banyaknya titik yang berderajat ganjil selalu genap.
2.2 Graf Pohon dan Beberapa Sifatnya
Graf pohon (tree) adalah suatu graf terhubung yang tidak memuat siklus. Daun adalah titik di graf yang mempunyai derajat satu.
10
v5
v1 v3 v2
v4 v6
Gambar 6. Contoh pohon G dengan enam titik
Pada Gambar
6, graf
) merupakan graf pohon karena graf tersebut
merupakan graf terhubung dan tidak memuat siklus. Titik
disebut
titik pendant atau daun. Gabungan dari beberapa pohon disebut hutan (forest).
Gambar 7. Contoh hutan (forest)
Selanjutnya, akan diberikan definisi beberapa kelas graf pohon. Suatu graf bintang K1,n
adalah suatu graf terhubung yang mempunyai satu titik berderajat n yang disebut pusat dan titik lainnya berderajat satu (Chartrand dkk., 1998).
11
Gambar 8. Contoh graf bintang K1,6
Graf pohon disebut graf bintang ganda (double star) jika graf pohon tersebut mempunyai tepat dua titik
dan
berderajat lebih dari satu. Jika
berturut-turut berderajat a+1 dan b+1, dinotasikan dengan
dan
Sa,b, (Chartrand
dkk.1998)
Gambar 9. Contoh graf bintang ganda S4,3
Graf ulat (caterpillar graf) adalah graf pohon yang memiliki sifat apabila dihapus semua daunnya akan menghasilkan lintasan (Chartrand dkk., 1998).
12
Gambar 10. Contoh graf ulat C(3, 3, 3, 3)
Graf pohon pisang
adalah graf yang diperoleh dari n buah graf bintang
dengan cara menghubungkan sebuah daun dari setiap
ke suatu titik baru (Chen
dkk.(1997)).
Gambar 11. Contoh graf pohon pisang
Graf kembang api seragam, bintang
adalah graf yang diperoleh dari n buah graf
dengan cara menghubungkan sebuah daun dari setiap
sebuah lintasan (Chen dkk.(1997)).
Gambar 12.Contoh graf kembang api
melalui
13
Selanjutnya diberikan beberapa teorema mengenai graf pohon sebagai berikut :
Teorema 2.2.1 (Harsfield dan Ringel, 1994) Jika dan
sisi, maka
adalah pohon dengan
titik
.
Bukti:
Jika
adalah pohon dengan satu sisi maka teorema benar untuk
teorema benar untuk semua pohon dengan sisi kurang dari maka
. Misal
terpanjang di
dari
ke
pohon dengan
. Titik
. Asumsikan
, artinya untuk
sisi. Pilih satu lintasan
harus berderajat . Karena kalau tidak,
lintasan akan menjadi lebih panjang atau terbentuk siklus di . Selanjutnya buang titik
dan akibatnya sisi terhubung titik
) dan
bahwa pohon terbentuk dengan )
terbuang. Sehingga berdasarkan asumsi
atau
) sisi adalah ■
.
Teorema 2.2.2 (Harsfield dan Ringel, 1994) Graf
adalah pohon jika dan
hanya jika ada terdapat tepat satu lintasan diantara kedua titik tersebut.
Bukti:
(1) Akan ditunjukkan graf
adalah pohon maka terdapat tepat satu lintasan
diantara kedua titik. Asumsikan
adalah pohon, misal
, maka pohon dapat dihubungkan dari lintasan dua lintasan dari
ke
,
ke dan
dan
titik-titik di
. Anggaplah terdapat
14
Selanjutnya jika pada yang juga dalam suatu ,
akan ditemukan suatu titik yang terdapat dalam
, maka akan terdapat siklus. Jika
, karena ada dua lintasan
, maka untuk
sebagai asumsi. Selanjutnya
dari
sampai ditemukan suatu titik yang terdapat dalam
dalam
dan selanjutnya ambil
kembali ke
yang juga
, dan akan didapatkan
siklus lagi. Tetapi
adalah pohon, sehingga tidak ada siklus. Jadi asumsi
bahwa ada dua
lintasan salah.
(2) Akan ditunjukkan bahwa ada terdapat tepat satu lintasan diantara kedua titik maka graf
adalah pohon. Asumsikan
diantara dua titik. Pertama perhatikan terdapat siklus
terhubung. Anggaplah bahwa pada
. Jelas bahwa ada dua lintasan dari
kontradiksi, karena graf
adalah graf dengan tepat satu lintasan
ke
. Ini
mempunyai tepat satu lintasan diantara dua titik. Jadi
tidak mengandung siklus dan
■
adalah pohon.
2.3 Dimensi Partisi Graf
Pada bagian ini akan diberikan definisi dan sifat-sifat dari dimensi partisi pada suatu graf yang diambil dari Chartrand dkk.(1998).
himpunan
) dan
) suatu graf,
Misalkan
, dinotasikan dengan
) adalah jarak dari titik label ke- , misalkan
{
) dengan dinotasikan dengan
ke .
) adalah
). Jarak dari titik {
)
} dengan
adalah himpunan titik-titik yang diberi } adalah himpunan k pasang terurut dari
adalah partisi-partisi. Representasi ∣
ke
) adalah k vektor (
)
terhadap )
, )).
15
Selanjutnya
) jika
disebut partisi pembeda dari
). Dimensi partisi dari
setiap dua titik berbeda ), adalah nilai
∣ )
terkecil sehingga
∣ ) untuk
, dinotasikan dengan
mempunyai partisi pembeda dengan
kelas. v5 v4 2
1
v6 3
1
v1 1 v3
2
v9
v8
2
1 v2
1
2
v10
v7
Gambar 13. Contoh gambar graf G dengan 10 titik dan dimensi partisinya.
Pada Gambar 13 diberikan graf ∏
{
}
dipartisi sedemikian sehingga diperoleh {
dengan
}
{ }. Perhatikan bahwa, ∣
)
)
∣
)
)
∣
)
berbeda, maka
)
∣ ∣
)
∣
)
) )
)
. Perhatikan titik
)
}
) ∣ )
dan
)
∣ )
); )
)
∣
)
) Karena representasi dari setiap titik
adalah partisi pembeda dari graf dan
Untuk menunjukkan dari
∣
{
)
.
, andaikan terdapat partisi pembeda memiliki 3 daun yaitu
dan
(3)
{
}
. Jika hanya
terdapat dua kelas partisi pembeda, maka dua dari tiga daun tersebut akan memiliki partisi yang sama. Akibatnya representasi kedua daun itu akan sama,
16
karena memiliki jarak yang sama terhadap titik-titik lainnya pada graf )
kontradiksi. Jadi
.
(4) )
Berdasarkan Persamaan (3) dan (4) diperoleh
Lemma 2.3.1 Diberikan
dan
.
graf terhubung dengan partisi pembeda
) jika
untuk
,
)
)
) untuk setiap
dari {
)
}, maka
merupakan elemen yang berbeda dari
Berikut ini akan diberikan teorema untuk menentukan dimensi partisi pada graf bintang ganda.
Teorema 2.3.2 (Chartrand dkk. 1998) Misalkan (
maka
)
graf bintang berorde
,
.
Bukti : vN-1 n
8 v2 v2
v2 1
7
v2
v2 2
6 5 v2
4
v2
3
v2
Gambar 14. Dimensi partisi graf bintang
Graf
dipartisi sedemikian sehingga diperoleh
dengan {
{
}
{ }
}. Perhatikan bahwa
{ } ∣
)
{ }
{
} { }
dan )
17
∣
)
);
∣
)
)
∣
)
)
)
∣ ∣
)
)
) )
∣
Karena representasi dari setiap titik berbeda, maka graf
(
dan
)
)
{
, andaikan bahwa terdapat partisi pembeda } dari
yaitu pada titik
dan
kontradiksi. Jadi
adalah partisi pembeda dari
. (
Untuk menunjukkan
).
. Maka (
)
maka ada representasi yang sama
bukan merupakan partisi pembeda dari graf . Akibatnya
(
)
.
Berikut ini akan diberikan contoh penentuan dimensi partisi dari graf bintang
.
v2 v7
1
6
v3 2
1 v1 5
3
v6
4 v5
v4
Gambar 15. Dimensi partisi graf
Graf
{
dipartisi sedemikian sehingga diperoleh
dengan
{
Perhatikan
bahwa
∣
)
∣
)
}
{ } ∣ ); )
{ } )
{ } )
}
{ } dan ∣
∣
)
)
∣
)
)
)
{ }. );
18
∣
)
). Karena representasi dari setiap titik berbeda, maka
adalah partisi pembeda dari graf
Untuk menunjukkan {
(
dan
)
(
)
.
, andaikan bahwa terdapat partisi pembeda
} maka akan ada representasi yang sama pada titik
Sehingga, (
bukan merupakan partisi pembeda dari graf
)
. Akibatnya,
(
dan
.
, kontradiksi. Jadi
)
Selanjutnya akan diberikan beberapa lemma dan teorema hasil penelitian Asmiati dkk. (2012) tentang dimensi partisi dari graf amalgamasi bintang.
Lemma 2.3.3 Misal | |
adalah partisi pembeda dari graf
. Partisi pembeda
hanya jika
dan
{ |
adalah hasil partisi dari graf
dengan jika dan
dalam kelas yang sama pada kelas kombinasi } dan jika { |
} adalah pembeda.
Bukti :
Misal
adalah hasil partisi dari graf adalah kelas yang sama dari
{
|
} dan { )
adalah sama. Jadi pengandaian.
|
) untuk setiap
dengan | |
dan
. Jika kombinasi kelas dari } adalah sama. Karena maka representasi dari
dan
bukan hasil dari partisi. Maka kontradiksi dengan
19
Misalkan
dengan | |
adalah partisi pembeda dari graf { |
Misal A dinotasikan dari kombinasi kelas graf dinotasikan dari kombinasi kelas graf { dan dimana
}.
.
Akan
ditunjukkan
dan bahwa
) adalah unik.
representasi dari setiap | )
Perbandingan
. Karena A = B, maka
dan
Jelas,
} dan B
|
adalah kelas yang sama dari
.
| ) karena representasinya berbeda dalam ordinat ke m
dan ordinat ke n. Jika
dan
adalah kelas yang sama pada
dan
adalah kelas yang sama pada
alasan pada teorema ini, yaitu A = B. Jadi ( | ) Kasus 2, misal
akan
| ). Di bagi dalam 2 kasus, yaitu:
ditunjukkan bahwa ( | ) Kasus 1, jika
dengan
dan
maka diperoleh | ).
maka ( | )dan
| )
adalah berbeda dalam ordinat ke x dan ordinat ke y. | ).
Jadi ( | ) Jika
dan
dalam kelas yang sama pada
maka representasi
| ) mempunyai setidaknya ada satu komponen yang bernilai 1. Sedangkan (
| ) mempunyai tepat satu komponen yang bernilai 1.
Maka
| )
(
| ).
20
Jika
dan
dalam kelas yang sama pada
| )
maka representasi
mempunyai setidaknya ada satu komponen yang bernilai 1. Sedangkan ( | ) mempunyai tepat satu komponen yang bernilai 1. | )
Maka Jika
dan
( | ).
dalam kelas yang sama pada . Di bagi dalam 2 kasus.
Kasus
.
Representasi
komponen yang bernilai 1. Sedangkan ) komponen yang bernilai 1. Maka Kasus
)
. Karena
Lemma 2.3.4 Misal )
( | )
| ) mempunyai kurang dari | )
( | )
) maka
| )
) partisi
adalah
)
mempunyai
( | ).
, maka
.
Bukti :
Misal
) partisi pada
adalah
, tetap untuk , misal ,
maka jumlah kombinasi partisi { | ) partisi dari
} adalah
) berdasarkan Lemma
, untuk setiap
2.3.1 di peroleh jumlah dari
adalah
partisi yang sama dan
)
). Karena
) . Akan tetapi, jika
dalam kelas
) maka harus menghilangkan
, untuk
memastikan bahwa semua titik akan mempunyai representasi yang berbeda. Jadi jumlah maksimum dari
adalah
) -1.
21
Teorema 2.3.5
(
)
{ )
)
Bukti:
Akan ditunjukkan batas bawah dimensi partisi pada graf
untuk
, berdasarkan Lemma 2.3.1 untuk setiap , terdapat 2 titik (
Maka
dan
memiliki partisi yang berbeda.
)
Akan ditunjukkan batas atas dimensi partisi pada graf . Misal
untuk
. Untuk menunjukkan bahwa setiap
daun akan memiliki representasi yang berbeda, maka harus menempatkan untuk setiap penyelesaian (
ke dalam kelas yang berbeda. Jadi, -partisi
)
).
dari
Karena
(
)
,
adalah ,
maka
.
Selanjutnya akan ditentukan batas bawah untuk ,
suatu partisi
yang sama, maka
hasil dari
(
dalam ordinat ke k dan 1 lainnya. Maka
). Jika | ) dan ( salah, jadi
. Misal dan
mempunyai kelas
| ) keduanya memiliki 0 (
)
.
22
Untuk menentukan batas atas dari
, berdasarkan Lemma
2.3.1, bahwa suatu daun untuk titik yang sama harus memiliki kelas yang berbeda, maka
kombinasi dari {
untuk
memiliki partisi yang berbeda, yaitu
}
, { |
. Untuk setiap
. Amati jika { |
adalah tetap untuk
} dan {
|
}
yang sama. Kemudian untuk menentukan bahwa akan ada
daun yang memiliki representasi yang berbeda, maka yang
berbeda.
{ |
Untuk } maka
sama. Jadi
, kecuali
pada
. Kemudian .
(
)
untuk
dan tidak
. Akan tetapi jika dan
memiliki kelas diberikan
dapat menjadi
. Ini menghindari
adalah
dan
jika
kehilangan sifat umum dari pada setiap
}
digunakan dalam
mempunyai representasi yang untuk
23
3 2
4
1
5 1
5
1
4
2
2
3 4
3
1
2
4 1
5
3 5
1 4
2
3
Gambar 16. Dimensi partisi graf amalgamasi bintang 3 1
4
4
1
3
2 3 3
1
3
1
4
4 4
2
1
1
3
3
1
4
3
1
4
Gambar 17. Dimensi partisi graf amalgamasi bintang
