Bilangan Ramsey r(Km, Sn)

INDONESIA:

Bilangan Ramsey pertama kali ditemuka oleh “Frank Ramsey”. Ide dasar bilangan Ramsey ini adalah “untuk setiap bilangan bulat positif m dan n, bilangan Ramsey r(m,n) adalah bilangan bulat positif terkecil p sedemikian sehingga untuk setiap graf G dengan order p, salah satu dari G memuat sebagai subgraf atau memuat Kn sebagai subgraf”. Saat pertama kali bilangan Ramsey ditemukan penelitian-penelitian yang dilakukan hanya seputar pada graf komplit saja. Skripsi ini akan membahas bilangan Ramsey untuk graf komplit Km dan graf bintang Sn atau bentuk lain dari graf bipartisi komplit K_1,n dengan m=2,3,4 dan n adalah bilangan asli dan dinotasikan dengan r(Km,Sn). Dalam perkembangan selanjutnya, bilangan Ramsey tidak hanya membicarakan graf komplit saja bahkan menyangkut dua graf yang berbeda, yang disebut dengan generalisasi bilangan Ramsey.

Generalisasi bilangan Ramsey adalah “diberikan dua graf F dan H, bilangan Ramsey r(F,H) adalah bilangan bulat positif terkecil sedemikian sehingga untuk setiap graf G dengan order n memenuhi kondisi G memuat F sebagai subgraf atau G ̅ memuat H sebagai subgraf”.

Untuk pertama kali yang akan diteliti adalah bilangan Ramsey r(K_2,Sn) sampai r(K_2,Sn), dengan menggambarkan sebarang graf G dengan titik mulai dari satu. Dilanjutkan dengan membuat teorema untuk bilangan Ramsey. Kemudian meneliti bilangan Ramsey dan. Dari hasil penelitian ini didapatkan bilangan Ramsey r(K_2,Sn)=2n+1, bilangan Ramsey r(K_4,Sn)=3n+1, dan bentuk umum bilangan Ramsey r(Km,Sn)=(m-1)n+1.

ENGLISH:

Numbers ramsey first discovered by "FRANK RAMSEY". The basic idea ramsey numbers is “let and be two positive integers. The Ramsey number is the least positive integes with the property that if is any graph of order, then either contains mutually adjacent vertices for or contains mutually nonadjacent vertices, that is, contains as subgraph or contains as subgraph.”. When was first discovered ramsey number studies done just about the only complete graph. This thesis will discuss the ramsey numbers for complete graphs and star graphs.

Generalized Ramsey numbers is let and be two graph, the Ramsey number is the least positive integer such that if is any graph of order , then either is a subgraph of, or is a subgraph of.

For the first time that will be examined is the Ramsey number with describe any graph g with the starting point of one. ollowed by making lemma for Ramsey numbers. Then examined the Ramsey number and
From the results of this research, a common form Ramsey numbers r(K2, Sn ) = n + 1, Ramsey numbers r(K3, Sn ) = 2n + 1 common forms and common forms Ramsey numbers r(K4, Sn ) = 3n + 1. Once it can be searched common form Ramsey number.