Download - Bermain dengan Teori Graf - Sanata Dharma University · Teori Graf di Sekolah II. Teori Graf Asal Mula De nisi Formal III. Mari Bermain dengan Teori Graf Mari Melukis Graf Euler Mari

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


Latar Belakang

Era Digital

Saat ini, kita berada di era digital.

Ditandai dengan pesatnya teknologi informasi.

Smartphone menjadi bagian hidup sehari-hari.


Latar Belakang

Google search menjadi tempat mencari informasi.


Latar Belakang

Google Map menjadi pegangan saat tersesat.


Latar Belakang

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


Latar Belakang

Sosial Media menjadi tempat kita hang out.


Latar Belakang

Era Digital - Teknologi Komunikasi

Pesatnya teknologi informasi.

Smartphone.

Google search.

Google Map.

Youtube.

Sosial Media menjadi tempat kita hang out.


Latar Belakang

Era Digital - Teknologi Komunikasi

Era digital identik dengan networking (jejaring)

Kita adalah bagian dari jejaring tersebut.


Latar Belakang

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


Latar Belakang

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


Latar Belakang



Latar Belakang

Matematika apakah yang ada di belakang dunia jejaring internet?


Latar Belakang

Matematika apakah yang membuat Google bisa menghubungkankita dengan website tertentu?


Latar Belakang

Matematika apakah yang membuat Google bisa menganjurkanjalan yang harus kita lalui?


Latar Belakang

Matematika apakah di balik Traveloka?


Latar Belakang

Flight Route Lion Air

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


Latar Belakang

Flight Route Garuda Indonesia

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


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.


Bermain dengan Teori Graf

a b

e

d

c

Memperkenalkan teori graf kepada siswa sekolah dasar danmenengah

Melalui permainan (yang menyenangkan)


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.


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.


Definisi Formal

a

b c d

ef

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


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|


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|


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|


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


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}


Mari Bermain dengan Graf

Alat yang diperlukan: Alat tulis dan kertas


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



Graf Euler


a b

e

d

c

a

b

c

d

e



Graf Euler


a b

e

d

c

a b

c

d

e



a b

e

d

c

Apakah ini graf Euler?



a bc

d

e e

Apakah ini 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.



a

b c d

ef

Teorema

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


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



Apakah ini graf planar?

a b

cd

a b

cd




a b

cd

e f

gh



http://www.planarity.net


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


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


Mari Mewarnai Graf

Konjektur Empat Warna

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

;


Mari Mewarnai Graf

www.transum.org/Maths/Activity/Colouring

;


Mari Mewarnai Graf


;


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.


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


Terima Kasih

a b

e

d

c

Terima Kasih


Download - Bermain dengan Teori Graf - Sanata Dharma University · Teori Graf di Sekolah II. Teori Graf Asal Mula De nisi Formal III. Mari Bermain dengan Teori Graf Mari Melukis Graf Euler Mari

Top Related