ALTERNATIF PEMBUKTIAN DAN PENERAPAN TEOREMA BONDY. Hasmawati Jurusan Matematika, Fakultas Mipa Universitas Hasanuddin

Jurnal Ilmiah “Elektrikal Enjiniring” UNHAS

Volume 07/ No.03/ Oktober-Desember/ 2009

ALTERNATIF PEMBUKTIAN DAN PENERAPAN TEOREMA BONDY Hasmawati Jurusan Matematika, Fakultas Mipa Universitas Hasanuddin [email protected] Abstract Graf yang memuat semua siklus dari yang terkecil sampai ke yang terbesar disebut pansiklis. Teorema Bondy menyebutkan bahwa jika G berorde n dan δ(G)≥n/2, maka G adalah pansiklis atau G=K_(n/2,n/2) untuk n genap. Sementara itu, graf dengan siklus yang memuat semua titik dari graf tersebut disebut graf Hamilton. Dalam makalah ini akan ditunjukkan bahwa graf Hamilton yang dilengkapi dengan syarat tertentu juga memuat siklus dari yang terkecil sampai yang terbesar. Dengan demikian, karakteristik graf Hamilton dengan sifat-sifat tertentu tersebut dapat digunakan untuk membuktikan teorema Bondy. Kata Kunci : graf, siklus, pasilkis, Bondy, Hamilton I.

II.

PENDAHULUAN

Teori Ramsey adalah suatu area penelitian dalam teori graf yang sedang berkembang pesat dan mempunyai banyak aplikasi, di antaranya pada teori bilangan, analisis harmonik, aljabar, geometri, komputasi, topologi, teori himpunan, logika, teori ergodik, teori informasi dan ilmu komputer (Makalah Pidato Ilmiah Baskoro, 2007). Meskipun tergolong area yang baru dalam bidang kombinatorik, khususnya dalam teori graf, namun teori ini telah mendapat perhatian dari banyak peneliti. Akibatnya kajian ini berkembang pesat dan telah memperoleh banyak hasil. Kesulitan utama dalam menentukan bilangan Ramsey graf adalah sulitnya menemukan metode, teknik, atau teorema yang terkait dengan karakteristik suatu graf. Namun untuk graf siklus, teorema Bondy dapat dijadikan sebagai alternatif metode. Lebih jauh, graf roda adalah graf yang subgraf pembangunnya memuat siklus, Olehnya itu, metode atau teknik yang digunakan pada penentuan bilangan Ramsey untuk graf siklus, juga dapat digunakan pada penentuan bilangan Ramsey untuk graf roda. Teorema Bondy adalah teorema yang menjamin keberadaan semua siklus. Teorema ini menyebutkan bahwa jika terdapat suatu graf yang derajat terkecilnya adalah setengah dari ordernya maka graf tersebut memuat semua siklus dari yang terkecil sampai yang terbesar. Dengan demikian, torema Bondy mempunyai peranan yang penting dalam penentuan bilangan Ramsey, khususnya untuk graf yang memuat siklus. Jadi pemahaman yang mendalam tentang teorema Bondy dengan cara menemukan alternatif pembuktiannya adalah penting.

2.1.

TINJAUAN PUSTAKA

