PERANGKAT PEMBELAJARAN

PERANGKAT PEMBELAJARAN

MATA KULIAH KODE DOSEN

: TEORI GRAPH : MKK519515 : EDY MULYONO, M.Pd.

PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS VETERAN BANGUN NUSANTARA SUKOHARJO

KONTRAK PEMBELAJARAN

TEORI GRAPH MKK519515

Semester V / 2 SKS Program Studi Pendidikan Matematika

Oleh : EDY MULYONO, M.Pd.

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS VETERAN BANGUN NUSANTARA SUKOHARJO

A.

Identitas Mata Kuliah Mata Kuliah Semester / SKS Pengampu Mata Kuliah Kode Mata Kuliah

B.

: : : :

TEORI GRAPH III / 2 SKS EDY MULYONO, M.Pd. MKK519515

Manfaat Mata Kuliah Setelah mengikuti kuliah ini diharapkan mahasiswa dapat : 1. Memiliki pemahaman tentang konsep dasar teori graph, jejak, lintasan, karakteristik graph khusus, pohon, graph euler, graph hamilton, pohon, graph bidang dan pewarnaan. 2. Mampu menerapakan konsep teori graph dalam kehidupan nyata.

C.

Deskripsi Mata Kuliah Teori Graph adalah mata kuliah yang mempelajari tentang konsep-konsep dasar pada graph yang meliputi pengertian, dan karakteristik graph-graph khusus. Selain itu juga akan dibahas mengenai graph euler, graph hamilton, graph bidang dan pewarnaan.

D.

Kompetensi Dasar dan Indikator Kompetensi Dasar 1. Mendefinisikan berbagai macam konsep graph dan membuat beberapa graph khusus.

2. Menggunakan konsep graph dalam pemecahan masalah.

E.

Indikator 1.1 1.2 1.3 1.4 1.5 1.6 1.7

Menjelaskan definisi dasar graph Menentukan sifat isomorphisme graph Mengidentifikasi sifat bipartite pada graph Menentukan subgraph dari suatu graph Menentukan path dan cycle pada suatu graph Membuat tree serta menetukan bridge dan cut vertex Menggunakan konsep minimum spanning tree dalam pemecahan masalah 1.8 Mengidentifikasi graph euler dan graph hamilton 1.9 Mengidentifikasi sifat ke-planar-an graph 1.10 Menentukan dual dari plane graph 2.1 Menentukan bilangan kromatis pada pewarnaan graph 2.2 Menggunakan konsep pewarnaan dalam pemecahan masalah

Organisasi Materi

KD I F.

KD II

Pendekatan Dan Strategi Pembelajaran Strategi pembelajaran yang digunakan mengarah pada Active Learning. Metode-metode yang digunakan adalah sebagai berikut : 1. Practice Rehearsal Pairs 2. Kelompok Belajar (The Study Group) 3. Two stay two stray 4. Gallery of Learning 5. The Learning Cell

G.

Sumber Belajar [1] Rinaldi Munir. 2010. Matematika Diskrit. Bandung: Informatika [2] Drs. Jong Jek Siang, M.Sc. 2009. Matematika Diskrit. Yogyakarta: Andi offset [3] Modul Kuliah

H.

Penilaian Dan Kriteria Pembelajaran 1. 2. 3. 4.

I.

Presensi dan Keaktifan Tugas Terstruktur UTS UAS

: : : :

30 % 20 % 20 % 30 % 100 %

Jadwal Perkuliahan Pertemuan

PEMBELAJARAN

1

Materi :

2

Materi :

3

Materi :

4

 Menjelaskan definisi dasar graph  Menentukan sifat isomorphisme graph  Mengidentifikasi sifat bipartite pada graph

Materi :  Menentukan subgraph dari suatu graph  Menentukan path dan cycle pada suatu graph

5

Materi :

6

Materi :

7

QUIZ I

8

Ujian Tengah Semester

9

Materi :

10

Materi :

11

Materi :

12

Materi :

13 14 15 16

 Membuat tree serta menetukan bridge dan cut vertex  Menggunakan konsep minimum spanning tree dalam pemecahan masalah

 Mengidentifikasi graph euler  Mengidentifikasi graph hamilton  Mengidentifikasi sifat ke-planar-an graph  Menentukan dual dari plane graph

Materi :  Menentukan bilangan kromatis pada pewarnaan graph  Menggunakan konsep pewarnaan dalam pemecahan masalah

QUIZ II REVIEW:  Persiapan Ujian Semester

Ujian Akhir Semester

UNIVERSITAS VETERAN BANGUN NUSANTARA SUKOHARJO FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

SILABUS Program Studi Kode Mata Kuliah Mata Kuliah Bobot Semester Mata Kuliah Prasyarat Standar Kompetensi

Kompetensi Dasar 1. Mendefinisikan berbagai macam konsep graph dan membuat beberapa graph khusus.

: : : : : : :

PENDIDIKAN MATEMATIKA MKK519515 TEORI GRAPH 2 SKS V Logika dan Himpunan, Riset Operasi Memiliki pemahaman tentang konsep dasar teori graph, jejak, lintasan, karakteristik graph khusus, pohon, graph euler, graph hamilton, pohon, graph bidang dan pewarnaan dan mampu menerapakan konsep teori graph dalam permasalahan kehidupan nyata.

Indikator 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10

Menjelaskan definisi dasar graph Menentukan sifat isomorphisme graph Mengidentifikasi sifat bipartite pada graph Menentukan subgraph dari suatu graph Menentukan path dan cycle pada suatu graph Membuat tree serta menetukan bridge dan cut vertex Menggunakan konsep minimum spanning tree dalam pemecahan masalah Mengidentifikasi graph euler dan graph hamilton Mengidentifikasi sifat ke-planaran graph Menentukan dual dari plane graph

Pengalaman Belajar Tatap muka  Memberikan teori dasar yang ada pada graph  Menjelaskan sifat sifat khusus pada graph : isomorphisme, dan bipartisi graph.  Memberikan penjelasan tentang Sub Graph, Path dan Cycle  Menjelaskan tentang Tree dan Aplikasinya  Menjelaskan tentang Euler Graph dan Hamiltonian Cycle  Menjelsakan tentang sifat keplanar-an graph. Kegiatan terstruktur  Mendiskusikan sifat pada berbagai jenis graph  Post-test

Materi Pokok  Graph theory  Trees  Euler tour dan

Hamiltonian Cycle

 Plane dan Planar Graph

Alokasi Waktu (menit) 12  150

Sumber/ Bahan/ Alat Sumber :  Buku panduan mata kuliah TEORI GRAPH Alat : Laptop, LCD, Whiteboard

