BILANGAN RAMSEY UNTUK GRAF BINTANG (S5) DAN GRAF BIPARTIT LENGKAP (K3,4)

Kadek Eva Suyanti (H111 15 006)

Departemen Matematika FMIPA UNHAS

ABSTRAK

Diberikan sebarang dua graf G dan H, bilangan Ramsey graf 𝑅(𝐺, 𝐻) adalah bilangan
asli terkecil 𝑛 sedemikian sehingga untuk setiap graf 𝐹 dengan 𝑛 titik memenuhi sifat
berikut: 𝐹 memuat graf 𝐺 atau memuat 𝐻. Dalam paper ini dibahas tentang bilangan
Ramsey untuk graf bintang (𝑆5 ) terhadap graf bipartit lengkap (𝐾3,4 ). Akan ditunjukkan
bahwa batas bawah diperoleh 𝑅(𝑆5 , 𝐾3,4 ) ≥ 11 dan batas atas diperoleh 𝑅(𝑆5 , 𝐾3,4 ) ≤
11.

Keywords : Bilangan Ramsey,Graf Bintang,Graf Bipartit,Batas Bawah, dan Batas Atas.

1. PENDAHULUAN

Seiring perkembangan zaman dan kemajuan teknologi, aplikasi teori graf telah merambah
ke aneka disiplin ilmu dan membantu memudahkan orang untuk menyelesaikan permasalahan.
Penggunaan graf ditekankan untuk memodelkan persoalan. Teori graf juga sangat berguna untuk
mengembangkan model-model yang terstruktur dalam berbagai situasi. Teori graf berkembang
seiring dengan ditemukannya masalah-masalah dalam kehidupan. Beberapa masalah yang dapat
diselesaikan dengan teori graf, seperti masalah jaringan listrik, jaringan telepon, jaringan
komputer, jalan penghubung antar kota dan lain sebagainya.

Salah satu teori yang berkembang pesat dalam bidang graf adalah teori Ramsey. Teori
Ramsey pertama kali dikaji oleh Frank Plumpton Ramsey (1930). Teori ini digunakan dalam
permasalahan mencari prosedur untuk menentukan benar-tidaknya (konsistensi ) suatu formula
logika yang diberikan. Teori tersebut menjadi terkenal setelah Erdos dan Szekeres (1935)
mengaplikasikannya ke dalam teori Graf. Ramsey mendefinisikan bahwa apabila terdapat dua
buah bilangan asli 𝑎 dan 𝑏 dengan 𝑎, 𝑏 ≥ 2, maka bilangan Ramsey 𝑅(𝑎, 𝑏) adalah bilangan asli
terkecil 𝑛, sedemikian sehingga jika graf lengkap Kn dengan 𝑛 titik diwarnai dengan warna merah
atau biru, maka graf tersebut akan selalu memuat graf lengkap. 𝐾𝑎 dengan 𝑎 titik merah atau 𝐾𝑏
dengan 𝑏 titik biru sebagai subgraf. Bilangan 𝑅(𝑎, 𝑏) ini disebut sebagai bilangan Ramsey
klasik[7]. Penelitian tentang penentuan bilangan Ramsey klasik 𝑅(𝑎, 𝑏) telah memperoleh banyak
perhatian. Namun demikian, hasilnya masih jauh dari yang diharapkan. Semenjak pertama kali
diperkenalkan (1928), hanya sembilan nilai eksak bilangan Ramsey klasik 𝑅(𝑎, 𝑏) yang baru
diketahui. Konsep awal bilangan Ramsey adalah konsep bilangan Ramsey klasik dua warna yang
diberikan oleh Erdos dan Szekeres. Karena masalah ini sangat sulit, beberapa peneliti
memperumum konsep bilangan Ramsey klasik menjadi konsep bilangan Ramsey graf sebarang.
Bilangan Ramsey graf 𝑅(𝐺, 𝐻) didefinisikan sebagai bilangan bulat terkecil 𝑁 sedemikian
sehingga setiap graf 𝐹 dengan orde N akan memenuhi kondisi sebagai berikut: F memuat G
sebagai subgraf atau komplemen dari 𝐹 memuat 𝐻 sebagai subgraf[8]. Kajian penentuan bilangan
 Ramsey Graf untuk pasangan graf bintang dan bintang telah tuntas dilakukan oleh Burr dkk
