Scribd Logo
Unggah

Selamat datang di Scribd!

  • 34 tayangan

    Pertemuan 5 Eulerian Graph

    Diunggah oleh

    Anisya
    Dokumen tersebut membahas tentang konsep graf Eulerian dan Hamiltonian. Graf Eulerian adalah graf yang dapat dilalui dengan menggunakan setiap sisi hanya sekali saja. Sedangkan graf Hamiltonian adalah graf yang memiliki jalur Hamiltonian yang melalui setiap simpul tepat sekali.

    Hak Cipta:

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

    Pertemuan 5 Eulerian Graph

    Diunggah oleh

    Anisya
    34 tayangan15 halaman
    Dokumen tersebut membahas tentang konsep graf Eulerian dan Hamiltonian. Graf Eulerian adalah graf yang dapat dilalui dengan menggunakan setiap sisi hanya sekali saja. Sedangkan graf Hamiltonian adalah graf yang memiliki jalur Hamiltonian yang melalui setiap simpul tepat sekali.

    Judul Asli

    pertemuan 5 Eulerian Graph

    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?

    Dokumen tersebut membahas tentang konsep graf Eulerian dan Hamiltonian. Graf Eulerian adalah graf yang dapat dilalui dengan menggunakan setiap sisi hanya sekali saja. Sedangkan graf Hamiltonian adalah graf yang memiliki jalur Hamiltonian yang melalui setiap simpul tepat sekali.

    Hak Cipta:

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

    Pertemuan 5 Eulerian Graph

    Diunggah oleh

    Anisya
    Dokumen tersebut membahas tentang konsep graf Eulerian dan Hamiltonian. Graf Eulerian adalah graf yang dapat dilalui dengan menggunakan setiap sisi hanya sekali saja. Sedangkan graf Hamiltonian adalah graf yang memiliki jalur Hamiltonian yang melalui setiap simpul tepat sekali.

    Hak Cipta:

    © All Rights Reserved
    Unduh sebagai PPTX, PDF, TXT atau baca online dari Scribd
    Unduh sebagai pptx, pdf, atau txt
    Anda di halaman 1dari 15

    Eulerian dan Hamiltonian

    Siti Khoiruli Ummah


    Silahkan simak tayangan youtube
    berikut

    https://youtu.be/2iovbcPwAro
    Nah, sekarang ayo kita coba

     Traversable adalah suatu


    sifat yang dimiliki graf  Ambil
    sedemikian sehingga apabila pensilmu,
    kita menggambar graf maka cobalah
    pensil kita tidak akan berhenti
    menyalin
    (bersambungan) dan tidak
    pernah melewati sisi/edge lebih graf berikut
    dari satu kali kemudian
    kemukakan
    mengapa
    graf tersebut
    tidak
    traversable?
    Nah, sekarang ayo kita coba

     Traversable adalah suatu


    sifat yang dimiliki graf  Ambil
    sedemikian sehingga apabila pensilmu,
    kita menggambar graf maka cobalah
    pensil kita tidak akan berhenti
    menyalin
    (bersambungan) dan tidak
    pernah melewati sisi/edge lebih graf berikut
    dari satu kali kemudian
    kemukakan
    mengapa
    graf tersebut
    tidak
    traversable?
    Nah, perjalanan Euler yang megharuskan melewati
    setiap jembatan sebanyak satu kali namun semua
    wilayah di Kota Konigsberg harus dikunjungi
    berlaku…

     Graf yang bersesuaian dengan


    denah tersebut yaitu:
    Akhirnya, Mr. Euler membuat suatu
    aturan yaitu:

    Suatu Graf dikatakan Traversable jika:


    • Semua vertices mempunyai degree yang jumlahnya
    genap

    ATAU
    • Hanya ada DUA VERTICES yang mempunyai degree
    yang JUMLAHNYA GANJIL sedangkan lainnya
    jumlahnya genap
    Graf yang mempunyai sifat
    Tranversable ini selanjutnya disebut
    sebagai GRAF EULER

    TUGAS 1
    1. Buatlah contoh graf euler dan bukan euler, masing-masing sebanyak 3 graf
    2. Beri penjelasan mengapa graf yang dibuat euler atau bukan euler
    Review sejenak..

    Masih ingat bedanya walk dan path?


    Euler Path

     Euler Path juga dapat disebut Syarat Euler Path


    dengan Euler Trail atau Euler Walk

    Jika ada Trail pada graf terhubung yang memuat


    semua edge dari graf maka trail tersebut disebut
    sebagai Euler Trail

     Suatu graf yang memuat euler path


    jika dan hanya jika memuat paling Jika ada walk pada graf terhubung yang melintasi
    banyak dua vertices yang berderajat semua edge pada graf tepat satu kali atau tanpa
    ganjil mengulang vertices maka walk tersebut disbeut dengan
    Euler Walk
    Simak Video berikut…

    https://youtu.be/Kwj5sdF8b18
    Euler Path juga dapat disebut dengan
    Euler Trail atau Euler Walk

    TUGAS 2
    1. Buatlah contoh euler trail dan euler walk, masing-masing sebanyak 3 graf
    2. Beri penjelasan mengapa graf yang dibuat merupakan euler trail atau euler walk
    Euler Circuits

    Syarat Euler Circuit


     Euler Circuit juga dapat disebut
    dengan Euler Cycle atau Euler Tour
    Jika ada circuit pada graf terhubung yang memuat semua edge dari graf
    maka trail tersebut disebut sebagai Euler Circuit

    Jika ada walk pada graf terhubung yang mempunyai vertex awal dan vertex
    ujung sama dan melintasi semua edge pada graf tepat satu kali atau tanpa
    mengulang vertices maka walk tersebut disbeut dengan Euler Circuit

     Suatu graf yang memuat euler Suatu Euler trail yang mempunyai vertex awal dan vertex ujung
    yang sama disebut dengan Euler Circuit
    circuit jika dan hanya jika semua
    verticesnya mempunyai degree
    sebanyak genap
    Suatu Euler Trail tertutup disebut dengan Euler Circuits
    Graf yang mempunyai sifat
    Tranversable ini selanjutnya disebut
    sebagai GRAF EULER

    TUGAS 3
    1. Buatlah contoh euler circuit dan bukan euler circuit, masing-masing sebanyak 3 graf
    2. Beri penjelasan mengapa graf yang dibuat euler circuit atau bukan euler circuit
    Semi-Euler Graph

     Jika suatu graf terhubung


    mempunyai Euler Trail tetapi tidak
    memuat Euler Circuit maka graf Syarat Semi-Euler Graph
    tersebut disebut dengan Semi-Euler
    Graf

    Graf Harus terhubung

    Graf Harus memuat Euler


    Trail
    Graf yang mempunyai sifat
    Tranversable ini selanjutnya disebut
    sebagai GRAF EULER

    TUGAS 4
    1. Buatlah contoh semi-euler graph dan bukan semi-euler graph, masing-masing
    sebanyak 3 graf
    2. Beri penjelasan mengapa graf yang dibuat semi-euler atau bukan semi-euler

    Anda mungkin juga menyukai