Penilaian/ Evaluasi Bentuk evaluasi :  Pre-test  Post-test Instrumen :  Lembar Kerja Individu  Lembar Kegiatan kelompok

2. Menggunakan konsep graph dalam pemecahan masalah.

2.1 2.2

Menentukan bilangan kromatis pada pewarnaan graph Menggunakan konsep pewarnaan dalam pemecahan masalah

Tatap muka  Memberikan deskripsi singkat tentang jenis pewarnaan graph.  Memberikan deskripsi singkat tentang cara pewarnaan graph.  Menjelaskan tentang aplikasi pewarnaan graph. Kegiatan terstruktur  Mendiskusikan berbagai permasalahan yang dapat diselesaikan dengan graph  Post-test

 Colouring

2  150

Sumber :  Buku panduan mata kuliah TEORI GRAPH

Bentuk evaluasi :  Pre-test  Post-test

Alat : Laptop, LCD, Whiteboard

Instrumen :  Lembar Kerja Individu  Lembar Kegiatan kelompok

RENCANA MUTU PERKULIAHAN (RMP) Nama Dosen Fakultas Program Studi

: : :

ERIKA LARAS ASTUTININGTYAS, M.Pd. KEGURUAN DAN ILMU PENDIDIKAN PENDIDIKAN MATEMATIKA

Mata Kuliah Kode Mata Kuliah Bobot Semester Pertemuan keStandart Kompetensi

: : : : : :

Kompetensi Dasar

:

Indikator

:

Tujuan

:

TEORI GRAPH MKK519515 2 SKS V 1 s.d 4 Memiliki pemahaman tentang konsep dasar teori graph, jejak, lintasan, karakteristik graph khusus, pohon, graph euler, graph hamilton, pohon, graph bidang dan pewarnaan dan mampu menerapakan konsep teori graph dalam permasalahan kehidupan nyata. 1. Mendefinisikan berbagai macam konsep graph dan membuat beberapa graph khusus. 1.1 Menjelaskan definisi dasar graph 1.2 Menentukan sifat isomorphisme graph 1.3 Mengidentifikasi sifat bipartite pada graph 1.4 Menentukan subgraph dari suatu graph 1.5 Menentukan path dan cycle pada suatu graph Menjelaskan definisi graph, unsur-unsur pada graph dan kekhususan bentuk graph tertentu Menentukan sifat isomorphisme dari dua buah graph Mengidentifikasi graph bipartite dan non-bipartite Mengkonstruk sub graph dan spanning sub graph Menentukan walk, trail, path dan cycle yang aa pada suatu graph

MATERI DEFINISI GRAPH Definisi 

Suatu graph G = {V(G), E(G)} terdiri atas dua buah himpunan berhingga. V(G) adalah himpunan vertex (titik) pada graph, yang sering dinotasikan dengan V, yang merupakan himpunan tak kosong dan terdiri atas elemen-elemen yang dinamakan dengan vertices. E(G) adalah himpunan edge (sisi) pada graph, yang sering dinotasikan dengan E, yang mungkin merupakan himpunan kosong. Elemenelemen pada E dinamakan dengan edges.

Definisi Definisi lain tentang Graph adalah sebagai berikut.  Suatu graph (undirected graph) G terdiri dari suatu himpunan vertex V (node) dan himpunan edge (arcs) E sedemikian sehingga tiap edge eE dikawankan dengan suatu pasangan tak berurut vertex. Jika ada edge tunggal e dikawankan dengan vertex-vertex v dan w, maka dapat ditulis e = (v, w) atau e = (w, v). Dalam hal ini (v, w) menyatakan suatu edge dalam undirected graph dan bukan pasangan berurutan.  Suatu directed graph (digraph) G terdiri dari suatu himpunan vertex (node ) V dan himpunan edge (arcs) E sedemikian sehingga tiap edge eE dikawankan dengan suatu pasangan berurutan vertexvertex. Jika ada edge tunggal e dikawankan dengan pasangan berurutan vertex-vertex (v, w), maka dapat ditulis e = (v, w).

Definisi 

Diketahui suatu graph G = {V(G), E(G)}. Jika ada edge eE yang dikawankan dengan sepasang vertex yang identik (v, v), atau dapat ditulis e = (v, v) maka e disebut sebagai loop.

Definisi 

Diketahui suatu graph G = {V(G), E(G)}. Jika ada edge e1, e2 E dengan e1 = (u, v) dan e2 = (u, v) maka e1 dan e2 disebut sebagai parallel edges atau multiple edges.

Definisi Diketahui suatu graph G = {V(G), E(G)}. a. Sebuah vertex vV yang tidak terhubung dengan setiap egde pada graph G dikatakan sebagai isolated vertex. b. Jika ada dua buah vertex u,vV terhubung dengan sebuah sisi eE maka dapat dikatakan bahwa vertex u,v incident dengan edge e, serta dapat pula dikatakan bahwa vertex u dan vertex v adjacent. Definisi a. b.

Suatu graph G dikatakan simple graph jika graph tersebut tidak memiliki loop dan parallel edge. Kn adalah suatu complete graph dengan n vertex jika setiap vertex dihubungkan dengan vertex yang lain oleh sebuah edge (tidak ada loop dan multiple edges).

Definisi Sebuah graph G1 = {V1, E1} dikatakan isomorphic dengan graph G1 = {V2, E2} jika ada korespondensi satusatu antara himpunan vertex V1 dengan V2, dan ada korespondensi satu-satu antara himpunan edge E1 dan E2. Dengan kata lain, jika e1 adalah sebuah edge pada G1 yang incident dengan u1 dan v1 pada G1 maka e2 pada G2 yang berkorespondensi dengan e1 harus incident dengan u2 dan v2 pada G2 yang juga berkorespondensi dengan u1 dan v1. Contoh Perhatikan pasangan graph isomorphic berikut. Dapatkah anda jelaskan mengapa pasangan graph berikut isomorphic?

(a)

(b)

(c) Gambar 1. 1 Contoh Isomorphism graph

Definisi a. b.

Bipartite graph adalah suatu graf yang vertex-vertex nya dapat dipartisi menjadi himpunan disjoint V 1 dan V2 dengan setiap edge incident pada satu vertex di V 1 dan satu vertex di V2. Km,n adalah complete bipartite graph dengan m dan n vertex jika graph tersebut mempunyai disjoint set V1 dengan m vertex dan V2 dengan n vertex. Setiap vertex dalam V1 dikawankan dengan setiap vertex dalam V2 oleh sebuah edge. (Tidak ada parallel edges).

Contoh Perhatikan graph berikut.

e

d

f

b

d

f

c

a Graph G1 b

a

Graph c G2

e

Gambar Bipartite Graph 



