perangkat pembelajaran - … · c. deskripsi mata kuliah teori graph adalah mata kuliah yang...

PERANGKAT PEMBELAJARAN

MATA KULIAH : TEORI GRAPH

KODE : MKK519515

DOSEN : 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.


UNIVERSITAS VETERAN BANGUN NUSANTARA

SUKOHARJO

A. Identitas Mata Kuliah

Mata Kuliah : TEORI GRAPH

Semester / SKS : III / 2 SKS

Pengampu Mata Kuliah : EDY MULYONO, M.Pd.

Kode Mata Kuliah : MKK519515

B. 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 Indikator

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

1.6 Membuat tree serta menetukan bridge dan cut vertex

1.7 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. Menggunakan konsep graph

dalam pemecahan masalah.

2.1 Menentukan bilangan kromatis pada pewarnaan graph

2.2 Menggunakan konsep pewarnaan dalam pemecahan

masalah

E. Organisasi Materi

F. 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

KD I KD II

H. Penilaian Dan Kriteria Pembelajaran 1. Presensi dan Keaktifan : 30 %

2. Tugas Terstruktur : 20 %

3. UTS : 20 %

4. UAS : 30 %

100 %

I. Jadwal Perkuliahan

Pertemuan P E M B E L A J A R A N

1 Materi :

Menjelaskan definisi dasar graph

2 Materi :

Menentukan sifat isomorphisme graph

3 Materi :

Mengidentifikasi sifat bipartite pada graph

4 Materi :

Menentukan subgraph dari suatu graph

Menentukan path dan cycle pada suatu graph

5 Materi :

Membuat tree serta menetukan bridge dan cut vertex

6 Materi :

Menggunakan konsep minimum spanning tree dalam pemecahan masalah

7 QUIZ I

8 Ujian Tengah Semester

9 Materi :

Mengidentifikasi graph euler

10 Materi :

Mengidentifikasi graph hamilton

11 Materi :

Mengidentifikasi sifat ke-planar-an graph

12 Materi :

Menentukan dual dari plane graph

13 Materi :

Menentukan bilangan kromatis pada pewarnaan graph

Menggunakan konsep pewarnaan dalam pemecahan masalah

14 QUIZ II

15 REVIEW:

Persiapan Ujian Semester

16 Ujian Akhir Semester

UNIVERSITAS VETERAN BANGUN NUSANTARA SUKOHARJO


SILABUS

Program Studi : PENDIDIKAN MATEMATIKA



Bobot : 2 SKS

Semester : V

Mata Kuliah Prasyarat : Logika dan Himpunan, Riset Operasi

Standar Kompetensi : 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.

Kompetensi Dasar Indikator Pengalaman Belajar Materi Pokok

Alokasi

Waktu

(menit)

Sumber/ Bahan/

Alat

Penilaian/

Evaluasi

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

1.6 Membuat tree serta menetukan

bridge dan cut vertex

1.7 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

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

Graph theory

Trees

Euler tour dan

Hamiltonian Cycle

Plane dan Planar

Graph

12 150 Sumber :

Buku panduan

mata kuliah

TEORI GRAPH

Alat :

Laptop, LCD,

Whiteboard

Bentuk

evaluasi :

Pre-test

Post-test

Instrumen :

Lembar

Kerja

Individu

Lembar

Kegiatan

kelompok

2. Menggunakan

konsep graph

dalam

pemecahan

masalah.

2.1 Menentukan bilangan kromatis

pada pewarnaan graph

2.2 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

Alat :

Laptop, LCD,

Whiteboard

Bentuk

evaluasi :

Pre-test

Post-test

Instrumen :

Lembar

Kerja

Individu

Lembar

Kegiatan

kelompok

RENCANA MUTU PERKULIAHAN (RMP)

Nama Dosen : ERIKA LARAS ASTUTININGTYAS, M.Pd.

Fakultas : KEGURUAN DAN ILMU PENDIDIKAN




Bobot : 2 SKS

Semester : V

Pertemuan ke- : 1 s.d 4

Standart Kompetensi : 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.

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

graph khusus.

Indikator : 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

Tujuan : 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. Elemen-

elemen 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 eE 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 eE dikawankan dengan suatu pasangan berurutan vertex-

vertex. 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 eE 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 vV yang tidak terhubung dengan setiap egde pada graph G dikatakan sebagai

