Tugas IndividuTeori Graf

BILANGAN RAMSEY

Nama : Christian BerenNIM : H12112276

Jurusan MatematikaFakultas Matematika dan Ilmu Pengetahuan AlamUniversitas Hasanuddin2014Halaman 301Example 11.7 Tunjukkan Penyelesaian :Ada 2 syarat untuk menunjukkan bahwa , yaitu:1. , dimana pada pewarnaan merah-biru graf , terdapat yang berwarna merah atau yang berwarna biru.Diasumsikan bahwa pewarnaan menghasilkan yang tidak berwarna merah dan yang tidak berwarna biru. Anggap himpunan titik-titik pada adalah v1, v2, v3, v4, v5, v6, v7, dan misalkan diambil titik v1. Maka paling banyak terdapat 2 sisi berwarna merah yang bertetangga dengan v1 (misalkan v6 dan v7), dan minimal terdapat 4 sisi berwarna biru yang bertetangga dengan v1 (misalkan v2, v3, v4, v5). Jika terdapat sisi berwarna biru yang menghubungkan 2 titik di {v2, v3, v4, v5}, maka diperoleh graf yang berwarna biru yaitu (v1v2, v2v3, v1v3), yang mana hal ini kontradiksi dengan asumsi bahwa tidak diperoleh yang berwarna biru

V2V1

V7V3

V6V4

V5

Kemudian, apabila semua sisi yang menghubungkan 2 titik di {v2, v3, v4, v5} diberi warna merah. Misalnya sisi v2v3, v2v4, dan v2v5 berwarna merah, maka diperoleh graf berwarna merah (yaitu v2v3, v2v4, dan v2v5), yang mana hal ini kontradiksi dengan asumsi bahwa tidak diperoleh yang berwarna merah.

V2V1

V7V3

V6V4

V5

Karena asumsinya salah (kontradiksi), maka syarat terpenuhi.

2. , dimana pada pewarnaan merah-biru graf , tidak terdapat yang berwarna merah dan yang berwarna biru.Misalnya warna merah, dan warna biru. Akan dihindari pewarnaan biru, maka yang diperoleh adalah sebagai berikut:

V2V1

V3V6V5V4

Karena graf di atas tidak mengandung yang berwarna biru dan yang berwarna merah, maka syarat terpenuhi.

Karena syarat dan terpenuhi, maka diperoleh bilangan Ramsey .