Graph G1 memiliki 6 vertex, yaitu a, b, c, d, e, dan f. Apabila keenam vertex tersebut dikelompokkan menjadi 2, yaitu E1 = {a, c, f} dan E2 = {b, d, f} kemudian kita letakkan setiap vertex menurut kelompoknya, maka diperoleh posisi vertex seperti Gambar 1. 2. Setiap dua vertex yang adjacent pada G1, juga harus adjacent pada G2. Sehingga graph yang baru diperoleh adalah seperti G 2. Pada G2, setiap vertex anggota E1 tidak berpasangan dengan anggota E1, demikian pula untuk setiap vertex anggota E2 tidak berpasangan dengan anggota E2 juga. Artinya setiap edge incident dengan satu vertex di E1 dan satu vertex di E2. Karena pada graph G1 vertex-vertex nya dapat dipartisi menjadi himpunan disjoint E1 dan E2 dengan setiap edge incident pada satu vertex di E1 dan satu vertex di E2 maka graph G1 adalah suatu Bipartite Graph. Perhatikan pula bahwa :  vertex a adjacent dengan vertex b, d, dan f  vertex c adjacent dengan vertex b, d, dan f  vertex e adjacent dengan vertex b, d, dan f Artinya, setiap vertex dalam E1 dikawankan dengan setiap vertex dalam E2 oleh sebuah edge. Hal ini berarti, graph G1 adalah sebuah comlplete bipartite graph (K3,3). Mengapa K3,3?

DERAJAT VERTEX Definisi 

Misalkan v adalah suatu vertex pada graph G. Derajat dari vertex v (d(v)) adalah banyaknya edge yang incident dengan v. Apabila vertex v incident dengan sebuah loop maka derajat dari v adalah dua.


Gambar 1. 2 Tentukan derajat setiap vertex pada graph tersebut!

Teorema (Handshaking Theorem) Untuk setiap graph G dengan e edge dan n vertex, v1, v2, ..., vn, berlaku: n

 dv  = 2e i

i1

(Jelaskan!) Suatu vertex dikatakan ganjil atau genap bergantung pada derajat vertex tersebut, ganjil atau genap. Akibat teorema Untuk setiap graph G ada sebanyak genap vertex yang berderajad ganjil. (Buktikan!)

SUBGRAPHS Definisi 

Misalkan H adalah suatu graph dengan V(H) adalah himpunan vertex pada H dan dan E(H) adalah himpunan edge pada H. G suatu graph dengan V(G) adalah himpunan vertex pada G dan dan E(G) adalah himpunan edge pada G. H adalah subgraph dari G jika V(H)  V(G) dan E(H)  E(G). Atau dengan istilah lain dapat dikatakan pula bahwa G adalah supergraph dari H. Sebagai contoh, perhatikan gambar di bawah ini.

g

h

e

d

c

a

b G1

h

f

e

d

c

a

b

g

G2

f

G3

Gambar Berdasarkan gambar di atas terlihat bahwa G3  G1, G2

G1. Mengapa ? Jelaskan!

Apakah setiap graph yang isomorphic dengan subgraph dari G juga merupakan subgraph dari G? Jelaskan! Definisi Spanning subgraph dari G adalah suatu subgraph H dari G, dengan V(H) = V(G), H dan G adalah himpunan vertex yang sama.

PATHS DAN CYCLES Definisi   

Sebuah walk (jalan) dari graph G adalah barisan berhingga W = v0 e1 v1 e2 v2 ... vn–1 en vn yang berawal dari vertex v0 dan berakhir di vn dan sering dinamakan dengan v0 – vn walk. Jika setiap edge e1, e2, ..., en pada walk W = v0 e1 v1 e2 v2 ... vn–1 en vn semuanya berbeda maka W disebut sebagai trail (jejak). Misal v0 dan vn adalah vetex-vertex dalam suatu graph. Suatu path (lintasan) dari v0 ke vn dengan panjang n adalah suatu barisan bergantian dari (n + 1) vertex dan n edge yang dimulai dari vertex v 0 dan berakhir di vertex vn, (v0, e1, v1, e2, v2, ... , vn-1, en, vn) dengan edge ei incident pada vertex vi-1 dan vi untuk i = 1, 2, ..., n, dan vertex v0, v1, ..., vn semuanya berbeda.

Contoh Perhatikan graph berikut

Gambar 1. 3 Buatlah path dengan panjang 12! Definisi Suatu graph G dikatakan connected jika diberikan sebarang vertex v dan w, maka terdapat suatu path dari v ke w. Jika tidak demikian dikatakan disconnected. Definisi Ambil sebarang vertex u pada graph G, misalkan C(u) adalah himpunan semua vertex pada G yang connected dengan u, maka subgraph dari G yang termuat dalam C(u) disebut connected component yang memuat u. Untuk lebih jelasnya perhatikan gambar berikut.

Gambar 1. 4 Graph dengan enam buah connected component Banyak component dari graph G dinotasikan dengan (G). Definisi 

Suatu cycle (circuit) adalah suatu path dengan panjang tidak nol dari v ke v dengan tidak ada edge yang diulang.


Gambar 1. 5 Dapatkah anda menemukan simple path, cycle, dan simple cycle pada graph tersebut?

METODE PEMBELAJARAN Learning Cell

LANGKAH PEMBELAJARAN PERTEMUAN 1 No.

Tahap

1.

Pendahuluan

2.

Penyajian

Kegiatan Pembelajaran a. Apersepsi Memberi gambaran tentang pemanfaatan graph dan memberikan gambaran tentang permasalahan sehari-hari yang memanfaatkan teori graph.

Eksplorasi a. Memberikan definisi dasar pada graph dan beberapa jenis graph khusus. b. Menjelsakan tentang isomorphisme graph. c. Membentuk siswa dalam beberapa kelompok.

Elaborasi a. Memberikan lembar kerja kepada setiap kelompok yang berisi contoh permasalahan tentang isomorphisma graph. b. Setiap kelompok dibagi lagi menjadi 2 grup. Setiap grup menuliskan permasalahan tentang isomorphisme graph. c. Pada kesempatan pertama, grup I bertugas sebagai penanya dan grup II menjawab pertanyaan. Setelah itu, bergantian grup II bertanya, dan grup I menjawab.

Eksplanasi Menunjuk perwakilan dari setiap kelompok untuk menyampaikan hasil diskusinya, untuk kemudian dibahas secara klasikal. 3.

Penutup

Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat satu sebuah graph dengan ketentuan tertentu, kemudian diminta membuat sebuah graph yang isomorphic dengan graph tersebut.

Alokasi Waktu 5 menit

10 menit 20 menit 5 menit 5 menit 5 menit 20 menit

15 menit

15 menit

PERTEMUAN 2 No.

Tahap