Graf dan Subgraf Graf G(V,E) adalah suatu sistem yang terdiri dari himpunan berhingga tak kosong V = V(G) dan himpunan E = E(G) dengan E , - . Himpunan V disebut himpunan titik dari G dan himpunan E disebut himpunan sisi dari G. Setiap u dan v di V(G) disebut titik dan setiap e = {u,v} di E(G) disebut sisi. Selanjutnya, sisi e = {u,v} ditulis uv. Titik u disebut tetangga (neighbor) dari titik v jika e = uv. Lebih lanjut, titik u dan v dikatakan titik-titik bertetangga (adjacent), sedangkan sisi e dikatakan terkait (incident) dengan titik u dan v. Dua sisi e1 dan e2 pada G disebut sisi-sisi bertetangga jika e1 dan e2 terkait pada satu titik yang sama. Sisi dan dikatakan saling bebas jika dan tidak bertetangga. Secara serupa, dua titik pada G dikatakan saling bebas jika kedua titik tersebut tidak bertetangga. Graf F disebut komplemen dari graf G, jika V(F) = V(G) dan uv E(F) jika dan hanya jika uv E(G). Komplemen dari graf G dinotasikan dengan ̅ . Dua graf G dan H disebut isomorfik jika terdapat pemetaan satu-satu dan pada : V(G) V(H) ( ) berlaku sedemikian sehingga untuk setiap ( ) xy E(G) jika dan hanya jika ( ) ( ) Kardinalitas himpunan S dinotasikan dengan | |, adalah banyaknya anggota dari S. Orde graf G adalah | ( )| dan ukuran graf G adalah | ( )|. Graf G berorde m dinotasikan dengan Gm. Graf dikatakan graf lengkap, dinotasikan dengan jika setiap dua titik pada bertetangga. Misalkan adalah sebarang ( ) . Didefinisikan titik pada dan Ns(vi) = {w ( )+ dan Ns[vi]=Ns(vi) * +,



dan

(

)

( ) ( ),

( )

(

)

( ) ( ).

( )

Derajat titik , dinotasikan dengan ( ), adalah | ( )|. Derajat maksimum dari adalah * ( ) ( )+, dan derajat minimum dari adalah ( ) * ( ) ( )+. Graf disebut graf r-reguler jika ( ) . Teorema II.1 Misalkan G adalah sebarang graf berorde n dan berukuran q. Jika ( ) ( ), maka

, ( ) dan dinotasikan dengan , -. Subgraf ( )- dinotasikan dengan . ( ) adalah sebarang graf. Misalkan Misalkan pula

*

*

+

+.

subgraf dari ( dan + . Graf

)

dan

. Didefinisikan dan adalah

Graf dengan

(

suatu

)

*

adalah suatu subgraf dari ( ) dan * + dan Khususnya untuk , subgraf ditulis dan ditulis . Contoh subgraf-subgraf dapat dilihat pada Gambar 2.

(

)

dengan . dengan subgraf tersebut

∑ ( ) Akibat II.1 Banyaknya titik yang berderajat ganjil pada suatu graf adalah genap Bukti Teorema II.1 dan Akibat II.1 dapat dilihat pada rujukan Chartrand dan Lesniak (1996). Misalkan u dan v adalah dua titik pada graf yang tidak bertetangga. Graf * + adalah suatu ) graf baru dengan himpunan titik ( ( ) ( ) ( ) * +. dan himpunan sisi Contoh graf baru tersebut dapat dilihat pada Gambar1.(b).

Gambar 1. (a) Graf

Graf

(

dan (b) Graf

Gambar 2. (a) Graf

, (b) subgraf

, dan

(c) subgraf

Lintasan (path) dengan titik adalah graf yang titik-titiknya dapat diurutkan dalam suatu barisan sedemikian sehingga ( ) * +. Graf dikatakan terhubung jika untuk setiap dua titik dan pada graf tersebut terdapat suatu lintasan yang memuat dan . Jika adalah suatu lintasan berorde dan , maka graf * + disebut siklus berorde (Lihat Gambar 3). Panjang adalah , yaitu banyaknya sisi pada dan panjang siklus adalah .

) disebut subgraf dari jika ( ). Selanjutnya, subgraf

( ) dan dari ditulis . Subgraf dikatakan subgraf maksimal dari jika memuat semua sisi ( ) untuk semua . Untuk sebarang himpunan ( ), subgraf tereduksi oleh dari adalah subgraf maksimal dari dengan himpunan titik

Gambar 3. (a) Lintasan Pn dan (b) Siklus Cn


Panjang siklus terbesar pada suatu graf dinotasikan dengan ( ), sedangkan panjang siklus terkecil dinotasikan dengan ( ). Graf dengan orde disebut pansiklis (pancyclic) jika memuat semua siklus dengan , dan disebut pansiklis lemah (weakly pancyclic) jika memuat siklus untuk ( ) ( ). Graf pada Gambar 4 adalah pansiklis lemah dengan ( ) dan adalah pansiklis karena memuat semua siklus untuk .

Gambar 4

Teorema II.2 berukuran

Jika G adalah graf berorde n dan

⁄

maka G memuat sebuah siklus

ganjilatau ⁄ ⁄ Teorema II.3 Misalkan G adalah sebarang graf ( ) ( ) berorde n Jika ( ) maka G dalah graf hamilton. Graf pohon adalah graf terhubung berorde dan tidak memuat siklus. Bintang adalah pohon dengan V(Sn) = {v1, v2, ..., vn} dan E(Sn) = {v1vi+1 : i = 1, 2, ..., n – 1}. Titik v1 disebut pusat dari Sn. Graf pada Gambar 5 adalah bintang S11 dengan pusat v1.

Gambar 5. Bintang S11

Roda Wk adalah suatu graf yang dibentuk dari siklus Ck dengan menambahkan satu titik, sebut x, dan menambahkan k sisi dari titik x ke semua titik di Ck. Dalam hal ini, titik x disebut poros (hub) roda dan siklus Ck disebut rim roda. Pada Gambar 6 adalah roda W8 dengan poros x.


Gambar 6

Misalkan V1, V2, ... Vk adalah beberapa himpunan bagian dari himpunan titik V(G) pada suatu graf G. Untuk setiap i, himpunan Vi disebut partisi dari ( ) ⋃ V(G) jika , dan serta dengan . Graf G disebut graf kpartit jika V(G) dapat dipartisi ke dalam k partisi himpunan bebas V1, V2,..., Vk. Graf k-partit untuk dengan | | disebut graf multipartit, dinotasikan dengan , disebut graf . Khusus untuk bipartit. Graf multipartit disebut graf multipartit lengkap jika setiap titik di setiap partisi bertetangga dengan semua titik di partisi-partisi lainnya. Graf multipartit lengkap dinotasikan dengan Menurut pengertian ini, bintang . merupakan graf bipartit lengkap dengan notasi

.

Misalkan adalah graf dengan himpunan titik dan himpunan sisi , . Graf gabungan adalah suatu graf dengan ⋃ himpunan titik

⋃

dan himpunan sisi

. Definisi graf jumlah secara umum ⋃ belum ada. Namun untuk jumlah dua graf, telah didefinisikan seperti berikut: Graf Jumlah (join) adalah suatu graf dengan ( ) ( ) dan * + (Disertasi Hasmawati, 2007). ̅̅̅ dapat dilihat Contoh graf jumlah pada Gambar 7 (b). Dengan demikian, bintang dapat ̅̅̅̅ didefinisikan sebagai , roda dapat didefinisikan sebagai .

Gambar 7. (a) graf

̅̅̅ dan (b) graf

̅̅̅.



2.2.

Pewarnaan dan Dekomposisi Secara umum pewarnaan graf terdiri atas pewarnaan titik dan pewarnaan sisi pada graf . Pewarnaan titik adalah pemberian warna pada himpunan titik ( ) dengan aturan setiap titik diberi hanya satu warna dan dua titik yang bertetangga diberi warna yang berbeda. Graf dikatakan berwarna k jika dapat diwarnai dengan k warna. Bilangan asli terkecil k sedemikian sehingga berwarna k disebut bilangan kromatik dari , dinotasikan ( ). Sebagai contoh :

( (

) )

Sedangkan pewarnaan sisi adalah memberi warna pada himpunan sisi ( ) sedemikian sehingga sisi-sisi yang bertetangga mempunyai warna yang berbeda. Selain kedua pewarnaan ini, juga terdapat bentuk pewarnaan lain yaitu pemberian dua atau lebih warna pada himpunan titik ( ) dan himpunan sisi ( ) sedemikian sehingga memuat suatu subgraf yang monokromatik (subgraf yang memiliki satu warna). Bentuk pewarnaan ini digunakan pada penentuan bilangan Ramsey. Misalkan adalah graf dan untuk setiap . Dekomposisi graf adalah himpunan ( ) * + sedemikian sehingga ( ) ( ) ( ) dan ( ) ⋃

( *

)

untuk

setiap

+ Dekomposisi dari graf

notasi

( ⋃ 2.3.

) dan

dan

Bilangan Mo disebut bilangan Ramsey klasik dua warna yang selanjutnya disebut bilangan Ramsey klasik, dan dinotasikan dengan R(n1, n2) atau R( , ). Pengertian bilangan Ramsey klasik R(n1, n2) dapat dinyatakan sebagai berikut. Definisi II.3.2 Untuk sembarang dua bilangan asli n 1 dan n2, bilangan Ramsey R(n1, n2) adalah bilangan bulat terkecil m sedemikian sehingga untuk setiap graf F berorde m memenuhi sifat berikut: F memuat graf atau

.

Karena setiap graf F memenuhi ̿ = F, R(n1, n2) pada Definisi II.3.2 bersifat simetri yaitu R(n1, n2)= R(n2, n1). Erdos dan Szekeres (1935) membuktikan eksistensi bilangan Ramsey klasik R(n1, n2) dengan menunjukkan batas atas dan batas bawahnya. Batas atas dan batas bawah tersebut, berturut-turut, disajikan dalam dua teorema berikut. Teorema II.3.2 (Batas atas). Untuk setiap bilangan asli n1 dan n2, R(n1, n2) senantiasa ada dan memenuhi R(n1, n2)

(

)

Teorema II.3.3 (Batas bawah). Untuk setiap bilangan asli dimana n1 2 dan n2 2 maka R(n1, n2) 1 + (n1 – 1)(n2 – 1). Pada definisi bilangan Ramsey klasik di atas, apabila graf bukan hanya graf lengkap melainkan berlaku secara umum yakni berlaku untuk sembarang graf, maka bilangan Ramsey R(G, H) hanya disebut bilangan Ramsey graf.

ditulis dengan . Sebagai contoh ̅̅̅̅.

Bilangan Ramsey Teori Ramsey pertama dipelajari dalam konteks problem penentuan prosedur regular untuk memeriksa konsistensi dari suatu formula logika yang diberikan. Kemudian, teori ini menjadi terkenal setelah Paul Erdos dan George Szekeres (1935) mengaplikasikannya ke dalam teori graf yang menghasilkan teorema tentang bilangan Ramsey graf. Selanjutnya, melalui teorema tersebut konsep bilangan Ramsey graf dua warna dinyatakan dalam teorema berikut Teorema II.3.1 Untuk setiap bilangan bulat n1 dan n2, terdapat bilangan bulat terkecil M0 sedemikian sehingga jika , maka setiap pewarnaan dua warna pada sisi-sisi graf lengkap Km akan memuat subgraf yang semua sisinya berwarna sama dan isomorfik dengan atau .

̅ memuat

III.

MANFAAT DAN TUJUAN PENELITIAN

Penelitian ini bertujuan untuk menemukan metode alternatif pembuktian teorema Bondy. Pada penelitian ini dikaji graf Hamilton dan sifat-sifatnya. Siklus Hamiltonian (Hamiltonian Cycle) merupakan siklus dalam graf G yang memuat setiap titik di G. Graf yang memuat siklus Hamiltonian disebut graf Hamilton. Selanjutnya, graf Hamilton yang memiliki sifat tertentu memuat semua siklus dari yang terkecil sampai ke yang terbesar. Dengan demikian graf Hamilton dengan beberapa tambahan sifat-sifat dapat digunakan untuk membuktikan teorema Bondy. 3.1.

Teorema Bondy Teorema Bondy adalah teorema yang menjamin keberadaan semua siklus. Teorema ini menyebutkan bahwa jika terdapat suatu graf yang derajat terkecilnya adalah setengah dari ordernya maka graf tersebut memuat semua siklus dari yang terkecil sampai yang terbesar. Oleh karena roda adalah graf yang subgraf



pembangunnya adalah siklus maka untuk mengetahui keberadaan roda juga dapat menggunakan teorema Bondy. Teorema III.1. (Bondy, 1971) Misalkan G adalah graf berorde n. Jika

( )

, maka

adalah pansiklis atau

untuk n genap. Bukti : Pertama-tama akan ditunjukkan bahwa jika adalah graf berorde dan

⁄

dimana

( )

,

Andaikan adalah bilangan ganjil. Maka dengan menggunakan persamaan (1) terdapat beberapa titik, yang dimisalkan , sedemikian sehingga ( ) . Akibatnya

, maka n genap

∑

⁄ . (

Misalkan G adalah graf berorde n dengan

( )

( ), akan diperoleh

. Maka

( )

( )

∑ .

⁄ .

bertetangga dengan

*

dengan

( (

yang

tidak

bertetangga

(

. Dan juga

(

))

, terdapat sebuah titik pada

+

(

) . (∑ ( )( ) ) )

)

,

⁄

adalah bilangan genap dan

⁄ .

menurut persamaan (1), maka

⁄ dan

⁄

menurut

⁄ .

persamaan (1), maka berlaku persamaan (1) berlaku untuk setiap maka ( ) jika dan hanya jika

Misalkan adalah siklus )-siklus Hamilton dari yang tidak memuat ( dimana dan misalkan dan adalah dua titik yang berurutan dari C (dimana semua subscripts dinyatakan sebagai modulo n). Jika dan dan , maka paling banyak satu dari dan adalah sebuah sisi dari G. Oleh karena itu untuk setiap titik-titik dengan pada ( ) { } yang

( )

Jika

Jika

Dengan demikian diperoleh graf Hamilton ), dimana

(

dimana kontradiksi dengan kenyataan bahwa

∑ ( )

atau

)

⁄ . Jadi n adalah bilangan genap.

Berdasarkan teorema II.3, graf G merupakan graf Hamilton. Menurut Teorema II.1, ukuran dari suatu graf atau banyaknya sisi pada suatu graf yang dinotasikan dengan adalah

(

(1)

)

dan

. Andaikan

⁄

⁄ .

Jika

Jika

( ) (2) berlaku

⁄ , dengan menggunakan Teorema II.2, maka mempunyai sebuah siklus ganjil. Ini menunjukkan bahwa G memuat sebuah siklus sebelah luar terbesar dengan panjang yang ganjil. Misalkan , adalah siklus sebelah luar yang terpendek dengan panjang ganjil maka adalah genap dan ( tidak memuat ( )-siklus). Oleh karena berlaku ( ), maka dengan persamaan (2), ( ). Dan begitu pula dengan menggunakan persamaan (2) maka diperoleh ( ). Oleh karena itu

)) (∑( (

)

adalah sebuah siklus bagian luar dengan panjang ganjil

, dimana hal ini



kontradiksi dengan panjang siklus terpendek pada yaitu . Jadi ⁄ ⁄ . Kemudian akan ditunjukkan dengan induksi pada bahwa jika adalah sebuah graf hamilton

(

⁄ , maka

), dimana

pansiklis atau

memiliki

⁄ untuk

karena

genap.

(

)⁄ (

maka

pansiklis

)⁄ untuk

)⁄ (

Misalkan

atau

sebuah graf Hamilton

⁄

⁄

atau (ii)

(

)

genap dan

ganjil. Akan ditunjukkan

bahwa

pansiklis. Menurut asumsi ini yang merupakan lanjutan dari bagian pertama pembuktian dimana ⁄ ⁄ dengan

genap dan

memuat

yang merupakan sebuah ( )-siklus dari G. ) yaitu Dalam hal ini, memuat sebuah siklus ( . Misalkan adalah titik yang tunggal dari yang tidak terdapat di . Jika deg , maka untuk setiap bilangan memenuhi , sehingga verteks terletak pada sebuah ( )-cycle dari ; Sebaliknya, jika ( ) dengan , maka ( ), dimana (mod ). tidak terletak pada setiap siklus atau terdapat siklus yang tidak memuat . Hal ini menunjukkan bahwa deg

(

)⁄ ,

⁄ . Jadi

yang mana kontradiksi dengan deg

⁄ .

adalah pansiklis jika deg Jika deg Hamilton berorder

⁄ , maka

adalah graf

dengan paling

sedikit

)⁄

sisi .

(

titik

(

.

)⁄

asumsi )⁄ (

)⁄

)⁄