(1973). Penentuan bilangan Ramsey untuk bintang dan graf bipartit lengkap juga telah dikaji,
walaupun hasilnya masih sedikit. Hal ini dilakukan oleh Harary (1972), Lawrence (1973),
𝑅(𝑆8 , 𝐾2,3 ) = 13 oleh Parson (1975), dan Rosyida (2004) memperoleh nilai eksak bilangan
Ramsey untuk bintang berorde kecil dan graf bipartite lengkap yaitu 𝑅(𝑆4 , 𝐾𝑡,𝑚 ) = 𝑡 + 𝑚 + 2
untuk 𝑡, 𝑚 ≥ 2, dan 𝑅(𝑆5 , 𝐾2,𝑚 ) = 𝑚 + 5 untuk m genap dan 𝑚 + 6 untuk m ganjil. Dengan
mengkombinasikan n,t dan m untuk n yang lebih besar n≥ 5 dan t, m ≥ 2 muncul banyak
masalah 𝑅(𝑆𝑛 , 𝐾𝑡,𝑚 ) yang masih terbuka untuk dikaji. [5]. Pada penulisan kali ini saya tertarik
untuk mencari nilai bilangan Ramsey 𝑅(𝑆5 , 𝐾3,4 ) karena masalah ini masih terbuka untuk dikaji
dan belum ada yang pernah mengkajinya terlebih dahulu.

2. TINJAUAN PUSTAKA

Definisi 2.1 (Definisi graf secara umum)

Graf 𝐺 adalah pasangan (𝑉(𝐺), 𝑋(𝐺)) dimana 𝑉(𝐺), adalah himpunan berhingga, yang elemen-
elemennya disebut titik (vertex), dan 𝑋(𝐺) adalah himpunan pasangan-pasangan dari elemen-
elemen 𝑉(𝐺) disebut sisi (edge) [6].

Definisi 2.2 Adjacent dan Incident

Sisi 𝑒 = {𝑢, 𝑣} dikatakan menghubungkan titik 𝑢 dan 𝑣 .Jika 𝑒 = {𝑢, 𝑣} adalah sisi pada graf G,
maka 𝑢 dan 𝑣 adalah titik yang terhubung langsung (adjacent), sementara itu 𝑢 dan 𝑒 sama
halnya dengan 𝑣 dan 𝑒 disebut terkait langsung (incident). Lebih jauh, jika 𝑒 1 dan 𝑒 2berbeda
pada G terkait langsung (incident) dengan sebuah titik bersama, maka 𝑒 1 dan 𝑒 2 disebut sisi
adjacent [3]

Definisi 2.3. Graf regular

Graf reguler adalah graf yang semua titiknya berderajat sama. Graf reguler dengan banyak n titik
dan derajat setiap titiknya adalah r, dinotasikan dengan r-reguler [9].

Definisi 2.4. Graf komplemen

Komplemen dari suatu graf 𝐺 , ditulis 𝐺̅ , yaitu suatu graf di mana jika 𝑢𝑣 bukan elemen E(G)
maka 𝑢𝑣 ∈ E(G) untuk setiap 𝑢, 𝑣 ∈ 𝑉(𝐺) [4].

Definisi 2.5. Sikel

Sirkuit 𝑣1 , 𝑣2 , … , 𝑣𝑛 (𝑛 ≥ 3) memiliki 𝑛 titik dengan 𝑣𝑖 adalah titik-titik berbeda untuk 1 ≤ 𝑖 ≤

𝑛 disebut sikel (Cycle) [3].

Definisi 2.6 Graf Bintang

Graf bipartisi komplit 𝐾1,𝑛 disebut graf bintang (star) dan dinotasikan dengan 𝑆𝑛 . Jadi,
𝑆𝑛 mempunyai order (𝑛 + 1) dan ukuran 𝑛 [2].

Definisi 2.7 Kardinalitas

 Misalkan 𝑆 adalah suatu himpunan. Banyaknya anggota 𝑆 disebut kardinalitas 𝑆 dinotasikan
dengan |𝑆| [6].

Definisi 2.8 Pewarnaan Titik

Pewarnaan titik pada graf 𝐺 adalah pemberian warna pada himpunan titik 𝑉(𝐺) dengan aturan
setiap titik diberi hanya satu warna dan dua titik yang bertetangga diberi warna beda [6].

Definisi 2.9 Bilangan Kromatik

Suatu graf 𝐺 dikatakan berwarna- 𝑘 jika titik-titik pada 𝐺 dapat diwarnai dengan 𝑘 warna.
Bilangan asli terkecil 𝑘 sedemikian sehingga 𝐺 berwarna 𝑘 disebut bilangan kromatik dari 𝐺,
dan dinotasikan dengan 𝑥(𝐺) [6].