1.

Pendahuluan

2.

Penyajian

Kegiatan Pembelajaran a. Apersepsi Memberi gambaran tentang bipartisi graph. b. Motivasi Memberikan gambaran tentang permasalahan sehari-hari yang memanfaatkan teori graph.

Eksplorasi a. Memberikan definisi bipartisi graph. b. Membentuk siswa dalam beberapa kelompok.

Elaborasi a. Memberikan lembar kerja kepada setiap kelompok yang berisi contoh permasalahan tentang bipartisi graph. b. Setiap kelompok dibagi lagi menjadi 2 grup. Setiap grup menuliskan permasalahan bipartisi graph. c. Pada kesempatan pertama, grup I bertugas sebagai penanya dan grup II menjawab pertanyaan. Setelah itu, bergantian grup II bertanya, dan grup I menjawab.

Alokasi Waktu 5 menit

20 menit 5 menit 5 menit 10 menit 20 menit


Penutup

Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat satu sebuah graph dengan ketentuan tertentu, kemudian diminta menentukan apakah graph tersebut bipartisi atau tidak.

20 menit 15 menit

PERTEMUAN 3 No.

Tahap

1.

Pendahuluan

2.

Penyajian

Kegiatan Pembelajaran a. Apersepsi dan motivasi Memberikan gambaran tentang permasalahan sehari-hari yang memanfaatkan teori graph.

Eksplorasi a. Memberikan definisi subgraph dan spanning sub graph. b. Membentuk siswa dalam beberapa kelompok.

Elaborasi a. Memberikan lembar kerja kepada setiap kelompok yang berisi contoh permasalahan tentang subgraph dan spanning sub graph. b. Setiap kelompok dibagi lagi menjadi 2 grup. Setiap grup menuliskan permasalahan subgraph dan spanning sub graph. c. Pada kesempatan pertama, grup I bertugas sebagai penanya dan grup II menjawab pertanyaan. Setelah itu, bergantian grup II bertanya, dan grup I menjawab.

Alokasi Waktu 5 menit 20 menit 5 menit 5 menit 10 menit 20 menit


Penutup

Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat satu sebuah graph dengan ketentuan tertentu, kemudian diminta menentukan sub graph dan spanning subgraphnya.

20 menit 15 menit

PERTEMUAN 4 No.

Tahap

1.

Pendahuluan

Kegiatan Pembelajaran

Apersepsi dan motivasi Memberikan gambaran tentang permasalahan sehari-hari yang memanfaatkan teori tentang path dan cycle.

2.

Penyajian

Eksplorasi a. Memberikan definisi tentang walk, trail, path, dan cycle. b. Membentuk siswa dalam beberapa kelompok.

Elaborasi a. Memberikan lembar kerja kepada setiap kelompok yang berisi contoh permasalahan tentang path dan cycle. b. Setiap kelompok dibagi lagi menjadi 2 grup. Setiap grup menuliskan permasalahan path dan cycle. c. Pada kesempatan pertama, grup I bertugas sebagai penanya dan grup II menjawab pertanyaan. Setelah itu, bergantian grup II bertanya, dan grup I menjawab.



Penutup

Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat satu sebuah graph dengan ketentuan tertentu, kemudian diminta menentukan walk, trai, path, and cycle.nya.

MEDIA PEMBELAJARAN Whiteboard, LCD, Laptop

SUMBER BELAJAR [1] Rinaldi Munir. 2010. Matematika Diskrit. Bandung: Informatika [2] Drs. Jong Jek Siang, M.Sc. 2009. Matematika Diskrit. Yogyakarta: Andi offset [3] Modul Kuliah

20 menit 15 menit

PENILAIAN 1. 2.

Teknik : Bentuk Instrumen :

Hasil diskusi, keaktifan dalam diskusi, hasil post-test Tes Uraian

SOAL 1 1.

Buatlah sebuah graph yang isomorphic dengan graph berikut!

2.

Diantara graph berikut mana yang saling isomorphic? (a)

(b)

(c)

(d)

(e)

(f)

Gambar 1. 6

SOAL 2 Perhatikan gambar berikut

G1

G2

Apakah kedua graph di atas merupakan bipartite graph? Jelaskan !

SOAL 3 Berikan contoh 3 spanning subgraph dari graph berikut.


: : :



: : : : : :

Kompetensi Dasar

:

Indikator

:

Tujuan

:

TEORI GRAPH MKK519515 2 SKS V 5 s.d 6 Memiliki pemahaman tentang konsep dasar teori graph, jejak, lintasan, karakteristik graph khusus, pohon, graph euler, graph hamilton, pohon, graph bidang dan pewarnaan dan mampu menerapakan konsep teori graph dalam permasalahan kehidupan nyata. 1. Mendefinisikan berbagai macam konsep graph dan membuat beberapa graph khusus. 1.6 Membuat tree serta menetukan bridge dan cut vertex 1.7 Menggunakan konsep minimum spanning tree dalam pemecahan masalah Mengkonstruksi tree serta menetukan bridge dan cut vertex. Memecahkan beberapa permasalahan menggunakan konsep minimum spanning tree.

MATERI DEFINISI DAN SIFAT SEDERHANA Definisi     

Tree adalah acyclic dan connected graph. Suatu tree T adalah suatu graf sederhana yang memenuhi : jika v dan w vertex-vertex dalam T, maka terdapat dengan tunggal simple path dari v ke w. Suatu rooted tree adalah suatu tree dimana vertex tertentu dijadikan sebagai akar. Level dari suatu tree adalah panjang dari simple path dari root v. Height dari suatu tree adalah maksimum level dari tree.

Contoh Perhatikan graph berikut 

root



level 0



level 1



level 2

Gambar 2. 1 Contoh Rooted Tree Berdasarkan contoh di atas diperoleh bahwa tree di atas memiliki height (maksimum level) 2.

Teorema : Characterisation of Trees Misal T adalah suatu graf dengan n vertex. Pernyataan berikut adalah ekuivalen : a. T adalah suatu tree b. T connected dan acyclic c. T connected dan mempunyai (n – 1) edge d. T acyclic dan mempunyai (n – 1) edge Teorema T adalah sebuah tree yang paling tidak terdiri atas 2 vertex, jika P = u 0 u1 ... un adalah path terpanjang pada T, maka u0 dan u1 keduanya berderajat 1. (Jelaskan!) Akibat teorema Setiap tree T yang paling tidak terdiri atas 2 vertex pasti memiliki lebih dari 1 vertex yang berderajat 1. Definisi Misal T adalah suatu tree dengan root v0. Andaikan bahwa x, y dan z adalah vertex-vertex dalam T dan (v0, v1, ... , vn) adalah simple path dalam T. Maka a. vn-1 adalah parent (orang tua) dari vn b. v0, v1, ... , vn-1 adalah ancestors (nenek moyang) dari vn c. vn adalah child (anak) dari vn-1

