Masalah Bilangan Ramsey: Teori Graf

Hai sobat matematika...

Pada sebuah pesta yang akan diadakan, seseorang bernama Ramsey mengundang lima orang. Jadi pesta dihadiri enam orang.

Lalu muncul teka teki di pesta Ramsey

Tunjukkan bahwa pada sebarang pesta dengan enam orang, terdapat tiga orang yang saling kenal atau tidak orang yang tidak saling kenal.

Matematika sebagai bahasa universal dapat memecahkan teka teki semacam ini. Masalah Ramsey tersebut terkenal dalam teori graf, cabang matematika yang membahas titik dan garis.

Teori Graf, Ulasan Sekilas

Graf dalam matematika didefinisikan dengan pasangan himpunan berurutan \(\boldsymbol{G = \left(V,E\right)}\) dari himpunan titik \(V\left(G\right)\) dan himpunan sisi \(E\left(G\right)\).

Suatu titik \(v\) anggota dari himpunan \(V\) dikatakan bertetangga dengan titik \(u\) jika dan hanya jika terdapat sisi \(uv\) anggota dari \(E\) di dalam graf \(E\).

Suatu graf yang sebarang dua titik di dalamnya bertetangga disebut graf lengkap. Graf lengkap dengan \(n\) titik dinotasikan dengan \(\boldsymbol{K_{n}}\). Misalkan graf lengkap \(K_{3}\) berikut.

Komplemen suatu graf \(G\), dinotasikan dengan \(\boldsymbol{\overline{G}}\), adalah graf yang mempunyai himpunan titik \(V\left(G\right)\) namun dua titik bertetangga di \(\overline{G}\) jika dan jika dua titik tersebut tidak bertetangga di \(G\).

Baca Juga : Apa sih itu graf pohon ?

Masalah ramsey tersebut digambarkan sebagai graf \(G\) dengan enam titik sebagai enam orang dan sisi di dalam graf \(G\) merepresentasikan hubungan saling kenal.

Jadi masalah ramsey merupakan salah kasus dalam bilangan ramsey, dan dapat dinyatakan pada teorema berikut

Teorema

Untuk sebarang graf \(G\) dengan enam titik, maka graf \(G\) atau komplemen \(\overline{G}\) memuat \(K_{3}\)

Bukti. Misalkan titik \(v\) adalah titik di dalam \(G\) di atara enam titik. Karena titik \(v\) bertetangga di \(G\) atau kalau tidak di \(\overline{G}\) dengan kelima titik yang lainnya. Tanpa mengurangi keumuman, misalkan titik \(v\) bertetangga dengan tiga titik \(u_{1}\), \(u_{2}\), dan \(u_{3}\).
Jika dua di antara ketiga titik ini bertetangga, maka dua titik tersebut berada di \(K_{3}\) yang titik ketiga adalah \(v\). Namun, jika tidak ada dari dua titik tersebut yang bertetangga, maka ketiga titik \(u_{1}\), \(u_{2}\), dan \(u_{3}\) saling bertetangga di komplemen graf \(\overline{G}\) membentuk graf \(K_{3}\). \(\blacksquare\).

Jadi pembuktian teorema di atas menunjukkan bahwa setiap pesta yang terdiri dari enam orang dijamin ada tiga orang saling kenal atau tiga orang yang saling tidak saling kenal.

Bilangan Ramsey

Peryataan yang terdapat pada teorema di atas menimbulkan pertanyaan

Berapakah bilangan bulat terkecil \(r(m,n)\) sedemikian sehingga graf \(G\) dengan \(r(m,n)\) titik memuat \(K_{m}\) atau \(\overline{K}_{n}\)?

Nilai \(\boldsymbol{r(m,n)}\) dinamakan Bilangan Ramsey. Pencarian bilangan ramsey ini pada faktanya merupakan masalah yang belum terpecahkan.

Namun, beberapa peniliti menemukan batas atas dari bilangan ramsey. Di antaranya Erdos dan Szekeres di dalam jurnalnya menemukan batas tersebut, yaitu
\[r(m,n) \leq
\left(\begin{array}{cc}
m+n-2\\m-1
\end{array}\right)\]Peneliti lain, mendata beberapa bilangan ramsey ini di dalam artikel review dan menghasilkan beberapa bilangan ramsey berikut

Tentunya, bilangan ramsey ini banyak menarik beberapa peneliti lain untuk menemukan dan menganalisa beberapa sifatnya pada berbagai macam graf.

Perumuman bilangan ramsey dinotasikan dengan\[\boldsymbol{R\left(n_{1},n_{2},\ldots,n_{r}\right)}\]yang dikenalkan oleh Grenwood dkk dalam jurnal mereka.

Bilangan Ramsey tersendiri merupakan kasus khusus dalam teori graf dari teorema Ramsey yang merupakan masalah dalam pewarnaan sisi pada suatu graf.

Baca Juga : Pembahasan Soal Pengantar Teori Graf

Kesimpulan

Bilangan ramsey sebagai salah satu topik dalam matematika memberikan jaminan masalah pada suatu pesta yang menjamin hubungan saling kenal di antara peserta pesta.

Pada artikel ini, kita membahas pesta yang dihadiri enam orang akan menjamin tiga orang saling kenal atau tiga orang yang tidak saling kenal.

Masalah Bilangan Ramsey: Teori Graf

4/ 5

Oleh Mohammad Mahfuzh Shiddiq

Mohammad Mahfuzh Shiddiq September 23, 2019 Komentar