Scribd Logo
Unggah

Selamat datang di Scribd!

  • 2 tayangan

    MTK Diskrit Klp.5

    Diunggah oleh

    Siti Nur Khalimah

    Hak Cipta:

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

    MTK Diskrit Klp.5

    Diunggah oleh

    Siti Nur Khalimah
    2 tayangan13 halaman

    Judul Asli

    Ppt Mtk Diskrit Klp.5

    Hak Cipta

    © © All Rights Reserved

    Format Tersedia

    PPTX, PDF, TXT atau baca online dari Scribd

    Apakah menurut Anda dokumen ini bermanfaat?

    Apakah konten ini tidak pantas?

    Hak Cipta:

    © All Rights Reserved
    Unduh sebagai PPTX, PDF, TXT atau baca online dari Scribd
    Unduh sebagai pptx, pdf, atau txt
    2 tayangan13 halaman

    MTK Diskrit Klp.5

    Diunggah oleh

    Siti Nur Khalimah

    Hak Cipta:

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

    GRAPH PLANAR

    Di susun oleh:
    Shauna Misriyani
    Vina Indriani
    Eyi Triutami
    Desi Ratna Sari
    Aprilia Sartika
    Graph Planar Dan Graph Bidang

    Graph yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling
    memotong (bersilangan) disebut graph planar.
    • jika tidak, maka ia disebut graph tak-planar.
    • adalah graph planar
    Contoh:
    Graph Planar Dan Graph Bidang
    GRAF BIDANG
    Graf planar yang digambarkan dengan sisi- sisi yang tidak saling bertindihan
    disebut graf bidang.
    Graf (a), (b), (c) adalah graf planar Graf (b), (c) adalah graf bidang.
    Contoh:
    Pembuktian graph dan Non Planar

    • Graph
    adalah graf dengan 5 simpul, dengan satu sisi di antara setiap pasangan simpul.

    • Contoh Graph

    Grap C Graph D

    Grap C adalah Graph Non planar karena tidak dapat di gambarkan pada bidang datar
    sehingga sisi sisinya ada yang saling berpotongan seperti Graph D
    Pembuktian graph dan Non Planar

    • Graph
    adalah graf dengan 6 simpul dalam dua himpunan 3, dengan satu sisi di antara setiap
    pasangan simpul dari himpunan yang berlawanan.

    • Contoh Graph

    Graph Pada graph (a) bukan termasuk graph planar karena jika ingin di gambarkan
    ulang tetap akan menemukan sisi yang berpotongan seperti pada graph (b).
    Keterhubungan Graph
    • Keterhubungan titik
    • Keterhubungan sisi
    K(G) adalah simpul minimum yang dapat dihapus agar menjadi graf tidak terhubung.

    K(G) untuk graf komplit berlaku : K(G) = n – 1


    Keterhubungan Graph
    • Keterhubungan titik
    • Keterhubungan sisi
    X(G) adalah jumlah sisi minimum yang dapat di hapus agar menjadi graf tidak
    terhubung

    SIMPUL PEMOTONG, simpul yang menyebabkan graf menjadi tidak terhubung


    FORMULA EULER
    • Sisi-sisi pada graf bidang membagi bidang datar menjadi
    beberapa wilayah (region) atau muka (face).
    • Graf bidang pada gambar di bawah ini terdiri atas 6
    wilayah (termasuk wilayah terluar):
    Pertidaksamaan Euler
    Pada graf planar sederhana terhubung dengan f buah
    wilayah, n buah simpul, dan e buah sisi (e > 2) selalu
    berlaku ketidaksamaan Euler:e <= 3n – 6
    • Ketidaksamaan ini dapat digunakan untuk menunjukkan
    keplanaransuatu graf sederhana
    • Jika sebuah graf planar, maka ia memenuhi
    ketidaksamaan Euler,sebaliknya jika tidak planar maka
    ketidaksamaan tersebut tidak dipenuhi.
    Pertidaksamaan Euler
    Contoh :

    Pada K, n = 4, e = 6, memenuhi ketidaksamaan Euler, sebab


    6≤3(4)-6.Jadi, K, adalah graf planar.
    Pada graf Ks, n = 5 dan e = 10, tidak memenuhi ketidaksamaan
    Euler sebab 10 ≥ 3(5)-6
    Graph Dual
    Graph dual adalah graph yang diperoleh dari suatu graph bidang dengan
    cara setiap daerah diwakili dengan satu titik, dan antar titik akan
    terhubung langsung jika daerah tersebut saling berbatasan langsung.
    Cara membuat dual dari graf planar:
    1. Pada setiap wilayah/muka di G. buatlah simpul v yang merupakan
    simpul di G*
    2. Untuk setiap sisi e di G, tariklah sisi e* (yang menjadi sisi untuk G*)
    yang memotong sisi e tersebut. Sisi e* menghubungkan dua buah
    simpul v1* dan v2* (simpul-simpul di G*). Untuk sisi e yang salah
    satu simpulnya merupakan simpul berderajat 1 (jadi sisi e
    seluruhnya terdapat di dalam sebuah muka), maka sisi e* berupa
    sisi gelang.
    Graph Dual
    Thankyou for your
    ()

    attention

    Anda mungkin juga menyukai