BRIDGES Teorema Misalkan e adalah salah satu edge pada graph G, dan G – e adalah subgraph dari G dengan menghilangkan edge e, maka (G)  (G – e)  (G) + 1. Buktikan! Definisi Suatu egde e pada graph G dikatakan sebagai bridge (a cut edge) jika grapg G – e memiliki lebih banyak connected components dari pada graph G. Contoh Perhatikan graph berikut.

Gambar 2. 2 Graph dengan menghilangkan 3 buah bridge

SPANNING TREE Definisi: Spanning Tree 

Suatu tree T adalah spanning tree dari suatu graf G jika T adalah subgraf dari G yang memuat semua vertex dari G.


Gambar 2. 3 Tentukan 2 buah spanning tree dari graph di atas! Definisi : Minimum Spanning Tree 

Misal G adalah suatu graf berbobot. Suatu MST dari G adalah suatu spanning tree dari G dengan bobot minimum.

Contoh Perhatikan gambar graph berbobot berikut.

B 6 A

4

2

F 6 4

1 2

C

5 3 E

2

D

Graph G Gambar graf berbobot G di atas menunjukkan enam kota dan biaya pembangunan jalan yang menghubungkan di antara pasangan kota tertentu. PROBLEM Membangun sistem jalan dengan beaya terendah yang menghubungkan enam kota tersebut. Solusi Dinyatakan dengan subgraf berupa suatu spanning tree karena harus memuat semua vertex (sehingga bahwa tiap kota termuat dalam sistem jalan itu) dan terhubung (sehingga bahwa sebarang kota bisa dicapai dari kota yang lain), serta harus mempunyai path yang tunggal diantara sepasang vertex (karena suatu graf yang memuat multiple path di antara sepasang vertex tidak mungkin menyatakan sistem beaya

minimum). Sehingga yang diperlukan adalah suatu spanning tree dengan jumlah bobot yang dimilikinya minimum. Tree semacam ini disebut dengan Minimum Spanning Tree (MST).

PRIM’S ALGORITHM Algoritma ini mencari MST dalam connected, weighted graph G. Input : Connected, weighted graph G with vertices v1, v2, ..., vn. Output : MST T 1. 2. 3.

Initialisation Let T be the graph consisting of the vertex v1 and no edges. Done? If T has n – 1 edges, STOP. (T is a MST.) Add edge Among all the edges not in T that are incident on a vertex in T and do not complete a cycle if added to T, select one having minimum weight and add it and the vertices on which it is incident to T. If more than one edge has the same minimum weight, select (v i, vj) with the smallest i, say vi0. If two or more edges (vi0, vj) have the same minimum weight, select the edge with the smallest j. Go to line 2.

Contoh Dengan Prim’s Algorithm di atas, dapat ditentukan MST dari graph G pada Gambar 2.3. a. Pilih salah satu vertex, misal dipilih vertex A. b. Banyak edge pada graph G ada 10 dengan 5 vertex, sehingga e > n – 1 artinya algorithm harus dilanjutkan. c. Berikut adalah urutan pemilihan edge-nya. (A, E) – (E, F) – (F, C) – (F, B) – (E, D) (Jelaskan mengapa demikian?) Sehingga diperoleh minimum spanning tree dengan bobot 9 sebagai berikut.

B 2 A

4

2

F 6 2

1 2

C

5 3 E

2

D

Gambar 2. 4 MST dari graph G dengan Prim’s Algorithm Apakah ada MST yang lain selain bentuk di atas??

KRUSKAL’S ALGORITHM Algoritma ini mencari MST dalam connected, weighted graph G. Input : Connected, weighted graph G with vertices v1, v2, ..., vn Output : MST T 1. 2.

Initialisation Let T be the graph consisting of no vertevertices and no edges. Done? If T has n – 1 edges, STOP. (T is a MST.)

3.

Add edge Among all the edges that if added to would not complete a cycle, choose one of minimum weight. If more than one edge has the same minimum weight, select(v i, vj) with the smallest i, say vi0. If two or more edges (vi0, vj) have the same minimum weight, select the edge with the smallest j. Add the edge and the vertices on which it is incident to T. Go to Line 2.

Contoh Dengan Prim’s Algorithm di atas, dapat ditentukan MST dari graph G pada Gambar 2.3. a. Pilih satu edge dengan bobot terkecil, yaitu (F, C). b. Banyak edge pada graph G ada 10 dengan 5 vertex, sehingga e > n – 1 artinya algorithm harus dilanjutkan. c. Berikut adalah urutan pemilihan edge-nya. (F, C) – (F, E) – (E, D) – (E, A) – (A, B) Sehingga diperoleh minimum spanning tree dengan bobot 9 sebagai berikut.

B 2 A

4

2

F 6 2

1 2

C

5 3 E

2

D

Gambar 2. 5 MST Graph G dengan Kruskal’s Algorithm Apakah ada MST lain yang bisa diperoleh dari Kruskal’s Algorithm selain bentuk di atas??

CUT VERTICES DefinisI Suatu vertex v pada graph G disebut sebagai cut vertex (articulation point) dari graph G jika (G – v)>(G). Contoh Perhatikan cut vertex dari graph G berikut.

Gambar 2. 6 Cut vertex pada graph G Jika ada, tentukan cut vertex yang lain!

METODE PEMBELAJARAN Two Stay Two Stray dan Gallery of Learning


Tahap

1.

Pendahuluan

2.

Penyajian


Apersepsi dan Motivasi Mengulas beberapa jenis graph, path dan cycle.

Eksplorasi Memberi penjelasan tentang tree, bridge dan cut vertex.

Elaborasi a. Memberikan permaslahan tentang tree, bridge dan cut vertex. b. Kegiatan Kelompok  Meminta mahasiswa secara berkelompok untuk menentukan penyelesaiannya.  Setiap kelompok menempelkan hasil diskusinya pada tempat yang telah disediakan. c. Diskusi antar kelompok  3 orang anggota kelompok diberi tugas untuk tetap berada di posisi semua untuk menjelaskan apabila ada pertanyaan atau koereksi yang nantinya diberikan kelompok lain.  3 orang yag lain ditugaskan untuk berkeliling dari satu kelompok ke kelompok yang lain untuk mengomentari dan bertanya pekerjaan kelompok lain.

Eksplanasi Diskusi kelas untuk membahas beberapa permasalahan yang sudah dibuat dikerjakan mahasiswa. 3.

Penutup

Refleksi dan Evaluasi Penarikan kesimpulan mengenai tree, bridge dan cut vertex.


