12
BAB III PELABELAN KOMBINASI
3.1
Konsep Pelabelan Kombinasi
Pelabelan kombinasi dari suatu graf dengan titik dan sisi, , â
graf G, disebut graf kombinasi jika terdapat fungsi bijektif dari ( himpunan titik di G) ke 1,2,3, âĶ , sehingga nilai setiap sisi yang diperoleh dari kombinasi
nilai titik ujung yang lebih besar ke nilai titik ujung yang lebih kecil berbeda satu sama lainnya. Definisi 3.1.1
Sebuah graf G dengan banyak titik dan banyak sisi disebut graf kombinasi
jika terdapat fungsi bijektif : â 1,2,3, âĶ , sehingga menghasilkan
pelabelan sisi : â â yang didefinisikan sebagai =
jika >
jika >
$
merupakan fungsi injektif dengan menyatakan kombinasi dari sejumlah
sebanyak , dengan merupakan himpunan titik pada dan adalah himpunan sisi pada , dan , â yang saling berdampingan
(adjacent). Pelabelan tersebut dinamai pelabelan kombinasi dari . Gambar 3.1.1 merupakan contoh graf kombinasi dan Gambar 3.1.2 bukan merupakan suatu graf kombinasi.
13
Graf G Gambar 3.1.1 Graf Kombinasi
Graf H Gambar 3.1.2 Bukan graf kombinasi
Graf G terdiri dari 7 titik dan 9 sisi, dari graf G tersebut diperoleh
: â 1,2,3, âĶ ,7, = 1,2,3, âĶ ,9, dan = 2,3,4,5,6,7,10,15,21. Sedangkan dari graf H = 2,3,3.
3.2
diperoleh : , â 1,2,3, , = 1,2,3, dan
Konsep Pelabelan Kombinasi Pada Graf Khusus. Pada bagian ini akan dijelaskan mengenai pelabelan kombinasi pada
sebuah graf
dengan titik dan sisi, graf lengkap dengan - titik, yang
dinotasikan dengan .- , cycle (graf lingkaran) dengan - titik, dinotasikan dengan
- , dan graf bipartit lengkap dengan titik disetiap partisi / , dinotasikan dengan ./, æ.
Teorema 3.2.1
Misal G adalah graf dengan titik sisi. Jika G merupakan graf kombinasi, maka berlaku 4 âĪ 1
2 jika genap $ 2 â 1 jika ganjil
14
Bukti:
Misalkan adalah fungsi pelabelan kombinasi untuk , maka terdapat himpunan
= 1 , 2 , 3 , âĶ , ,
titik
sehingga
7 = 1, 2 = 2, 8 =
3, âĶ , 9: ; = . Karena < = â<, banyak nilai yang berbeda di antara
1 , 2 , 3 , âĶ , â1 tidak lebih dari =2> , di mana ?@A merupakan bilangan bulat
terbesar yang sama atau kurang dari x. Secara umum, banyak nilai yang berbeda di antara 1 , 2 , 3 , âĶ , â/â1 ,
1âĪ/ âĪâ2
â/
tidak lebih dari =
â/ > 2
â/
â/
â/
. Tetapi nilai-nilai yang berbeda di antara
1 , 2 , 3 , âĶ â1 dan nilai-nilai berbeda di antara 1 , 2 , 3 , âĶ , â/â1 ,
â/
â/
â/
â/
1 âĪ / âĪ â 2 , kemungkinan ada nilai yang sama di antara keduanya. Karena
adalah fungsi pelabelan kombinasi untuk graf , terdapat q nilai sisi yang berbeda
pada sisi graf tersebut, sehingga diperoleh
â1 â â 2 âĪ = >+C D+âŊ+C D 2 2 2
Kasus 1. Misalkan = 2<, maka, dari persamaan di atas, diperoleh âĪC
2< 2< â 1 D+C D + âŊ + ?1A 2 2
= < + < â 1 + < â 1 + < â 2 + < â 2 + âŊ + 1 + 1
= F< + < â 1 + âŊ + 3 + 2 + 1G + F< â 1 + < â 2 + âŊ + 3 + 2 + 1G
<< + 1 < â 1< + 2 2 << + 1 + << â 1 = 2 = =
2< 2 2
15
= <2 =
2 4
Kasus 2. Misalkan = 2< + 1, maka dari persamaan di atas diperoleh âĪC
2< + 1 2< D + C D + âŊ + ?1A 2 2
= < + < + < â 1 + < â 1 + < â 2 + < â 2 + âŊ + 1 + 1
= F< + < â 1 + âŊ + 3 + 2 + 1G + F< + < â 1 + âŊ + 3 + 2 + 1G << + 1 << + 1 + 2 2 << + 1 + << + 1 = 2 = =
2< 2 + 2< 2
= <2 + <
2 â 1 = 4 Dari kedua kasus tersebut, diperoleh bahwa 4 âĪ 1
2 jika genap $ 2 â 1 jika ganjil
Akibat 3.2.1
Dari Teorema. 3.2.1 graf lengkap dengan - titik, yang dinotasikan dengan .adalah graf kombinasi jika dan hanya jika - âĪ 2.
Bukti:
âđ Diketahui bahwa .- adalah graf kombinasi, maka banyaknya sisi pada .-
adalah 4
--â1 . 2
Dari Teorema 3.2.1 diperoleh
-- â 1 -2 , jika - genap $ âĪ1 2 2 - â 1 , jika - ganjil
16
2-2 â 2 âĪ I
-2 , jika - genap $ âĶâĶâĶâĶâĶâĶâĶ.(*) 2 - â 1 , jika - ganjil
Pertidaksamaan (*) hanya dipenuhi oleh - = 1 atau - = 2 Jadi, .- adalah graf kombinasi dengan - âĪ 2.
âļ Diketahui - âĪ 2, maka .- adalah .1 dan .2 . .7 adalah graf lengkap
dengan satu titik. Jadi, .1 adalah graf yang hanya terdiri dari satu titik tanpa sisi.
.2 adala graf lengkap dengan dua titik dan satu sisi. .1
Jadi, untuk - âĪ 2, .1 dan .2 adalah graf kombinasi.
.2
Teorema 3.2.2
Lingkaran - merupakan graf kombinasi untuk semua - > 3. Bukti:
Namai titik-titik dari - secara berurutan sebagai 1 , 2 , 3 , âĶ , - dengan 1
bertetangga dengan K dan L bertetangga dengan L+1 untuk 1 âĪ L âĪ - â 1 .
Kemudian definisikan pelabelan : K â 1,2,3, âĶ , - dengan
pelabelan
- â 1, L=L = - â 1$ M = N - , L , 1âĪL âĪ-â2
adalah pelabelan dengan nilai-nilai sisinya
O2,3, âĶ , - â 1, -,
--â1 P. 2
Perhatikan bahwa nilai-nilai sisinya berbeda, jika tidak,
untuk suatu / â â, 0 âĪ / âĪ - â 2 ,
-- â 1 =-â/ 2
-2 â - = 2- â 2/
9- ; =
17
-2 â 3- + 2/ = 0 -=
3 Âą â9 â 8/ 2
Sehingga 9 â 8/ > 9 saat - âĨ 4 . Diperoleh / < 0 , kontradiksi. Karena itu,
untuk - âĨ 4, - merupakan graf kombinasi. Teorema 3.2.3
Graf bipartit lengkap dengan partisi titik / yang dinotasikan dengan ./,/ adalah graf kombinasi jika dan hanya jika / âĪ 2 . Bukti:
âļ Diketahui / âĪ 2, akan dibuktikan ./,/ adalah graf kombinasi.
Untuk / âĪ 2 maka ./,/ adalah .1,1 dan .2,2 . Jelas bahwa .1,1 dan .2,2
adalah graf kombinasi
.7,7 Jadi, .1,1 dan .2,2 adalah graf kombinasi.
.2,2
âđ Misalkan A dan B adalah himpunan label pada graf bipartit. Tanpa
mengurangi keumuman, kita asumsikan bahwa 1 â V. Misalkan V =
1, @7 , @2 , âĶ , @WX7 dengan 1 < @7 < @2 < âŊ < @WX7 . Karena @+1 = @+1 1 @ 1, @ â V âđ 1 + @ bukan anggota B
(1)
18
karena 1 + @WX2 bukan anggota B, 1 + @WX2 â V yang berarti bahwa 1 + @WX2 = @WX7. Begitu pula dengan 1 + @WX8 â V yang berarti bahwa 1 + @WX8 = @WX2. Kita dapat melihat bahwa
V = 1, @7 , @7 + 1, @7 + 2, âĶ , @7 + / â 2
misalkan ^ = _7 , _2 , _8 , âĶ , _W dengan _1 < _2 < _3 < âŊ < _/ . Kita akan mempunyai satu dan hanya satu dari
1 < @7 + 1 < @7 + 2 < âŊ < @7 + / â 2 < _7 < _2
(2)
atau
1 < _7 < _2 < âŊ < _W < @7 < @7 + 1 < @7 + 2 < âŊ < @7 + / â 2
(3)
atau
terdapat k, 0 < < < /, sehingga
1 < _7 < _2 < âŊ < _` < @7 < @7 + 1 < @7 + 2
< âŊ < @7 + / â 2 < _`a7 < _`a2 < âŊ < _b
(4)
Jika / âĨ 3 maka, dari (2), 1 dan @1 + / â 2 anggota A. Hal ini berarti
bahwa 1 + @7 + / â 2 = _7 yang anggota B, kontradiksi dengan (1). Dari
(3) kita peroleh bahwa _1 + _/ = @1 + 1 â V, kontradiksi dengan (1). Karena 1 + @7 + / â 2 â V, dari (4) kita peroleh 1 + @7 + / â 2 =
_`a7 â ^, kontradiksi dengan (1). Oleh karena itu ./,/ bukan graf kombinasi untuk / âĨ 3.
Pada bab selanjutnya akan dikemukakan algoritma pelabelan kombinasi
pada graf dengan p titik q sisi, graf lengkap .- , cycle (graf lingkaran) - , graf
bipartit lengkap ./,/ yang berdasarkan pada konsep pelabelan pada bab ini dan menampilkan hasil dari program yang telah dibuat.