matematika diskrit
Post on 27-Jan-2016
156 Views
Preview:
DESCRIPTION
TRANSCRIPT
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)
Dasar – dasar Graf
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.
Dasar – dasar Graf
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.
Dasar – dasar Graf
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.
Jenis – jenis graf
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.
Jenis – jenis graf
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.
top related