15 menit

5 menit

PERTEMUAN 6 No.

Tahap

1.

Pendahuluan


Apersepsi dan Motivasi Menjelaskan penerapan graph dalam pemecahan beberapa permasalahan.

2.

Penyajian

Eksplorasi Memberi penjelasan tentang Minimum Spanning Tree..

Elaborasi a. Memberikan permaslahan Minimum Spanning Tree dalam kehidupan sehari-hari. b. Kegiatan Kelompok  Meminta mahasiswa secara berkelompok untuk menentukan penyelesaiannya.  Setiap kelompok menempelkan hasil diskusinya pada tempat yang telah disediakan. c. Diskusi antar kelompok  3 orang anggota kelompok diberi tugas untuk tetap berada di posisi semua untuk menjelaskan apabila ada pertanyaan atau koereksi yang nantinya diberikan kelompok lain.  3 orang yag lain ditugaskan untuk berkeliling dari satu kelompok ke kelompok yang lain untuk mengomentari dan bertanya pekerjaan kelompok lain.



Penutup

Refleksi dan Evaluasi Penarikan kesimpulan mengenai kegunaan Minimum Spanning Tree.

15 menit 5 menit



PENILAIAN 1. 2. 3.

Teknik : Bentuk Instrumen : Contoh instrumen :

Hasil diskusi, keaktifan dalam diskusi, hasil post-test Tes Uraian Terlampir

SOAL 1.

Tentukan semua bridges yang terdapat pada graph berikut.

Gambar 2. 7 2. 3.

Suatu graph G disebut unicyclic jika graph tersebut adalah suatu connected graph dan memuat tepat satu cycle. Berikan contoh unicyclic graph! Buktikab bahwa suatu graph G dengan n vertex dan e edge disebut unicyclic jika dan hanya jika G connected dan n = e.


: : :



: : : : : :

Kompetensi Dasar

:

Indikator Tujuan

: :

TEORI GRAPH MKK519515 2 SKS V 9 s.d 10 Memiliki pemahaman tentang konsep dasar teori graph, jejak, lintasan, karakteristik graph khusus, pohon, graph euler, graph hamilton, pohon, graph bidang dan pewarnaan dan mampu menerapakan konsep teori graph dalam permasalahan kehidupan nyata. 1. Mendefinisikan berbagai macam konsep graph dan membuat beberapa graph khusus. 1.8 Mengidentifikasi graph euler dan graph hamilton 1.8.1 Mengidentifikasi graph euler. 1.8.2 Mengidentifikasi graph hamilton.

MATERI EULER TOUR Definisi    

Sebuah trail pada graph G disebut sebagai Euler trail jika memuat setiap edge pada G Tour pada graph G adalah sebuah jalan tertutup (closed walk) yang memuat setiap edge pada graph G paling tidak sekali. Euler tour pada graph G adalah sebuah tour yang memuat setiap edge pada graph G dengan tepat sekali. Suatu graph G dikatakan Euler Graph jika graph tersebut memiliki Euler tour.

Contoh Perhatikan graph G1 dan G2 berikut.

G1

G2 Gambar 1

Apakah graph G1 dan G2 merupakan Euler graph? Jelaskan! Teorema Jika G adalah sebuah graph yang setiap vertex-nya memiliki derajat minimal 2, maka G memuat cycle.

Teorema Sebuah connected graph G adalah suatu Euler Graph jika dan hanya jika derajat dari setiap vertex-nya adalah genap.

HAMILTONIAN GRAPHS Definisi   

Hamiltonian path adalah pada graph G adalah sebuah path yang melalui setiap vertex pada graph G. Hamiltonian cycle (Hamiltonian circuit) pada graph G adalah cycle yang memuat setiap vertex pada graph G. Suatu graph G disebut sebagai Hamiltonian graph jika graph tersebut memuat Hamiltonian cycle.

Contoh (Travelling Salesman Problem) Perhatikan gambar berikut.

Gambar di atas menunjukkan 20 kota yang harus dikunjungi oleh seorang salesman. PROBLEM carilah jalur tertutup dengan mengunjungi tiap kota dengan tepat sekali dan kembali ke kota semula ! SOLUSI Ada. Bisa dimulai dari sebarang titik !!! Cycle yang ditemukan disebut dengan Hamiltonian cycle. Salah satu solusinya adalah sebagai berikut :

Definisi Suatu simple graph G disebut sebagai maximal non-Hamiltonian graph jika graph G bukan Hamiltonian graph, tetapi dengan penambahan beberapa edge yang menghubungan vertex yang tidak adjacent pada graph G dapat membentuk Hamiltonian graph.

NON-HAMILTONIAN GRAPH Perhatikan aturan berikut. Showing That a Graph Is not Hamiltonian Rule 1

:

Rule 2

:

Rule 3

:

If a vertex v has degree 2, then both of its incident edges must be part of any Hamiltonian cycle. During the construction of a hamiltonian cycle, no cycle can be formed until all the vertices have been visited. If during the construction of a Hamiltonian cycle two of the edges incident on a vertex v are shown to be required, then all other incident edges can be deleted.

METODE PEMBELAJARAN Practice Rehearsal Pairs


Tahap

1.

Pendahuluan

2.

3.

Penyajian

Penutup

Kegiatan Pembelajaran a. Apersepsi Mengulas kembali tentang Minimum Spanning Tree . b. Motivasi 1. Memberikan permasalahan Jembatan Konigsberg. 2. Mengungkapkan kesulitan yang dialami pada saat menentukan solusinya Eksplorasi Memberi penjelasan tentang Euler trail, Euler Tour, dan Euler Graph. Elaborasi a. Meminta mahasiswa berkelompok. b. Memberikan mahasiswa permasalahan tentang Euler Graph. c. Setiap kelompok dibagi menjadi dua tim, dan setiap tim harus menyelesaiakan permassalahan yang ada pada LKM. d. Setelah selesai, salah satu tim diminta menjelaskan kepada tim yang lain. Pada tahap berikutnya kedua tim bertukar peran. Eksplanasi Dosen memberikan beberapa pertanyaan kepada mahasiswa tentang permasalahan Euler Graph. Refleksi dan Evaluasi Menyimpulkan apa yang dipelajari secara klasikal tentang ciri dari euler graph.

Alokasi Waktu 5 menit 10 menit

10 menit 5 menit 5 menit 20 menit 20 menit 15 menit 10 menit

PERTEMUAN 10 No.

Tahap

1.

Pendahuluan

2.

Penyajian

Kegiatan Pembelajaran a. Apersepsi Mengulas kembali tentang Euler Graph. b. Motivasi 1. Memberikan permasalahan yang akan diselesaikan dengan Hamiltoian Graph. 2. Mengungkapkan kesulitan yang dialami pada saat menentukan penyelesaian pada kasus tersebut Eksplorasi Memberi penjelasan tentang Hamiltonian Graph.

