Nisa, Fakhrun (2020) Penentuan graf ramsey (P3, C6)- minimal / Fakhrun Nisa. Masters thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Konsep graf Ramsey minimal pertama kali diperkenalkan oleh Burr dkk (1976). Konsep tersebut merupakan salah satu konsep yang diperoleh dari penerapan teori Ramsey ke dalam teori graf. Suatu graf disebut graf Ramsey dari pasangan graf jika diberi sebarang pewarnaan pada sisi-sisi dari graf misal merah dan biru menghasilkan subgraf berwarna merah yang isomorfik dengan graf atau subgraf berwarna biru yang isomorfik dengan graf . Jika graf tersebut juga memenuhi syarat keminimalan yaitu untuk sebarang sisi graf memiliki pewarnaan merah-biru yang tidak menghasilkan subgraf berwarna merah yang isomorfik dengan graf dan subgraf berwarna biru yang isomorfik dengan graf maka graf disebut graf Ramsey minimal. Himpunan yang memuat semua graf Ramsey (G H)-minimal dinotasikan dengan . Pada tahun 2005 Borowiecki dkk. memperoleh graf-graf yang termasuk dalam . Selain itu pada tahun 2008 Baskoro dkk. memperoleh graf baru yang merupakan graf Ramsey -minimal berdiameter 2 dan kemudian pada tahun 2010 Vetrik dkk. memperoleh kelas tak berhingga dari dengan diameter 4. Pada tahun 2013 Ahsanunnisa dalam kajiannya memperoleh beberapa graf yang termasuk dalam . Berdasarkan kajian-kajian sebelumnya mengenai graf Ramsey minimal belum ada yang mengkaji graf Ramsey minimal dari pasangan graf lintasan dan graf siklus . Dengan demikian penelitian ini bertujuan untuk menentukan syarat perlu untuk graf Ramsey minimal dari pasangan graf lintasan dan graf siklus untuk serta menentukan graf yang termasuk graf Ramsey minimal dari pasangan graf lintasan dan graf siklus . Penelitian ini menggunakan metode studi literatur yaitu dengan mempelajari kajian sebelumnya yang berkaitan dengan graf Ramsey minimal khususnya dari pasangan graf lintasan dan graf siklus. Dengan memahami sifat umum dari graf Ramsey minimal dari pasangan graf lintasan dan graf siklus dapat ditentukan syarat perlu untuk (P3 Cn) untuk . Selanjutnya asumsikan terdapat suatu graf terhubung yang tidak memuat daun atau jembatan dan memiliki subgraf siklus . Jika diberi pewarnaan sebarang pada graf dan memenuhi sifat umum dari graf Ramsey minimal maka graf termasuk graf Ramsey -minimal. Sebaliknya jika tidak memenuhi sifat graf Ramsey minimal maka graf bukan merupakan graf Ramsey -minimal. Hasil dari penelitian ini yaitu diperoleh dua lema yang merupakan syarat perlu untuk graf yang termasuk dalam himpunan graf Ramsey (P_3 C_n)-minimal untuk n lebih besar dari atau sama dengan 3. Selain itu diperoleh 4 teorema yang menyatakan beberapa graf dengan titik tertentu yang merupakan graf Ramsey (P_3 C_6)-minimal.
| Item Type: | Thesis (Masters) |
|---|---|
| Subjects: | ?? ?? |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S2 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 29 Apr 2020 04:29 |
| Last Modified: | 09 Sep 2020 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/159089 |
Actions (login required)
 |
View Item |