Scribd Logo
Unggah

Selamat datang di Scribd!

  • 398 tayangan

    GRAF Isomorfik Dan Planar

    Diunggah oleh

    fatimah
    Tiga konsep utama graf yang dibahas dalam dokumen ini adalah graf isomorfik, graf planar, dan rumus Euler untuk graf planar. Graf isomorfik adalah dua graf yang memiliki jumlah simpul dan garis yang sama beserta derajat simpul yang setara. Graf planar adalah graf yang dapat digambar di bidang datar tanpa saling potong. Rumus Euler menyatakan hubungan antara jumlah simpul, garis, dan wilayah pada graf planar.

    Hak Cipta:

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

    GRAF Isomorfik Dan Planar

    Diunggah oleh

    fatimah
    398 tayangan17 halaman
    Tiga konsep utama graf yang dibahas dalam dokumen ini adalah graf isomorfik, graf planar, dan rumus Euler untuk graf planar. Graf isomorfik adalah dua graf yang memiliki jumlah simpul dan garis yang sama beserta derajat simpul yang setara. Graf planar adalah graf yang dapat digambar di bidang datar tanpa saling potong. Rumus Euler menyatakan hubungan antara jumlah simpul, garis, dan wilayah pada graf planar.

    Deskripsi Asli:

    Graf lanjutan

    Judul Asli

    GRAF Isomorfik dan Planar

    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?

    Tiga konsep utama graf yang dibahas dalam dokumen ini adalah graf isomorfik, graf planar, dan rumus Euler untuk graf planar. Graf isomorfik adalah dua graf yang memiliki jumlah simpul dan garis yang sama beserta derajat simpul yang setara. Graf planar adalah graf yang dapat digambar di bidang datar tanpa saling potong. Rumus Euler menyatakan hubungan antara jumlah simpul, garis, dan wilayah pada graf planar.

    Hak Cipta:

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

    GRAF Isomorfik Dan Planar

    Diunggah oleh

    fatimah
    Tiga konsep utama graf yang dibahas dalam dokumen ini adalah graf isomorfik, graf planar, dan rumus Euler untuk graf planar. Graf isomorfik adalah dua graf yang memiliki jumlah simpul dan garis yang sama beserta derajat simpul yang setara. Graf planar adalah graf yang dapat digambar di bidang datar tanpa saling potong. Rumus Euler menyatakan hubungan antara jumlah simpul, garis, dan wilayah pada graf planar.

    Hak Cipta:

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

    GRAF

    Fatimah Putri Jarir


    1910501046
    Nabhan Ghiyats Bagas P 1910501059
    Peta Konsep

    Graf

    Graf Isomorfik Graf Planar

    Rumus euler
    Graf Isomorfik : Pengertian

    Dua buah graf yang sama


    tetapi secara geometri
    berbeda

     Syarat : Jumlah simpul sama

    Jumlah garis sama

    Derajat yang sama dari simpul-


    simpulnya
    Graf Isomorfik : Contoh
    Graf Isomorfik : Contoh (1)
    Graf Isomorfik : Graf Tidak Isomorfik
    Catatan :
    Jika dua graf yang berbeda tidak memiliki
    salah satu dari syarat, pasti tidak isomorfis.
    Tetapi walaupun kedua graph tersebut
    memiliki seluruh syarat diatas belum tentu Ada 2 graf yang memenuhi
    juga keduanya isomorfis. syarat, tetapi tidak
    isomorfis. Contoh :

    Dalam G, titik yang berderajat 3 adalah titik


    x. Titik x dihubungkan dengan 2 titik lain
    yang berderajat 1 (titik y dan z).
    Dalam G', titik yang berderajat 3 adalah c.
    titik berderajat 1 yang dihubungkan dengan c
    hanyalah titik d. Jadi, G tidak mungkin
    isomorfis dengan G'.
    Graf Isomorfik : Syarat +
    Syarat tambahan :

    Graf sederhana G1= (V1, E1) dan G2= (V2, E2) adalah isomorfis jika ada
    sebuah fungsi bijektif dari V1 ke V2

    Misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e’ yang
    berkoresponden di G2 harus bersisian dengan simpul u’ dan v’ yang di G2.

    G1 dan G2 adalah isomorfis jika simpul-simpulnya dapat diurut dengan cara


    sedemikian rupa sehingga matriks ketetanggaan M G1dan M G2 adalah identik.
    Graf Isomorfik : Matriks
    Ketetanggaan
    Contoh 1 :
    Contoh 2 :

    • Apakah Graf tersebut berkorespondensi?


    • Bagaimana cara menentukan isomorfik atau tidaknya?
    Graf Planar : Pengertian & contoh

    Graf yang dapat digambarkan


    pada bidang datar dengan sisi-
    Contoh : sisi tidak saling memotong
    (bersilangan)

    Contoh Graf Planar Contoh Graf tidak Planar


    Graf Planar : Graf Bidang

    Graf planar yang digambarkan dengan sisi-sisi


    yang tidak saling berpotongan disebut graf
    bidang (plane graph).
    (a). Masih
    berpotongan atau
    belum dapat
    disebut graf bidang

    (b). Penggambaran
    kembali graf (a)
    yang tidak saling
    berpotongan, jadi
    dapat disebutGraf
    Bidang

    (c). Graf Bidang


    Graf Planar : Persoalan Utilitas

    Pengaplikasian Graf Planar : Persoalan Utilitas

    Keterangan :

    H1 = Rumah pertama W = air


    H2 = Rumah Kedua G = Gas
    H3 = Rumah Ketiga E = listrik

    Saat digambar ulang, ternyata tidak mungkin sisi yang tidak saling
    berpotongan. Maka, persoalan utilitas TIDAK PLANAR
    Graf Planar : Wilayah (f)

    Sisi pada graf bidang membagi bidang


    datar menjadi beberapa wilayah/muka.

    Termasuk wilayah luar

    Jumlah wilayah (f) pada graf planar sederhana juga dapat dihitung dengan
    rumus ; Rumus Euler
    Graf Planar : Rumus Euler

    n–e+f=2 f=e–n+2

    DIK : e = 11
    n=7
    DIT = f?
    DIJ = f = 11 – 7 + 2 = 6
    Graf Planar : Contoh
    Graf sederhana planar terhubung
    memiliki 16 buah simpul, masing–masing
    simpul berderajat4.
    Representasi planar dari graf tersebut
    membagi bidang datar menjadi
    sejumlahwilayah (f). Berapa banyak
    wilayah yang terbentuk?

    DIK : n = 16
    e = 32, dari
    jumlah derajat simpul = 16 x 4 = 64
    jumlah sisi = jumlah derajat/2 = 64/2 = 32
    DIT : f ?
    DIJ : f = e – n + 2, maka f = 32 – 16 + 2 = 18
    Graf Planar : Ketidaksamaan Euler

    Jika G adalah graf sederhana terhubung


    dengan e adalah jumlah sisi dan n adalah
    jumlah simpul, yang dalam hal ini n ≥ 3, maka
    berlaku ketidaksamaan Euler e ≤ 3n -6.

    Contoh : K4 • Graf Planar

    • Tidak memenuhi
    K5
    • Bukan planar

    • Memenuhi
    K6
    • Tidak planar
    Graf Planar : Ketidaksamaan Euler (1)

    Jika G adalah graf sederhana terhubung


    dengan e adalah jumlah sisi dan n adalah
    jumlah simpul, yang dalam hal ini n ≥ 3 dan
    tidak ada sirkuit yang panjangnya 3, maka
    berlaku e ≤ 2n – 4.

    Contoh :

    • tidak memenuhi
    K3,3 ketidaksamaan
    e ≤ 2n – 4,

    Anda mungkin juga menyukai