Alokasi Waktu 5 menit 10 menit

10 menit

3.

Penutup

Elaborasi a. Meminta mahasiswa berkelompok, dan memberikan mahasiswa permasalahan yang menyangkut Hamiltoian. b. Setiap kelompok dibagi menjadi dua tim, dan setiap tim harus menyelesaiakan permassalahan yang ada pada LKM. c. Setelah selesai, salah satu tim diminta menjelaskan kepada tim yang lain. Pada tahap berikutnya kedua tim bertukar peran. Eksplanasi Dosen memberikan beberapa pertanyaan kepada mahasiswa tentang permasalahan tidak seimbang. Refleksi dan Evaluasi Menyimpulkan apa yang dipelajari secara klasikal tentang ciri Hamiltonian Graph



PENILAIAN 1. 2. 3.

Teknik : Bentuk Instrumen : Contoh Instrumen :

Hasil diskusi, keaktifan dalam diskusi, hasil post-test Tes Uraian terlampir

5 menit 5 menit 20 menit 20 menit 15 menit 10 menit

SOAL 1 Perhatikan graph berikut.

Apakah graph di atas merupakan maximal non-Hamiltonian graph? Jelaskan!

SOAL 2 Perhatikan dua graph berikut.

Graph G

Graph H

Diantara dua graph di atas, manakah yang memiliki Euler Tour dan Euler Trail?

SOAL 3 Perhatikan gambar berikut.

Gambar 3. 2 Selidiki apakah graph di atas adalah non-hamiltonian graph!


: : :



: : : : : :

Kompetensi Dasar

:

Indikator

:

Tujuan

:

TEORI GRAPH MKK519515 2 SKS V 11 s.d 12 Memiliki pemahaman tentang konsep dasar teori graph, jejak, lintasan, karakteristik graph khusus, pohon, graph euler, graph hamilton, pohon, graph bidang dan pewarnaan dan mampu menerapakan konsep teori graph dalam permasalahan kehidupan nyata. 1. Mendefinisikan berbagai macam konsep graph dan membuat beberapa graph khusus. 1.9 Mengidentifikasi sifat ke-planar-an graph 1.10 Menentukan dual dari plane graph Mengidentifikasi sifat ke-planar-an pada suatu graph. Menentukan dual dari suatu plane graph dan sebaliknya

MATERI PLANE DAN PLANAR GRAPH Definisi  

Plane graph adalah suatu graph yang digambarkan dalam suatu bidang datar, yang setiap pasang edge-nya hanya bertemu pada setiap titik akhir (jika kedua edge tersebut bertemu pada satu titik). Planar graph adalah suatu graph yang isomorphic dengan plane graph, dengan kata lain, graph tersebut dapat digambar ulang sebagai plane graph.

Contoh

G1

G2

G3 Gambar 4. 1 Lima buah planar graph

G4

Definisi 

Jordan curve adalah sebuah bidang yang dibatasi oleh kurva kontinu yang tidak memiliki potongan, dengan titik asal dan titik akhirnya berhimpit.

Contoh Perhatikan beberapa kurva berikut.

Manakah diantara kurva di atas yang merupakan Jordan curve?

Teorema 4. 1 K5, complete graph dengan 5 vertex adalah non planar. Jelaskan!

Latihan 4. 1 Tunjukkan bahwa jika e adalah suatu edge pada K5, maka K5 – e adalah planar graph. Perhatikan graph berikut.

Apakah graph di atas merupakan planar graph? Jelaskan!

FORMULA EULER Definisi 

Suatu plane graph G membuat beberapa partisi dari suatu bidang datar menjadi sejumlah daerah yang disebut sebagai face.

Teorema (Euler Formula) (Buktikan!) Jika G adalah suatu connected plane graph, misalkan n adalah banyaknya vertex, e adalah banyaknya edge, dan f adalah banyaknya face pada graph G, maka berlaku: n–e+f=2

Latihan Perhatikan gambar graph berikut!

Uji kebenaran Formula Euler pada graph diatas!

DUAL DARI PLANE GRAPH Definisi Diketahui G adalah sebuah plane graph. Dual dari graph G yang dinyatakan dengan G* didefinisikan sebagai berikut.

Untuk setiap face f pada graph G berkorespondensi dengan vertex f* pada graph G* dan setiap edge e pada G berkorespondensi dengan edge e* pada G* sedemikian sehingga jika edge e terdapat pada perbatasan 2 buah edge f dan g, maka edge e* incident dengan vertex f* dan g* pada G*. (Jika edge e adalah sebuah bridge, maka kita menghilangkan edge e kemudian korespondensi edge e* adalah sebuah loop yang incident dengan vertex f* di G*)



Contoh Perhatikan gambar dua buah graph berikut.

Gambar Sebuah Plane Graph dan dualnya

METODE PEMBELAJARAN Two Stay Two Stray dan Gallery of Learning


Tahap

1.

Pendahuluan

2.

Penyajian


Apersepsi dan Motivasi Mengulas tentang Euler Graph dan Hamiltonian Graph

Eksplorasi Memberi penjelasan tentang Plane dan Planar Graph.

Elaborasi a. Memberikan permasalahan tentang Plane dan Planar Graph b. Kegiatan Kelompok  Meminta mahasiswa secara berkelompok untuk menentukan penyelesaiannya.  Setiap kelompok menempelkan hasil diskusinya pada tempat yang telah disediakan. c. Diskusi antar kelompok  3 orang anggota kelompok diberi tugas untuk tetap berada di posisi semua untuk menjelaskan apabila ada pertanyaan atau koereksi yang nantinya diberikan kelompok lain.  3 orang yag lain ditugaskan untuk berkeliling dari satu kelompok ke kelompok yang lain untuk mengomentari dan bertanya pekerjaan kelompok lain.


Penutup

Refleksi dan Evaluasi Penarikan kesimpulan mengenai ke-planar-an graph.


20 menit

5 menit

PERTEMUAN 12 No.

Tahap

1.

Pendahuluan


Apersepsi dan Motivasi Memberikan contoh permasalahan Plane Graph dan aplikasi dual dari plane graph.

2.

Penyajian

Eksplorasi Memberi penjelasan tentang teknik penyusunan dual dari suatu plane graph.

