Bilangan Ramsey r(Km, Sn)

Ghufron, Muh Ali (2012) Bilangan Ramsey r(Km, Sn). Undergraduate thesis, Universitas Islam Negeri Maulana Malik Ibrahim.

[img]
Preview
Text (Fulltext)
07610074.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (3MB) | Preview

Abstract

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.

Item Type: Thesis (Undergraduate)
Supervisor: Irawan, Wahyu Hengky and Nashichuddin, Achmad
Keywords: Ramsey Numbers; Complete Graph; Star Graph; Bilangan Ramsey; Graf Komplit; Graf Bintang
Subjects: 01 MATHEMATICAL SCIENCES > 0101 Pure Mathematics > 010101 Algebra and Number Theory
01 MATHEMATICAL SCIENCES > 0101 Pure Mathematics > 010199 Pure Mathematics not elsewhere classified
Departement: Fakultas Sains dan Teknologi > Jurusan Matematika
Depositing User: M. Muzakir
Date Deposited: 30 May 2017 03:15
Last Modified: 30 May 2017 03:15
URI: http://etheses.uin-malang.ac.id/id/eprint/6768

Actions (login required)

View Item View Item