Definisi 2.10 Definisi Graf Kritis

Diberikan graf 𝐺 dan 𝐻. Suatu graf 𝐹 disebut graf kritis untuk 𝐺 dan 𝐻 jika 𝐹 tidak memuat 𝐺
dan tidak memuat 𝐻. Sebarang graf kritis untuk graf 𝐺 dan 𝐻 yang memiliki 𝑛 titik dinotasikan
dengan (𝐺, 𝐻, 𝑛) –kritis [6].

Definisi 2.11 Bilangan Ramsey

Diberikan sebarang dua graf G dan H, bilangan Ramsey graf 𝑅(𝐺, 𝐻) adalah bilangan asli
terkecil 𝑛 sedemikian sehingga untuk setiap graf 𝐹 dengan 𝑛 titik memenuhi sifat berikut: 𝐹
memuat graf 𝐺 atau memuat 𝐻.

Teorema 2.1: Untuk setiap bilangan bulat 𝑛1 dan 𝑛2 , terdapat bilangan bulat terkecil
𝑀0 sedemikian sehingga jika 𝑚 ≥ 𝑀0 , maka setiap pewarnaan dua warna pada sisi-sisi graf
lengkap 𝐾𝑚 akan memuat subgraf yang semua sisinya berwarna sama dan isomorfik dengan 𝐾𝑛1
atau 𝐾𝑛2 . Bilangan 𝑀0 disebut bilangan Ramsey klasik dua warna yang selanjutnya disebut
bilangan Ramsey klasik, dan dinotasikan dengan R(𝑛1 , 𝑛2 ) atau R(𝐾𝑛1 , 𝐾𝑛2 ) [6].

Teorema 2.2: Batas bawah ChvátalHarary adalah sebagai berikut:

𝑅(𝐺, 𝐻) ≥ (𝐶(𝐺) − 1) (𝜒(𝐻) − 1) + 1

dimana 𝜒(𝐻) adalah bilangan kromatik graf 𝐻 dan 𝐶(𝐺) adalah banyaknya titik pada komponen
terbesar graf 𝐺. Batas bawah bilangan Ramsey adalah banyaknya titik pada graf kritis maksimal
untuk graf-graf yang akan dicari bilangan Ramseynya [6].

3. PEMBAHASAN

Bahwa untuk mengetahui bilangan Ramsey dapat dilakukan beberapa cara yaitu pada kali ini
kita akan menggunakan batas atas dan batas bawah.

3.1 Batas Bawah Bilangan Ramsey Pada Graf Bintang (𝑆5 ) Dan Graf Bipartite Lengkap (𝐾3,4 )
 Batas bawah bilangan Ramsey 𝑅(𝐺, 𝐻) yang diberikan oleh Chvatal dan Harary adalah
𝑅(𝐺, 𝐻) ≥ (𝜒(𝐻) − 1)(Ϲ(𝐺) – 1) + 1, dengan 𝜒(𝐻) adalah bilangan kromatik graf 𝐻 dan
Ϲ(𝐺) adalah banyaknya titik pada komponen terbesar graf 𝐺. Dengan menggunakan rumus
Chvatal-Harary untuk batas bawah bilangan Ramsey 𝑅(𝑆5, 𝐾3,4 ) yaitu sebagai berikut:
𝑅(𝑆5, 𝐾3,4 ) ≥ (𝜒(𝐾3,4) − 1)(Ϲ(𝑆5) – 1) + 1

≥ (2 − 1)(5 – 1) + 1

≥ (1)(4) + 1

𝑅(𝑆5, 𝐾3,4 ) ≥ 5

Setelah batas bawah dinaikkan diperoleh graf kritis dengan vertex 10 yaitu tidak memuat 𝑆5
dan komplemennya tidak memuat 𝐾3,4.

Teorema 𝑅(𝑆5 , 𝐾3,4 ) > 10

Untuk menunjukkan 𝑅(𝑆5 , 𝐾3,4 ) > 10 yaitu sebagai berikut :

1. Akan Ditunjukkan F Tidak Memuat 𝑆5

Bukti :

Pilih graf 𝐹dengan |𝐹| = 10 yang himpunan titik dan himpunan sisinya berturut-turut seperti
berikut :

𝑉𝐹 = {𝑉𝑖 : 1 ≤ 𝑖 ≤ 10}

Dan

