matematika diskrit

Matematika Diskrit

Teori Graf

Makalah pertama tentang teori graf ditulis pada tahun 1736 oleh

seorang matematikawan Swiss yang bernama Leonard Euler. Ia

menggunakan teori graf untuk menyelesaikan masalah jembatan

Königsberg (sekarang, bernama Kaliningrad). Berikut adalah ilustrasi

masalah tersebut :

Gambar 1. Masalah Jembatan Königsberg (Rossen, 2003)

Sejarah Graf

Masalah yang dikemukakan Euler : Dapatkah melewati setiap

jembatan tepat sekali dan kembali lagi ke tempat semula? Berikut

adalah sketsa yang merepresentasikan ilustrasi jembatan Königsberg

yang pada gambar diatas. Himpunan titik yaitu {A, B, C, D}

merepresentasikan sebagai daratan, dan garis yang menghubungkan

titik-titik tersebut adalah sebagai jembatan.

Gambar 2. Representasi graf masalah jembatan Königsberg

Sejarah Graf

Jawaban pertanyaan Euler adalah

tidak mungkin. Agar bisa melalui setiap

jembatan tepat sekali dan kembali lagi

ke tempat semula maka jumlah

jembatan yang menghubungkan setiap

daratan harus genap.

Sejarah Graf

Graf adalah suatu diagram yang memuat informasi

tertentu jika diinterprestasikan secara tepat. Tujuannya

adalah sebagai visualisasi objek – objek agar lebih mudah

dimengerti.

Tiap – tiap diagram memuat sekumpulan objek (kotak,

titik, dan lain – lain) beserta garis – garis yang

menghubungkan objek – objek tersebut. Representasi

visual dari graf adalah menyatakan objek dinyatakan

sebagai noktah, bulatan, atau titik, sedangkan hubungan

antara objek dinyatakan dengan garis.

Teori Graf

Dasar – Dasar Graf

Definisi 1

Suatu graf terdiri dari 2 himpunan yang berhingga, yaitu himpunan

titik – titik tidak kosong (simbol V(G)) dan himpunan garis – garis

(simbol E(G)).

Graf G didefinisikan sebagai pasangan himpunan (V, E), di tulis

dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak-

kosong dari simpul – simpul (vertice and node) dan E adalah himpunan

sisi (edges and arcs) yang menghubungkan sepasang simpul.

v

Definisi di atas menyatakan bahwa V tidak boleh kosong,

sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan

tidak mempunyai sisi satu buah pun, tetapi simpulnya

harus ada, minimal satu. Graf yang hanya mempunyai satu

buah simpul tanpa sebuah sisi dinamakan Graf Trivial.

Graf dinyatakan dengan gambar. Gambar suatu Graf G

terdiri dari himpunan titik – titik atau simpul V(G),

himpunan garis – garis atau sisi yang dinyatakan dengan

E(G) yang menghubungkan titik tersebut (beserta arah

garis pada graf berarah), dan label pada garisnya (jika

ada).

Dasar – dasar Graf

v

Simpul pada graf dapat dinomori dengan

huruf, seperti a, b, c, …., v, w, … dengan

bilangan asli 1, 2, 3, … , atau gabungan dari

keduanya. Sedangkan sisi yang menghubungkan

simpul u dengan simpul v dinyatakan dengan

pasangan (u,v) atau dinyatakan dengan

lambang e1, e2, … Dengan kata lain, jika e

adalah sisi yang menghubungkan simpul u dan

v, maka e dapat di tulis sebagai

e = (u,v)


Secara geometri graf di gambarkan sebagai sekumpulan

noktah (simpul) yang di hubungkan dengan sejumlah garis.

Dan berikut adalah beberapa contoh Graf.

Setiap garis berhubungan dengan satu atau dua

titik. Titik – titik tersebut dinamakan Titik Ujung.

Garis yang hanya berhubungan dengan satu titik

ujung disebut Loop.

Dua garis berbeda yang menghubungkan titik

yang sama disebut Garis Paralel.

Dua titik dikatakan Berhubungan (adjacent) jika

ada garis yang menghubungkan keduanya.


Titik yang tidak memiliki garis yang berhubungan

dengannya disebut Titik Terasing (Isolating

Point)

Graf yang tidak memiliki titik (sehingga tidak

memiliki garis) disebut Graf Kosong.


Perhatikan gambar berikut ini:

Gambar tesebut memperlihatkan tiga buah graf, G1, G2, dan

G3.

G1 adalah graf dengan himpunan simpul V dan

Himpunan sisi E adalah :

V (G) = {1, 2, 3, 4}

E (G) = {(1,2), (1,3), (2,3), (2,4), (3,4)}

G2 adalah graf dengan himpunan simpul V dan

Himpunan sisi E adalah :

V (G) = {1, 2, 3, 4}

E (G) = {(1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4)}

Himp. Ganda.

= {e1, e2, e3, e4, e5, e6, e7}