isolated vertex.

b. Jika ada dua buah vertex u,vV terhubung dengan sebuah sisi eE maka dapat dikatakan bahwa

vertex u,v incident dengan edge e, serta dapat pula dikatakan bahwa vertex u dan vertex v adjacent.

Definisi

a. Suatu graph G dikatakan simple graph jika graph tersebut tidak memiliki loop dan parallel edge.

b. 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 satu-

satu 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. Bipartite graph adalah suatu graf yang vertex-vertex nya dapat dipartisi menjadi himpunan disjoint V1

dan V2 dengan setiap edge incident pada satu vertex di V1 dan satu vertex di V2.

b. 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.

Graph G1 Graph G2

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 G2. 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.

Contoh


Gambar 1. 2

Tentukan derajat setiap vertex pada graph tersebut!

a b

c

d e

f

a

b

c

d

e

f

Teorema (Handshaking Theorem)

Untuk setiap graph G dengan e edge dan n vertex, v1, v2, ..., vn, berlaku:

n

1iivd = 2e

(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.

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 v0

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.

a b

c d

a b

c d

e f

g h

e f

g h

G1 G2 G3

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.

Contoh


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 Kegiatan Pembelajaran Alokasi

Waktu

1. Pendahuluan a. Apersepsi

Memberi gambaran tentang pemanfaatan graph dan memberikan

gambaran tentang permasalahan sehari-hari yang memanfaatkan

teori graph.

5 menit

2. Penyajian 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.

10 menit

20 menit

5 menit

5 menit

5 menit

20 menit

15 menit

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.

15 menit

PERTEMUAN 2


Waktu


Memberi gambaran tentang bipartisi graph.

b. Motivasi

Memberikan gambaran tentang permasalahan sehari-hari yang

memanfaatkan teori graph.

5 menit

2. Penyajian Eksplorasi a. Memberikan definisi bipartisi graph.

b. Membentuk siswa dalam beberapa kelompok.


contoh permasalahan tentang bipartisi graph.


menuliskan permasalahan bipartisi graph.






20 menit

5 menit

5 menit

10 menit

20 menit

20 menit


dengan ketentuan tertentu, kemudian diminta menentukan apakah

graph tersebut bipartisi atau tidak.

15 menit

PERTEMUAN 3


Waktu

1. Pendahuluan a. Apersepsi dan motivasi

Memberikan gambaran tentang permasalahan sehari-hari yang

memanfaatkan teori graph.

5 menit

2. Penyajian Eksplorasi a. Memberikan definisi subgraph dan spanning sub graph.



contoh permasalahan tentang subgraph dan spanning sub graph.


menuliskan permasalahan subgraph dan spanning sub graph.






20 menit

5 menit

5 menit

10 menit

20 menit

20 menit


dengan ketentuan tertentu, kemudian diminta menentukan sub

graph dan spanning subgraphnya.

15 menit

PERTEMUAN 4


Waktu

1. Pendahuluan Apersepsi dan motivasi Memberikan gambaran tentang permasalahan sehari-hari yang

memanfaatkan teori tentang path dan cycle.

5 menit

2. Penyajian Eksplorasi a. Memberikan definisi tentang walk, trail, path, dan cycle.



contoh permasalahan tentang path dan cycle.


menuliskan permasalahan path dan cycle.






20 menit

5 menit

5 menit

10 menit

20 menit

20 menit


dengan ketentuan tertentu, kemudian diminta menentukan walk,

trai, path, and cycle.nya.

15 menit

MEDIA PEMBELAJARAN

Whiteboard, LCD, Laptop

SUMBER BELAJAR



[3] Modul Kuliah

PENILAIAN

1. Teknik : Hasil diskusi, keaktifan dalam diskusi, hasil post-test

2. Bentuk Instrumen : 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.







Bobot : 2 SKS

Semester : V







graph khusus.

Indikator : 1.6 Membuat tree serta menetukan bridge dan cut vertex

1.7 Menggunakan konsep minimum spanning tree dalam pemecahan

masalah

Tujuan : 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


Gambar 2. 1 Contoh Rooted Tree

Berdasarkan contoh di atas diperoleh bahwa tree di atas memiliki height (maksimum level) 2.

root level 0

level 1

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 = u0 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


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.

Contoh


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.

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

B

A

C

D E

F

6

4

6

2 4

1

5 2

2

3

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. Initialisation

Let T be the graph consisting of the vertex v1 and no edges.

2. Done?

If T has n – 1 edges, STOP. (T is a MST.)

3. 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 (vi, 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.

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. Initialisation

Let T be the graph consisting of no vertevertices and no edges.

2. Done?

If T has n – 1 edges, STOP. (T is a MST.)

B

A

C

D E

F

2

2

6

2 4

1

5 2

2

3

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(vi, 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.

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!

B

A

C

D E

F

2

2

6

2 4

1

5 2

2

3

METODE PEMBELAJARAN

Two Stay Two Stray dan Gallery of Learning


PERTEMUAN 5


Waktu

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

5 menit

2. Penyajian 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.

20 menit

5 menit

15 menit

5 menit

30 menit

15 menit

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

5 menit

PERTEMUAN 6


Waktu

1. Pendahuluan Apersepsi dan Motivasi Menjelaskan penerapan graph dalam pemecahan beberapa

permasalahan.

5 menit

2. Penyajian Eksplorasi Memberi penjelasan tentang Minimum Spanning Tree..

Elaborasi a. Memberikan permaslahan Minimum Spanning Tree dalam

kehidupan sehari-hari.



penyelesaiannya.












20 menit

5 menit

15 menit

5 menit

30 menit

15 menit

3. Penutup Refleksi dan Evaluasi Penarikan kesimpulan mengenai kegunaan Minimum Spanning

Tree.

5 menit

MEDIA PEMBELAJARAN


SUMBER BELAJAR



[3] Modul Kuliah

PENILAIAN



3. Contoh instrumen : Terlampir

SOAL

1. Tentukan semua bridges yang terdapat pada graph berikut.

Gambar 2. 7

2. Suatu graph G disebut unicyclic jika graph tersebut adalah suatu connected graph dan memuat tepat

satu cycle. Berikan contoh unicyclic graph!

3. Buktikab bahwa suatu graph G dengan n vertex dan e edge disebut unicyclic jika dan hanya jika G

connected dan n = e.







Bobot : 2 SKS

Semester : V







graph khusus.

Indikator : 1.8 Mengidentifikasi graph euler dan graph hamilton

Tujuan : 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 : If a vertex v has degree 2, then both of its incident edges must be part of any

Hamiltonian cycle.

Rule 2 : During the construction of a hamiltonian cycle, no cycle can be formed until all the

vertices have been visited.

Rule 3 : 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


PERTEMUAN 9


Waktu


Mengulas kembali tentang Minimum Spanning Tree .

b. Motivasi

1. Memberikan permasalahan Jembatan Konigsberg.

2. Mengungkapkan kesulitan yang dialami pada saat

menentukan solusinya

5 menit

10 menit

2. Penyajian 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.

10 menit

5 menit

5 menit

20 menit

20 menit

15 menit

3. Penutup Refleksi dan Evaluasi

Menyimpulkan apa yang dipelajari secara klasikal tentang ciri dari

euler graph.

10 menit

PERTEMUAN 10


Waktu


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

5 menit

10 menit

2. Penyajian Eksplorasi

Memberi penjelasan tentang Hamiltonian Graph.

10 menit

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.

5 menit

5 menit

20 menit

20 menit

15 menit

3. Penutup Refleksi dan Evaluasi

Menyimpulkan apa yang dipelajari secara klasikal tentang ciri

Hamiltonian Graph

10 menit

MEDIA PEMBELAJARAN


SUMBER BELAJAR



[3] Modul Kuliah

PENILAIAN



3. Contoh Instrumen : terlampir

SOAL 1


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!







Bobot : 2 SKS

Semester : V







graph khusus.

Indikator : 1.9 Mengidentifikasi sifat ke-planar-an graph

1.10 Menentukan dual dari plane graph

Tujuan : 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 G4

Gambar 4. 1 Lima buah planar graph

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.


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


PERTEMUAN 11


Waktu

1. Pendahuluan Apersepsi dan Motivasi Mengulas tentang Euler Graph dan Hamiltonian Graph

5 menit

2. Penyajian Eksplorasi Memberi penjelasan tentang Plane dan Planar Graph.

Elaborasi a. Memberikan permasalahan tentang Plane dan Planar Graph



penyelesaiannya.












20 menit

5 menit

20 menit

5 menit

20 menit

20 menit

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

5 menit

PERTEMUAN 12


Waktu

1. Pendahuluan Apersepsi dan Motivasi Memberikan contoh permasalahan Plane Graph dan aplikasi dual

dari plane graph.

5 menit

2. Penyajian Eksplorasi Memberi penjelasan tentang teknik penyusunan dual dari suatu

plane graph.

Elaborasi a. Memberikan permaslahan Dual dari Plane Graph.



penyelesaiannya.












20 menit

5 menit

20 menit

5 menit

20 menit

20 menit

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

5 menit

MEDIA PEMBELAJARAN


SUMBER BELAJAR



[3] Modul Kuliah

PENILAIAN



3. Contoh Instrumen : terlampir

SOAL

1. Perhatikan kedua graph berikut.

Gambar 4. 2

Tentukan dual dari kedua graph di atas!

2. Perhatikan kedua graph berikut.

Graph G1 Graph G2

Gambar 4. 3

a. Apakah kedua graph di atas adalah sepasang isomorphic graph?

b. Gambarkan dual dari kedua graph di atas!

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







Bobot : 2 SKS

Semester : V

Pertemuan ke- : 13





Kompetensi Dasar : 2. Menggunakan konsep graph dalam pemecahan masalah.

Indikator : 2.1 Menentukan bilangan kromatis pada pewarnaan graph

2.2 Menggunakan konsep pewarnaan dalam pemecahan masalah

Tujuan : Menentukan bilangan kromatis pada pewarnaan graph, dan melakukan

pewarnaan pada graph

Menggunakan konsep pewarnaan dalam pemecahan masalah

MATERI

PENDAHULUAN

Macam Pewarnaan Graph

1. 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.

2. Pewarnaan sisi (edge colouring)

3. 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. χ(G) = 1 jika dan hanya jika G adalah graph kosong. (mengapa?)

2. χ(G) ≥ 3 jika dan hanya jika Gmemiliki subgraph yang merupakan K3.

3. Untuk setiap graph planar berlaku χ(G) ≤ 4.

4. Graph lengkap Kn memiliki χ(G) = n.

5. Graph Lingkaran Cn memiliki χ(G) =2 bila n genap dan χ(G) =3 bila n ganjil.

6. Bipartite graph selalu bisa diwarnai dengan2 warna.

7. Graph yang berupa pohon selalu dapat diwarnai dengan2 warna.

ALGORITMA PEWARNAAN

1. Untuk inisialisasi, catat semua vertex yang ada beserta derajat tiap vertex.

2. Urutkan vertex berdasarkan derajatnya dari besar ke kecil.

3. Cari vertex dengan derajat terbesar dan belum terwarnai, berikan warna ke vertex tersebut.

4. Cari vertex lain yang belum diwarnai, tidak adjacent dengan vertex langkah nomor 3, dan tidak

adjacent dengan vertex berwarna sama.

5. Ulangi ke langkah nomor 3 sampai semua vertex terwarnai.

Contoh 5. 1


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 Contoh 5.1. Bagaimana hasilnya jika kita akan

memberikan warna pada setiap edge-nya?

SOLUSI

Bagaimana dengan face colouring?

Contoh 5. 3


Gambar 5. 2

Hasil dari face colouring adalah sebagai berikut.

Gambar 5. 3

Bagaimana bisa demikian?

METODE PEMBELAJARAN

Kelompok belajar (The Study Group)


PERTEMUAN 13


Waktu

1. Pendahuluan Apersepsi dan Motivasi Memberikan gambaran tentang manfaat pewarnaan graph dalam

menyelesaikan permasalahan.

15 menit

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.



5 menit

10 menit

50 menit

50 menit

3. Penutup Refleksi dan Evaluasi Menyimpulkan cara penentuan solusi pada permasalahan pewarnaan

graph

20 menit

MEDIA PEMBELAJARAN


SUMBER BELAJAR



[3] Modul Kuliah

PENILAIAN



3. Contoh Instrumen :

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 Mata Kuliah

A B C D E

M1 1 1

M2 1 1

M3 1 1

M4 1 1

M5 1 1

M6 1 1

M7 1 1

M8 1 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 - … · c. deskripsi mata kuliah teori graph adalah mata kuliah yang...

Documents