Elaborasi a. Memberikan permaslahan Dual dari Plane Graph. b. Kegiatan Kelompok  Meminta mahasiswa secara berkelompok untuk menentukan penyelesaiannya.  Setiap kelompok menempelkan hasil diskusinya pada tempat yang telah disediakan. c. Diskusi antar kelompok  3 orang anggota kelompok diberi tugas untuk tetap berada di posisi semua untuk menjelaskan apabila ada pertanyaan atau koereksi yang nantinya diberikan kelompok lain.  3 orang yag lain ditugaskan untuk berkeliling dari satu kelompok ke kelompok yang lain untuk mengomentari dan bertanya pekerjaan kelompok lain.


Penutup

Refleksi dan Evaluasi Penarikan kesimpulan mengenai Dual dari suatu Plane Graph.



PENILAIAN 1. 2. 3.


Hasil diskusi, keaktifan dalam diskusi, hasil post-test Tes Uraian terlampir


20 menit

5 menit

SOAL 1.

Perhatikan kedua graph berikut.

Gambar 4. 2 2.

Tentukan dual dari kedua graph di atas! Perhatikan kedua graph berikut.

Graph G1

Graph G2 Gambar 4. 3

a. b. c.

Apakah kedua graph di atas adalah sepasang isomorphic graph? Gambarkan dual dari kedua graph di atas! Apakah dual dari kedua graph di atas adalah sepasang isomorphic graph? Jelaskan!


: : :



: : : : : :

Kompetensi Dasar Indikator

: :

Tujuan

:

TEORI GRAPH MKK519515 2 SKS V 13 Memiliki pemahaman tentang konsep dasar teori graph, jejak, lintasan, karakteristik graph khusus, pohon, graph euler, graph hamilton, pohon, graph bidang dan pewarnaan dan mampu menerapakan konsep teori graph dalam permasalahan kehidupan nyata. 2. Menggunakan konsep graph dalam pemecahan masalah. 2.1 Menentukan bilangan kromatis pada pewarnaan graph 2.2 Menggunakan konsep pewarnaan dalam pemecahan masalah Menentukan bilangan kromatis pada pewarnaan graph, dan melakukan pewarnaan pada graph Menggunakan konsep pewarnaan dalam pemecahan masalah

MATERI PENDAHULUAN Macam Pewarnaan Graph 1.

2. 3.

Pewarnaan simpul (vertex colouring) yaitu teknik mewarnai semua vertex pada graph sehingga tidak ada vertex – vertex yang saling adjacent memiliki warna yang sama dan jumlah warna yang digunakan diusahakan seminimal mungkin. Pewarnaan sisi (edge colouring) Pewarnaan wilayah(face colouring) Pewarnaan edge dan face hanyalah bentuk lain dari pewarnaan vertex dan dapat diubah kembali menjadi model pewarnaan vertex.

VERTEX COLOURING Definisi 5. 1 Bilangan kromatik 

Jumlah warna minimum yang dapat digunakan untuk mewarnai semua vertex disebut bilangan kromatik dari graph G, dan disimbolkan dengan χ(G).

Sifat-sifat bilangan kromatik 1. 2. 3. 4. 5. 6. 7.

χ(G) = 1 jika dan hanya jika G adalah graph kosong. (mengapa?) χ(G) ≥ 3 jika dan hanya jika Gmemiliki subgraph yang merupakan K 3. Untuk setiap graph planar berlaku χ(G) ≤ 4. Graph lengkap Kn memiliki χ(G) = n. Graph Lingkaran Cn memiliki χ(G) =2 bila n genap dan χ(G) =3 bila n ganjil. Bipartite graph selalu bisa diwarnai dengan2 warna. Graph yang berupa pohon selalu dapat diwarnai dengan2 warna.

ALGORITMA PEWARNAAN 1. 2. 3. 4. 5.

Untuk inisialisasi, catat semua vertex yang ada beserta derajat tiap vertex. Urutkan vertex berdasarkan derajatnya dari besar ke kecil. Cari vertex dengan derajat terbesar dan belum terwarnai, berikan warna ke vertex tersebut. Cari vertex lain yang belum diwarnai, tidak adjacent dengan vertex langkah nomor 3, dan tidak adjacent dengan vertex berwarna sama. Ulangi ke langkah nomor 3 sampai semua vertex terwarnai.

Contoh 5. 1 Perhatikan graph berikut

Gambar 5. 1 Bagaimana cara memberikan warna di setiap vertex pada graph tersebut?

SOLUSI Berikut adalah solusinya.

EDGE AND FACE COLOURING Contoh 5. 2 Perhatikan kembali graph pada gambar 5.2 dalam memberikan warna pada setiap edge-nya?

SOLUSI

Contoh 5.1. Bagaimana hasilnya jika kita akan

Bagaimana dengan face colouring?

Contoh 5. 3 Perhatikan graph berikut.

Gambar 5. 2 Hasil dari face colouring adalah sebagai berikut.

Gambar 5. 3 Bagaimana bisa demikian?

METODE PEMBELAJARAN Kelompok belajar (The Study Group)


Tahap

1.

Pendahuluan


Apersepsi dan Motivasi Memberikan gambaran tentang manfaat pewarnaan graph dalam menyelesaikan permasalahan.

2.

Penyajian

Eksplorasi Memberikan penjelasan tetang jenis dan teknik pewrnaan graph.

Elaborasi a. Membentuk siswa dalam beberapa kelompok. b. Setiap kelompok diminta menentukan penyelesaian permasalahan pewarnaan graph.


Penutup

Refleksi dan Evaluasi Menyimpulkan cara penentuan solusi pada permasalahan pewarnaan graph

Alokasi Waktu 15 menit 5 menit 10 menit 50 menit 50 menit

20 menit



PENILAIAN 1. 2. 3.


Hasil diskusi, keaktifan dalam diskusi, hasil post-test Tes Uraian

APLIKASI COLOURING Latihan 5. 1 1.

Berikut ini adalah peta dari suatu kecamatan yang terdiri dari 5 kelurahan. Warnailah peta tersebut dengan warna minimal!

2.

Misalkan terdapat delapan orang mahasiswa (M1, M2, M3, M4, ... , M8) dan lima buah mata kuliah yang dapat dipilihnya (A, B, C, D, E). Tabel berikut memperlihatkan matriks antara mahasiswa dan mata kuliah yang dipilihnya. Angka 1 menunjukkan bahwa mahasiswa memilih mata kuliah tersebut. Mahasiswa M1 M2 M3 M4 M5 M6 M7 M8

A

1 1

Mata Kuliah B C D 1 1 1 1 1 1 1 1 1 1 1 1 1

E 1

Berapa paling sedikit jumlah hari yang dibutuhkan untuk jadwal ujian tersebut sedemikian sehingga semua mahasiswa dapat mengikuti ujian mata kuliah yang diambilnya tanpa bertabrakan waktunya dengan jadwal ujian kuliah lain yang juga diambilnya?

PERANGKAT PEMBELAJARAN

Recommend Documents