Scribd Logo
Unggah

Selamat datang di Scribd!

  • 569 tayangan

    Teori Graf: Teorema Turan

    Diunggah oleh

    Petrina Talita
    Teorema Turan menyatakan bahwa graf terbesar dengan n titik dan bilangan kromatik k adalah graf k-partit lengkap, dimana titik-titik dibagi menjadi k kelompok dan setiap titik dalam satu kelompok bertetangga dengan setiap titik pada kelompok lainnya. Teorema ini membuktikan bahwa graf Turan, Tn,k merupakan graf terbesar dengan sifat tersebut.

    Hak Cipta:

    © All Rights Reserved
    Unduh sebagai PDF, TXT atau baca online dari Scribd

    Teori Graf: Teorema Turan

    Diunggah oleh

    Petrina Talita
    569 tayangan23 halaman
    Teorema Turan menyatakan bahwa graf terbesar dengan n titik dan bilangan kromatik k adalah graf k-partit lengkap, dimana titik-titik dibagi menjadi k kelompok dan setiap titik dalam satu kelompok bertetangga dengan setiap titik pada kelompok lainnya. Teorema ini membuktikan bahwa graf Turan, Tn,k merupakan graf terbesar dengan sifat tersebut.

    Deskripsi Asli:

    Paul Turan's Theorem

    Hak Cipta

    © © All Rights Reserved

    Format Tersedia

    PDF, TXT atau baca online dari Scribd

    Apakah menurut Anda dokumen ini bermanfaat?

    Apakah konten ini tidak pantas?

    Teorema Turan menyatakan bahwa graf terbesar dengan n titik dan bilangan kromatik k adalah graf k-partit lengkap, dimana titik-titik dibagi menjadi k kelompok dan setiap titik dalam satu kelompok bertetangga dengan setiap titik pada kelompok lainnya. Teorema ini membuktikan bahwa graf Turan, Tn,k merupakan graf terbesar dengan sifat tersebut.

    Hak Cipta:

    © All Rights Reserved
    Unduh sebagai PDF, TXT atau baca online dari Scribd
    Unduh sebagai pdf atau txt
    569 tayangan23 halaman

    Teori Graf: Teorema Turan

    Diunggah oleh

    Petrina Talita
    Teorema Turan menyatakan bahwa graf terbesar dengan n titik dan bilangan kromatik k adalah graf k-partit lengkap, dimana titik-titik dibagi menjadi k kelompok dan setiap titik dalam satu kelompok bertetangga dengan setiap titik pada kelompok lainnya. Teorema ini membuktikan bahwa graf Turan, Tn,k merupakan graf terbesar dengan sifat tersebut.

    Hak Cipta:

    © All Rights Reserved
    Unduh sebagai PDF, TXT atau baca online dari Scribd
    Unduh sebagai pdf atau txt
    dari 23

    TEOREMA TURAN

    Disusun oleh:
    ALIF RAHMAN NASRUL (140210101046)
    PETRINA TALITA PUTRI (140210101048)
    LUSIA DEWI MINARTI (140210101051)
    TEOREMA TURAN : PENGENALAN
    Teorema Turan dicetuskan oleh Paul Turan pada tahun 1941. Teorema Turan merupakan
    hasil dari studi mengenai teori graf ekstrim (extreme graph theory). Extreme graph
    theory adalah bagian dari teori graf yang mempelajari kasus-kasus ekstrim (maksimum
    atau minimum) yang dapat terjadi pada graf dengan sifat-sifat tertentu. Biasanya, kata
    graf maksimum atau graf terbesar mengacu pada sebuah graf sederhana dengan sisi
    terbanyak yang dapat dibuat berdasarkan banyak titik yang diberikan (Medina. 2013).
    Sebelum mempelajari mengenai teorema Turan, hal yang perlu
    diketahui terlebih dahulu adalah sebuah graf dibentuk dari
    himpunan titik tak kosong () dan himpunan sisi yang
    menghubungkan titik-titik tersebut.

    Berikut adalah beberapa graf sederhana yang berkaitan dengan


    Teorema Turan
    GRAF LENGKAP
    Sebuah graf sederhana yang mana di dalamnya tiap-tiap pasangan titik (simpul) yang berbeda
    saling bertetangga disebut graf lengkap (complete graph). Kita melambangkan graf lengkap
    yang memiliki simpul dengan . Graf 3 , 4 dan 5 diperlihatkan dalam Gambar 2. Graf
    1
    memiliki sebanyak ( 1) sisi (Wilson. 2010: 19).
    2

    Gambar 2. Graf , dan


    GRAF BIPARTIT
    Jika himpunan simpul dari suatu graf dapat dibagi menjadi dua buah himpunan dan yang
    tak berhubungan, sehingga tiap-tiap rusuk terhubung ke sebuah simpul dalam himpunan dan
    sebuah simpul dalam himpunan , maka disebt graf bipartit (bipartite graph) (lihat Gambar 3).
    Kita dapat menuliskan = (, ) bila kita hendak menyatakan secara eksplisit himpunan dan
    dari .

    Gambar 3. (, )
    Sebuah Graf Bipartit Lengkap (Complete Bipartite Graph) adalah graf bipartit dimana
    tiap simpul dalam A terhubung ke tiap-tiap simpul dalam B oleh tepat satu buah sisi saja.
    Kita melambangkan graf bipartit lengkap yang memiliki simpul kuning dan simpul
    merah dengan , . Graf 3,5 diperlihatkan dalam Gambar 4. Graf , memiliki sebanyak
    + simpul dan sisi (Wilson. 2010: 20-21).
    PERMASALAHAN 1
    Temukan sebuah graf terbesar (maksimum) dengan titik dan bilangan kromatik 2.

    G memiliki bilangan kromatik 2, kita misalkan titik-titiknya diberi warna 2


    macam warna, misal merah dan biru. Untuk menemukan sebuah graf sederhana
    dengan sisi terbanyak, jika terdapat sebuah titik berwarna merah yang tidak
    bertetangga dengan titik berwarna biru, maka kita dapat menghubungkannya sehingga
    banyak sisi (size/ukuran) dari graf semakin bertambah. Dari hal tersebut maka akan
    terbentuk sebuah graf dimana setiap titik berwarna biru bertetangga/dihubungkan
    dengan setiap titik berwarna merah. Dengan kata lain graf yang terbentuk
    merupakan graf bipartit lengkap.
    PERMASALAHAN 2
    Temukan sebuah graf terbesar (maksimum) dengan titik dan bilangan kromatik .
    Permasalahan 2 merupakan pembuktian dari teorema 4.1.1 berikut.
    Pertama-tama akan dibuktikan kasus khusus untuk Teorema Turan dimana = 2 sebagai
    berikut.
    Buat sebuah graf baru dengan himpunan yang sama dengan graf dan misalkan
    juga subset dari sama seperti diatas, sedemikian hingga pada setiap titik di
    bertetangga dengan setiap titik di , dan tidak ada sisi lainnya lagi pada . Dengan kata lain,
    akan membentuk sebuah graf bipartit lengkap.

    Jika adalah sebuah titik di , maka


    = = () ()
    Karena telah kita dimisalkan sebagai titik dengan derajat maksimal pada . Misalkan
    bahwa banyaknya titik pada adalah , maka jika adalah sebuah titik ,
    = ()

    Karena kita telah menunjukkan bahwa tidak ada dua titik di yang akan saling bertetangga
    di . Kemudian kita menemukan sebuah graf baru sedemikian hingga untuk setiap titik
    di , (). Artinya, banyaknya sisi di haruslah sedikitnya adalah
    banyaknya sisi di . adalah graf bipartit lengkap dan telah dibuktikan pada teorema 4.1.1
    bahwa graf bipartit lengkap terbesar dengan n titik adalah 1,2 dengan = 1 + 2 dan
    1 2 1 (terbukti).
    Pembuktian yang lebih umum untuk teorema 4.2.1 membutuhkan lemma berikut yang
    diperoleh dari pembuktian teorema 4.1.2*.
    Teorema 4.1.2 dibuktikan sebagai berikut. Lemma 4.1.3 menunjukkan bahwa
    jika adalah sebuah graf pada n titik yang tidak mengandung sebuah subgraf
    isomorfik +1 , maka dapat digantikan oleh sebuah graf -partit dengan titik dan
    sisi yang sama seperti pada . Karena graf -partit terbesar dengan titik adalah
    graf -partit lengkap seperti yang telah dibuktikan pada teorema 4.1.1, maka
    teorema 4.1.2 telah terbukti.
    Jika dan diketahui, maka graf terbesar yang terbentuk disebut sebagai Graf
    Turan dengan notasi , .
    CONTOH SOAL
    LATIHAN SOAL
    PEMBAHASAN 1
    PEMBAHASAN 2
    PEMBAHASAN 2
    TERIMA KASIH

    Anda mungkin juga menyukai