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

Bermain dengan Teori Graf

Eko Budi Santoso, SJ.

Universitas Sanata DharmaYogyakarta

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 MulaDefinisi Formal

III. Mari Bermain dengan Teori Graf

Mari Melukis Graf EulerMari Melukis Graf PlanarMari 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 November2017, 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 menghubungkankita dengan website tertentu?

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

Latar Belakang

Matematika apakah yang membuat Google bisa menganjurkanjalan 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 teknikkomputer (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 danmenengah

Melalui permainan (yang menyenangkan)

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

Bermula dari Kota Konigsberg, Russia

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

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

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

Bermula dari Kota Konigsberg, Russia

Euler membuktikan bahwa tidak mungkin.

Dalam buktinya, Euler mengganti bidang tanah pada petadengan sebuah titik dan jembatan dengan sebuah garis yangmenghubungkan titik-titik.

A

B

C

D3

4

76

5

1

2

Euler percaya ini adalah masalah geometri yang oleh Leibnizdisebut 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, bermuladari satu titik, melewati semua titik-titik tetapi hanya bolehmelewati 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, bermuladari satu titik, melewati semua titik-titik tetapi hanya bolehmelewati 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, bermuladari satu titik, melewati semua titik-titik tetapi hanya bolehmelewati 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, bermuladari satu titik, melewati semua titik-titik tetapi hanya bolehmelewati 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, bermuladari satu titik, melewati semua titik-titik tetapi hanya bolehmelewati 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, bermuladari satu titik, melewati semua titik-titik tetapi hanya bolehmelewati 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, bermuladari satu titik, melewati semua titik-titik tetapi hanya bolehmelewati 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, bermuladari satu titik, melewati semua titik-titik tetapi hanya bolehmelewati 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, bermuladari satu titik, melewati semua titik-titik tetapi hanya bolehmelewati 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

a b

e

d

c

Apakah ini graf Euler?

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

Mari Melukis Graf Euler

a bc

d

e e

Apakah ini graf Euler?

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

Mari Melukis Graf Euler

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}Derajat sebuah titik adalah banyaknya tetangga titik tersebut.

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

Mari Melukis Graf Euler

a

b c d

ef

Teorema

Sebuah graf adalah Euler jika dan hanya jika setiap titik dalam graftersebut berderajat genap.

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

Mari Melukis Graf Planar

Definisi

Sebuah graf adalah graf planar jika kita bisa melukisnya dalambidang datar sehingga tidak ada sisi yang bersilangan.

a bc

d

e f

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

Mari Melukis Graf Planar

Apakah ini graf planar?

a b

cd

a b

cd

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

Mari Melukis Graf Planar

Apakah ini graf planar?

a b

cd

a b

cd

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

Mari Melukis Graf Planar

Apakah ini graf planar?

a b

cd

e f

gh

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

Mari Melukis Graf Planar

Apakah ini graf planar?

a b

cd

e f

gh

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

Mari Melukis Graf Planar

http://www.planarity.net

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

Mari Melukis Graf Planar

http://www.planarity.net

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

Mari Melukis Graf Planar

http://www.planarity.net

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

Mari Mewarnai Graf

Aturan mewarnai

Ada beberapa aturan untuk mewarnai graf. Salah satunya,mewarnai titik-titik dalam graf sehingga titik-titik yangbertetangga harus berbeda warna.

a b

e

d

c

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

Mari Mewarnai Graf

Aturan mewarnai

Ada beberapa aturan untuk mewarnai graf. Salah satunya,mewarnai titik-titik dalam graf sehingga titik-titik yangbertetangga harus berbeda warna.

a b

e

d

c

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

Mari Mewarnai Graf

Pertanyaan

Berapa jumlah minimal warna yang dipakai untuk mewarnai?Jumlah minimal itu disebut Bilangan Kromatik. Berbeda grafbilangan kromatiknya bisa berbeda, bisa sama.

a b

e

d

c

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

Mari Mewarnai Graf

Konjektur Empat Warna

Hanya dibutuhkan empat warna untuk mewarnai sebuah petasehingga negara (wilayah) bertetangga berbeda warna.

;

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

Mari Mewarnai Graf

www.transum.org/Maths/Activity/Colouring

;

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

Mari Mewarnai Graf

www.transum.org/Maths/Activity/Colouring

;

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

Mari Mewarnai Graf

www.transum.org/Maths/Activity/Colouring

;

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

Mari Mewarnai Graf

www.transum.org/Maths/Activity/Colouring

;

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

Catatan Akhir

Baru Sebagian Sangat Kecil

Permainan yang disajikan dalam presentasi ini hanya sebagiankecil saja.

Masih ada peluang untuk terus menggali, menemukanpermainan-permainan berdasarkan konsep-konsep dalam teorigraf.

Sebuah permaian tentu harus menyenangkan.

Silahkan kalau ada yang berminat membuat penelitianberkaitan dengan topik ini.

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

Catatan Akhir

Topik Lain

Jejak Euler (Eulerian Trail)

Jejak Hamilton (Hamiltonian Trail)

Tur Ksatria (Knight’s Tour)

Masalah Tukang Pos China (Chinese Postman Problem)

Teori Dominasi

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

Terima Kasih

a b

e

d

c

Terima Kasih

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