G3 adalah graf dengan himpunan simpul V dan Himpunan

sisi E adalah :

V (G) = {1, 2, 3, 4}

E (G) = {(1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4), (3, 3)}

Himp. Ganda

= {e1, e2, e3, e4, e5, e6, e7, e8}

Pada G2, sisi e3 = (1,3) dan sisi e4 = (1,3) dinamakan Sisi Ganda

(Multiple edges atau paralel adges) karena kedua simpul

menghubungkan dua buah simpul yang sama, yaitu simpul 1 dengan

simpul 3.

Pada G3, sisi e8 = (3,3) dinamakan Gelang atau Kalang atau disebut

juga sebagai Loop, karena dia berawal dan berakhir di simpul yang

sama.

Contoh Soal

Ada 7 kota (A,..,G) yang beberapa diantaranya dapat

dihubungkan secara langsung dengan jalan darat. Hubungan –

hubungan langsung yang dapat dilakukan adalah sebagai berikut :

A dengan B

A dengan D

B dengan D

C dengan B

E dengan F

Buatlah graf yang menunjukan keadaan transportasi di 7 kota

tesebut:

Contoh Soal

Penyelesaian :

Misalkan kota – kota dianggap sebagai titik – titik. Dua titik / atau

lebih dihubungkan dengan garis bila dan hanya bila ada jalan yang

menghubungkan langsung kedua kota tersebut. Untuk itu keadaan

transportasi dalam kota tersebut adalah sebagai berikut :

Dalam graf tersebut, e1 berhubungan

dengan titik A dan B (keduanya disebut

titik ujung e1). Titik A dan Bdikatakan

berhubungan, sedangkan titik A dan C

tidak berhubungan karena tidak ada garis

yang menghubungkannya secara langsung.

Titik G adalah titik terasing karena tidak

ada garis yang berhubungan dengan G.

Soal latihan

Gambarlah Graf G dengan titik V(G) = {V1, V2,

V3, V4} dan garis E(G) = {e1, e2, e3, e4, e5}

dengan titik-titik ujung berikut : Garis Titik Ujung

e1 {V1, V3}

e2 {V2,V4}

e3 {V1}

e4 {V2,V4}

e5 {V3}

Soal latihan

Gambarlah Graf G dengan titik V(G) = {V1, V2,

V3, V4, V5, V6} dan garis E(G) = {e1, e2, e3, e4,

e5, e6} dengan titik-titik ujung berikut :

Garis Titik Ujung

e1 {V1, V6}

e2 {V1,V2}

e3 {V2, V3}

e4 {V3,V4}

e5 {V4,V5}

e6 {V5,V6}

Soal latihan

Dalam graf G pada gambar berikut, tentukan :

a. Himpunan titik – titik, himpunan garis – garis, titik – titik

ujung masing – masing garis, dan garis paralel.

b. Loop dan titik Terasing.

Jenis – jenis graf Graf Sederhana (Simple graf) adalah graf yang tidak mengandung Loop

maupun Garis Paralel. Graf d bawah ini adalah contoh graf sederhana.

Pada graf sederhana, sisi adalah pasangan tak-terurut (Unordered

Pairs). Jadi menuliskan sisi (u,v) sama saja dengan (v,u). Kita juga

dapat mendeskripsikan graf sederhana G=(V,E) terdiri dari himpunan

tidak kosong simpul-simpul dan E adalah himpunan pasangan tak-

terurut yang berbeda yang disebut sisi.

Jenis – jenis Graf

Graf tak sederhana (Unsimple-graph), adalah graf yang

mengandung garis paralel atau Loop. Ada dua macam Graf

tak sederhana, yaitu :

1. Graf Ganda (MultiGraph), adalah graf yang mengandung

sisi ganda (garis paralel). Sisi ganda yang

menghubungkan sepasang simpul bisa lebih dari dua

buah.

Jenis – jenis graf

2. Graf Semu (Pseudograph), adalah graf yang

mengandung Loop. Contoh geaf di bawah ini

disebut graf semu walaupun memiliki sisi ganda

sekalipun.


Sisi pada graf dapat mempunyai orientasi arah,

berdasarkan orientasi arah pada sisi, maka secara umum

graf dibedakan atas 2 jenis :

Graf Tak Berarah , adalah graf yang sisinya tidak

mempunyai orientasi arah disebut graf tak berarah. Pada

graf tak – berarah, urutan pasangan simpul yang

dihubungkan oleh sisi tidak di perhatikan. Jadi (u,v) =

(v,u) adalah sisi yang sama.


Graf Berarah , adalah graf yang setiap sisinya

diberikan orientasi arah. Sisi berarah disebut sebagai

arch (busur). Pada graf berarah, (u,v) dan (v,u)

menyatakan dua buah busur yang berbeda. Untuk

simpul (u,v), simpul u dinamakan simpul asal dan

simpul v disebut sebagai Simpul Terminal.

matematika diskrit

Documents