𝐸𝐹 = {𝑉𝑖 𝑉𝑖+𝑗 : 𝑉𝑖 𝑉𝑖+1 , 𝑉𝑖 𝑉𝑖+5 , 𝑉𝑖 𝑉𝑖+9 }

Dengan i+j dinyatakan modulo 10. Seperti gambar berikut:

Gambar 3.1 graf K10 = ( 𝑭)

 Graf 𝐹 adalah 3-reguler yang berarti ∆(𝐹) = 3, sedangkan ∆(𝑆5 ) = 4 . Jadi terbukti bahwa 𝐹10
tidak memuat 𝑆5

2. Akan Ditunjukkan 𝐹̅ Tidak Memuat 𝐾3,4

Bukti:

Pilih graf 𝐹̅ dengan |𝐹̅ | = 10 yang himpunan titik dan himpunan sisinya berturut-turut seperti
berikut :

𝑉′𝐹̅ = {𝑉′𝑖 : 1 ≤ 𝑖 ≤ 10}

Dan

𝐸𝐹̅ = {𝑉′𝑖 𝑉′𝑖+𝑗 : 𝑉′𝑖 𝑉′𝑖+2 , 𝑉′𝑖 𝑉′𝑖+3 , 𝑉′𝑖 𝑉′𝑖+4 , 𝑉′𝑖 𝑉′𝑖+6 , 𝑉′𝑖 𝑉′𝑖+7 , 𝑉′𝑖 𝑉′𝑖+8 }

̅
Gambar 3.2 graf 𝑭

Dimana setiap tiga titik 𝑢, 𝑣, 𝑤 ∈ 𝑉′𝐹̅ yang memiliki tetangga bersama ditulis |𝑁(𝑢) ∩ 𝑁(𝑣) ∩
𝑁(𝑤)| :

|𝑁(𝑉′1 ) ∩ 𝑁(𝑉′2 ) ∩ 𝑁(𝑉′3 )| ≤ 3 |𝑁(𝑉′1 ) ∩ 𝑁(𝑉′2 ) ∩ 𝑁(𝑉′7 )| ≤ 3

|𝑁(𝑉′1 ) ∩ 𝑁(𝑉′2 ) ∩ 𝑁(𝑉′4 )| ≤ 1 |𝑁(𝑉′1 ) ∩ 𝑁(𝑉′2 ) ∩ 𝑁(𝑉′8 )| ≤ 2

|𝑁(𝑉′1 ) ∩ 𝑁(𝑉′2 ) ∩ 𝑁(𝑉′5 )| ≤ 2 |𝑁(𝑉′1 ) ∩ 𝑁(𝑉′2 ) ∩ 𝑁(𝑉′9 )| ≤ 2

|𝑁(𝑉′1 ) ∩ 𝑁(𝑉′2 ) ∩ 𝑁(𝑉′6 )| ≤ 3 |𝑁(𝑉′1 ) ∩ 𝑁(𝑉′2 ) ∩ 𝑁(𝑉′10 )| ≤ 2

Karena titik 𝑉′1 memiliki derajat dan status yang sama dengan 𝑉′𝑖 untuk setiap i = 2,3,...10
sehingga dapat dikatakan bahwa untuk setiap 𝑢, 𝑣, 𝑤 ∈ 𝑉′𝐹̅ ditulis |𝑁(𝑢) ∩ 𝑁(𝑣) ∩ 𝑁(𝑤)| ≤ 3.
Jadi 𝐹̅ tidak memuat 𝐾3,4. Sehingga diperoleh (𝑆5 , 𝐾3,4 ) > 10 atau 𝑅(𝑆5 , 𝐾3,4 ) ≥ 11.

