bermain dengan teori graf - sanata dharma university · pdf file teori graf di sekolah ii....

Click here to load reader

Post on 24-May-2020

1 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • Bermain dengan Teori Graf

    Eko Budi Santoso, SJ.

    Universitas Sanata Dharma Yogyakarta

    16 November 2017

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 1/51

  • Outline

    I. Latar Belakang

    Era Digital - Network (Jejaring) Teori Graf di Sekolah

    II. Teori Graf

    Asal Mula Definisi Formal

    III. Mari Bermain dengan Teori Graf

    Mari Melukis Graf Euler Mari Melukis Graf Planar Mari Mewarnai Graf

    IV. Catatan Akhir

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 2/51

  • Latar Belakang

    Era Digital

    Saat ini, kita berada di era digital.

    Ditandai dengan pesatnya teknologi informasi.

    Smartphone menjadi bagian hidup sehari-hari.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 3/51

  • Latar Belakang

    Google search menjadi tempat mencari informasi.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 4/51

  • Latar Belakang

    Google Map menjadi pegangan saat tersesat.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 5/51

  • Latar Belakang

    Youtube menggantikan televisi sebagai sarana belajar, pengetahuan, dan hiburan.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 6/51

  • Latar Belakang

    Sosial Media menjadi tempat kita hang out.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 7/51

  • Latar Belakang

    Era Digital - Teknologi Komunikasi

    Pesatnya teknologi informasi.

    Smartphone.

    Google search.

    Google Map.

    Youtube.

    Sosial Media menjadi tempat kita hang out.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 8/51

  • Latar Belakang

    Era Digital - Teknologi Komunikasi

    Era digital identik dengan networking (jejaring)

    Kita adalah bagian dari jejaring tersebut.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 9/51

  • Latar Belakang

    Kasus konkret: FB - Mathematical Association of America (diakses 14 November 2017, pk 22:15)

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 10/51

  • Latar Belakang

    Aplikasi Netvizz: crawling data network. Aplikasi Gephi : visualisasi data jejaring FB - MAA

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 11/51

  • Latar Belakang

    Aplikasi Netvizz: crawling data network. Aplikasi Gephi : visualisasi data jejaring FB - MAA

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 12/51

  • Latar Belakang

    Aplikasi Netvizz: crawling data network. Aplikasi Gephi : visualisasi data jejaring FB - MAA

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 13/51

  • Latar Belakang

    Matematika apakah yang ada di belakang dunia jejaring internet?

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 14/51

  • Latar Belakang

    Matematika apakah yang membuat Google bisa menghubungkan kita dengan website tertentu?

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 15/51

  • Latar Belakang

    Matematika apakah yang membuat Google bisa menganjurkan jalan yang harus kita lalui?

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 16/51

  • Latar Belakang

    Matematika apakah di balik Traveloka?

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 17/51

  • Latar Belakang

    Flight Route Lion Air

    (http://www.lionair.co.id/promotion/flight-routes)

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 18/51

  • Latar Belakang

    Flight Route Garuda Indonesia

    (https://www.garuda-indonesia.com/id/en/destination/route-map/index-domestic.page)

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 19/51

  • Latar Belakang

    a b

    e

    d

    c

    Pengantar yang panjang: peran Teori Graf dalam hidup kita

    Fakta: Teori Graf hanya dipelajari oleh mahasiswa teknik komputer (informatika), mahasiswa Matematika.

    Teori graf tidak dikenal di sekolah dasar dan menengah.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 20/51

  • Bermain dengan Teori Graf

    a b

    e

    d

    c

    Memperkenalkan teori graf kepada siswa sekolah dasar dan menengah

    Melalui permainan (yang menyenangkan)

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 21/51

  • Bermula dari Kota Königsberg, Russia

    Abad ke-18, Leonhard Euler (bapak teori graf) ditanya oleh penduduk kota itu.

    Bisakah kita mulai di suatu tempat, berjalan melintasi ke-7 jembatan hanya sekali, dan kembali ke tempat semula.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 22/51

  • Bermula dari Kota Königsberg, Russia

    Euler membuktikan bahwa tidak mungkin.

    Dalam buktinya, Euler mengganti bidang tanah pada peta dengan sebuah titik dan jembatan dengan sebuah garis yang menghubungkan titik-titik.

    A

    B

    C

    D3

    4

    7 6

    5

    1

    2

    Euler percaya ini adalah masalah geometri yang oleh Leibniz disebut sebagai geometri posisi.

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 23/51

  • Definisi Formal

    a

    b c d

    ef

    Himpunan titik V (G) = {a, b, c, d, e, f}

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 24/51

  • Definisi Formal

    a

    b c d

    ef

    Himpunan titik V (G) = {a, b, c, d, e, f} Himpunan sisi E(G) = {ab, af, bc, bf, cd, ce, fe}

    Order graf G = |V | Ukuran graf G = |E|

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 25/51

  • Definisi Formal

    a

    b c d

    ef

    Himpunan titik V (G) = {a, b, c, d, e, f} Himpunan sisi E(G) = {ab, af, bc, bf, cd, ce, fe} Order graf G = |V |

    Ukuran graf G = |E|

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 25/51

  • Definisi Formal

    a

    b c d

    ef

    Himpunan titik V (G) = {a, b, c, d, e, f} Himpunan sisi E(G) = {ab, af, bc, bf, cd, ce, fe} Order graf G = |V | Ukuran graf G = |E|

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 25/51

  • Definisi Formal

    a

    b c d

    ef

    Himpunan titik V (G) = {a, b, c, d, e, f} Himpunan sisi E(G) = {ab, af, bc, bf, cd, ce, fe} Titik a dan b bertentangga

    Titik a dan c tidak bertetangga

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 26/51

  • Definisi Formal

    a

    b c d

    ef

    Himpunan titik V (G) = {a, b, c, d, e, f} Himpunan sisi E(G) = {ab, af, bc, bf, cd, ce, fe} Tetangga titik b, N(b) = {a, c, f}

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 27/51

  • Mari Bermain dengan Graf

    Alat yang diperlukan: Alat tulis dan kertas

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 28/51

  • Mari Bermain dengan Graf

    Alat yang diperlukan: Alat tulis dan kertas

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 28/51

  • Mari Bermain dengan Graf

    Alat yang diperlukan: Alat tulis dan kertas

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 28/51

  • Mari Melukis Graf Euler

    Graf Euler

    Sebuah graf disebut graf Euler jika kita bisa melukisnya, bermula dari satu titik, melewati semua titik-titik tetapi hanya boleh melewati sisi sekali saja dan kembali ke titik semula.

    a b

    e

    d

    c

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 29/51

  • Mari Melukis Graf Euler

    Graf Euler

    Sebuah graf disebut graf Euler jika kita bisa melukisnya, bermula dari satu titik, melewati semua titik-titik tetapi hanya boleh melewati sisi sekali saja dan kembali ke titik semula.

    a b

    e

    d

    c

    a

    b

    c

    d

    e

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 30/51

  • Mari Melukis Graf Euler

    Graf Euler

    Sebuah graf disebut graf Euler jika kita bisa melukisnya, bermula dari satu titik, melewati semua titik-titik tetapi hanya boleh melewati sisi sekali saja dan kembali ke titik semula.

    a b

    e

    d

    c

    a b

    c

    d

    e

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 30/51

  • Mari Melukis Graf Euler

    Graf Euler

    Sebuah graf disebut graf Euler jika kita bisa melukisnya, bermula dari satu titik, melewati semua titik-titik tetapi hanya boleh melewati sisi sekali saja dan kembali ke titik semula.

    a b

    e

    d

    c

    a b

    c

    d

    e

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 30/51

  • Mari Melukis Graf Euler

    Graf Euler

    Sebuah graf disebut graf Euler jika kita bisa melukisnya, bermula dari satu titik, melewati semua titik-titik tetapi hanya boleh melewati sisi sekali saja dan kembali ke titik semula.

    a b

    e

    d

    c

    a b

    c

    d

    e

    Eko Budi Santoso, SJ. Bermain dengan Teori Graf 30/51

  • Mari Melukis Graf Euler

    Graf Euler

    Sebuah graf disebut graf Euler jika kita bisa melukisnya, bermula dari satu titik, melewati semua titik-titik tetapi hanya boleh melewati sisi sekali saja dan kembali ke titik semula.

    a b

    e

    d

    c

    a b

    c