maka

Oleh dan bahwa dengan

menggunakan hipotesis induksi maka disimpulkan bahwa adalah pansiklis. Jadi terbukti adalah pansiklis. 3.2.

bernilai genap.

⁄ . Diasumsikan bahwa (i)

dengan

(

⁄

(

Jika , maka dan pansiklis. Diasumsikan bahwa untuk semua graf Hamilton berorder ( ) dengan sisi paling sedikit

)⁄

adalah sisi yang terkait dengan

sesuai ⁄

(

⁄

Penentuan Batas Atas Bilangan Ramsey Dengan Menggunakan Teorema Bondy Terdapat beberapa teknik dan metode yang dapat digunakan dalam menentukan batas atas bilangan Ramsey. Diantaranya: konsep keberadaan suatu graf tertentu, keterhubungan suatu graf, himpunan bebas dan lain-lain. Khusus untuk menentukan bilangan Ramsey graf yang memuat roda, biasanya digunakan konsep keberadaan suatu siklus seperti lemma Dirac, lemma Brandt atau teorema Bondy. Roda adalah graf yang subgraf pembangunnya memuat siklus. Oleh karena itu, penentuan bilangan Ramsey untuk graf roda dapat menggunakan teorema Bondy, khususnya dalam menentukan batas atasnya. Sebagai contoh, kita akan menunjukkan bahwa batas atas untuk bilangan Ramsey graf bintang terhadap graf ) untuk ganjil dan roda ( ) adalah atau ( . Misalkan graf F adalah sembarang graf dengan orde . Andaikan graf F tidak memuat bintang Sn . Akan ditunjukkan bahwa komplemen F memuat roda Wm. Misalkan titik x di graF. Karena graf F tidak memuat bintang Sn , maka d(x) < 2n -1 untuk setiap x di F. Tulis A = V(F)/N[x] dan T = F[A]. Mudah untukdiperiksa bahwa T ≥ 2n – 1. Mengingat d(v) < 2n -1 untuk setiap titik di T, dan banyaknya titik di koplemen T sama dengan banyaknya titik di T, maka derajat setiap titik di komplemen T lebih besar dari setengah ordenya. Menurut Teorema Bondy komplemen T memuat semua siklus Cm untuk 3≤m≤T. Siklus Cm bersama-sama dengan titik x membentuk roda Wm di komplemen F. Dengan demikian, dapat disimpulkan bahwa graf F dengan orde 3n - 2 selalu memuat bintang Sn atau komplemennya memuat roda Wm. Jadi 3n - 2 adalah batas atas bilangan Ramsey untuk bintang Sn terhadap roda Wm atau . Menurut definisi batas atas bilangan Ramsey, untuk sebarang graf dengan orde , atau ̅ . ̅ Andaikan F tidak memuat . Akan ditunjukkan



memuat . Misalkan adalah sebarang titik di ( ) . Karena , untuk setiap , - dan , -. . Sebut ( ) Mudah untuk diperiksa bahwa | | . Karena ( ) untuk setiap titik dan | ̅ |

| |, maka

̅(

)

| |

(

| ̅|

DAFTAR PUSTAKA 1. 2.

) . 3. ̅ Menurut teorema Bondy , memuat siklus | ̅ |. , untuk 4. Dengan demikian, diperoleh suatu roda di ̅ yang ) berporos di . Jadi, ( untuk 5. .

IV.

KESIMPULAN

1. Teorema Bondy adalah suatu metode yang mempermudah seseorang dalam penentuan bilangan Ramsey graf khususnya untuk pasangan graf yang memuat siklus atau roda. 2. Teorema Bondy adalah teorema tentang karakteritik graf yang memuat semua siklus dari yang terkecil sampai yang terbesar. Sementara itu, graf Hamilton yang memnuhi sifat tertentu juga memuat semua siklus. Karena itu, graf Hamilton dengan sifat tertentu tersebut dapat dijadikan sebagai metode alternative pembuktian teorema Bondy.

Chartrand, G., dan Lesniak, L., CRC (1996) : Graph and Digraph, 3th , Chapman and Hall. Erd ̈ s, P., dan Szekeres, G. (1935) : A Combinatorial Problem in Geometry, Composito Math., 2 , 463 - 470. Hasmawati. (2007) : Disertasi Bilangan Ramsey untuk Graf yang Memuat Bintang, Departemen Matematika ITB, Indonesia. Johnsonbaugh, R. (2002) : Matematika Diskrit, perpustakaan Nasional, Jakarta. Wilson R. J., (1996) : Introduction to Graph Theory. Longman.

ALTERNATIF PEMBUKTIAN DAN PENERAPAN TEOREMA BONDY. Hasmawati Jurusan Matematika, Fakultas Mipa Universitas Hasanuddin

Recommend Documents