3.2 Batas Atas Bilangan Ramsey Graf Bintang (𝑆5 Dan Graf Bipartite Lengkap (𝐾3,4 )

Penentuan batas atas bilangan Ramsey 𝑅(𝑆𝑛 , 𝐾𝑡,𝑚 ) menggunakan teorema : Misal 𝑛 ∈ 𝑁 dan
𝑛 ≥ 5. Jika 3 ≤ 𝑡 ≤ 𝑛 − 1 dan 𝑚 ≥ 2, maka 𝑅(𝑆𝑛 , 𝐾𝑡,𝑚 ) ≤ (𝑡 − 1)(𝑛 − 3) + (𝑛 − 1) +
𝑚. Dengan menggunakan teorema ini untuk menentukan batas atas bilangan Ramsey 𝑅(𝑆5, 𝐾3,4 )
itu sebagai berikut:
 𝑅(𝑆𝑛 , 𝐾𝑡,𝑚 ) ≤ (𝑡 − 1)(𝑛 − 3) + (𝑛 − 1) + 𝑚.

𝑅(𝑆5, 𝐾3,4 ) ≤ (3 − 1)(5 − 3) + (5 − 1) + 4.

𝑅(𝑆5, 𝐾3,4 ) ≤ (2)(2) + (4) + 4.
𝑅(𝑆5, 𝐾3,4 ) ≤ 12
Setelah batas atas bilangan Ramsey diturunkan diperoleh dengan vertex 11.

Teorema 𝑅(𝑆5 , 𝐾3,4 ) ≤ 11.

Bukti:
Misalkan 𝐹 adalah sebarang graf dengan |𝐹| = 11, dan andaikan 𝐹 tidak memuat 𝑆5 . Akan
ditunjukkan bahwa 𝐹̅ memuat 𝐾3,4. Misalkan setiap 𝑢 ∈ 𝐹 dengan d𝐹(𝑢) ≤ 3, sedangkan
d(𝑆5 ) = 4, maka 𝐹 tidak memuat 𝑆5 , karena ∆(𝐹) ≤ 3 akibatnya ∆(𝐹̅ ) ≥ 7. Lebih jauh, dapat
diperiksa bahwa setiap tiga titik 𝑢, 𝑣, 𝑤 ∈ 𝐹̅ , dimana |𝑁𝐹̅ (𝑢) ∩ 𝑁𝐹̅ (𝑣) ∩ 𝑁𝐹̅ (𝑤)| ≥ 4. Dengan
demikian, 𝐹̅ memuat 𝐾3,4.
3.3 Bilangan Ramsey Graf Bintang (𝑆5 ) Dan Graf Bipartite Lengkap (𝐾3,4 )
Diberikan sebarang dua graf G dan H, bilangan Ramsey graf 𝑅(𝐺, 𝐻) adalah bilangan asli
terkecil 𝑛 sedemikian sehingga untuk setiap graf 𝐹 dengan 𝑛 titik memenuhi sifat berikut: 𝐹
memuat graf 𝐺 atau memuat 𝐻. Dari batas bawah 𝑅(𝑆5 , 𝐾3,4 ) ≥ 11 dan batas atas menunjukkan
𝑅(𝑆5 , 𝐾3,4 ) ≤ 11. Sehingga diperoleh bilangan ramsey eksak graf bintang 𝑆5 dan 𝐾3,4 adalah
𝐾3,4= 11.

4. KESIMPULAN
Bilangan Ramsey untuk graf bintang (𝑆5 ) dan graf bipartite lengkap (𝐾3,4) adalah
𝑅(𝑆5 , 𝐾3,4 ) = 11. Dengan batas bawah yang telah dinaikkan diperoleh 𝑅(𝑆5 , 𝐾3,4 ) ≥ 11 dan batas
atas yang juga telah diturunkan diperoleh 𝑅(𝑆5 , 𝐾3,4 ) ≤ 11.

5. DAFTAR PUSTAKA

[1] Abdullah Bin Muhammad.2007. Tafsir Ibnu Katsir Jilid 6. Bogor: Pustaka Imam Asy-Syafii

[2] Abdussakir, dkk. 2009. Teori Graf. Malang: UIN Press

[3] Chatrand, Gery and Lesniak, Linda. 1986. Graphs and Digraphs Second Edition. California: a
Division of Wadsworth.Inc.

[4] Diestel, Reinhard. 2005. Graph Theory, Electronic Edition 3. New York.

[5] Hasmawati. 2008. Bilangan Ramsey untuk Graf Gabungan Bintang. Disertasi Departemen
Matematika ITB, Indonesia.

[6] Hasmawati. 2015. Bahan Ajar Teori Graf. Prodi Matematika,Departemen Matematika, FMIPA
Universitas Hasanuddin,Makassar.
[7] Jondesi.2012. Syarat Perlu Untuk Graf Ramsey (2k2,Cn)-Minimal. Program Studi
Matematika,FMIPA Universitas Andalas Padang,Indonesia

[8] Luthfiyah,Deny.2008.Menentukan Bilangan Ramsey r(m,n) Dengan m,n Bilangan Asli. Skripsi
Jurusan Matematik UIN, Malang.

[9] X. Li dan Y. Sun. 2010. Rainbow connection numbers of complementary graphs,

arXiv:1011.4572v3 [math.CO].