Tugas Bilangan Ramsey Example 11.7

  • Published on
    22-Nov-2015

  • View
    10

  • Download
    4

Embed Size (px)

DESCRIPTION

Bilangan Ramsey Teori Graf

Transcript

<p>Tugas IndividuTeori Graf</p> <p>BILANGAN RAMSEY</p> <p>Nama : Christian BerenNIM : H12112276</p> <p>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</p> <p>V2V1</p> <p>V7V3</p> <p>V6V4</p> <p>V5</p> <p>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.</p> <p>V2V1</p> <p>V7V3</p> <p>V6V4</p> <p>V5</p> <p>Karena asumsinya salah (kontradiksi), maka syarat terpenuhi.</p> <p>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:</p> <p>V2V1</p> <p>V3V6V5V4</p> <p>Karena graf di atas tidak mengandung yang berwarna biru dan yang berwarna merah, maka syarat terpenuhi.</p> <p>Karena syarat dan terpenuhi, maka diperoleh bilangan Ramsey .</p>