Jumat, 08 Januari 2010

tugas kuliah

Graf Berarah (Digraf)
Di dalam situasi yang dinamis, seperti pada komputer digital ataupun pada sistem aliran (flow system), konsep graf berarah lebih sering digunakan dibandingkan dengan konsep graf tak berarah.
Apabila ruas suatu graf berarah mempunyai suatu bobot, graf berarah tersebut dinamakan suatu jaringan atau network.
Beberapa Pengertian dalam graf berarah :
• Derajat ke luar (out degree) suatu simpul adalah banyaknya ruas yang mulai / keluar dari simpul tersebut.
• Derajat ke dalam (in degree) suatu simpul adalah banyaknya ruas yang berakhir / masuk ke simpul tersebut.
• Simpul berderajat ke dalam = 0 disebut sumber (source), sedangkan simpul berderajat ke luar = 0 disebut muara (sink).
• Pengertian Walk, Trail, Path (Jalur) dan Sirkuit (Cycle) berlaku pula pada graf berarah, dimana harus sesuai dengan arah ruas. Kalau tidak sesuai dengan arah ruas-nya, maka disebut sebagai semi walk, semi path atau semi trail.
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 2
Pada graf berarah terdapat 3 pengertian keterhubungan, yakni :
• Terhubung lemah, jika terdapat suatu semi path antara setiap 2 simpul dari D.
• Terhubung unilateral, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari u ke v atau dari v ke u.
• Terhubung kuat, jika antara setiap 2 simpul u dan v dari D, terdapat jalur dari u ke v dan dari v ke u.
Contoh :
RELASI DAN MATRIKS
Pandang D(V,A) suatu graf berarah tanpa ruas sejajar, maka A adalah himpunan bagian dari V x V (produk Cartesis himpunan), jadi merupakan Relasi pada V. Sebaliknya bila R adalah Relasi pada suatu himpunan V, maka D(V,R) merupakan graf berarah tanpa ruas sejajar. Jadi konsep Relasi dan konsep graf berarah tanpa ruas sejajar adalah satu dan sama.
Misalkan D(V,A) suatu graf berarah dengan simpul v1, v2, … , vm. Matriks M berukuran (mxm) merupakan matriks (matriks adjacency) dari D, dengan mendefinisikan sebagai berikut :
M = (Mij), dengan mij banyaknya ruas yang mulai di vi dan berakhir di vj
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 3
Bila D tidak mengandung ruas berganda, maka elemen M adalah 0 dan 1. Kalau Graf berarah mengandung ruas berganda, elemen M merupakan bilangan bulat non negatif.
Jadi suatu matriks berukuran (mxm) yang elemennya bilangan bulat non negatif menyatakan secara tunggal suatu graf berarah dengan m simpul.
Contoh :
Teorema :
M adalah Matriks dari sutau graf berarah D, maka elemen baris ke i kolom ke j dari Matriks Mn menyatakan banyaknya walk dengan panjang n dari simpul vi ke simpul vj.
ALGORITMA JALUR TERPENDEK
Pandang D suatu Graf berarah yang hingga dengan tiap-tiap ruas mempunyai bobot. Jadi D merupakan suatu Network. Kita hendak menentukan Jalur Terpendek antara simpul u dan v. Misalkan D tidak mengandung sirkuit.
Sebagai contoh, gambar berikut merupakan suatu Network. Kita hendak menghitung Jalur terpendek dari simpul u ke v.
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 4
Simpul u disebut Sumber (Source).
Simpul v disebut Muara (Sink).
Untuk menentukan Jalur Terpendek tersebut, cara berikut dapat digunakan :
• Buat tabel jarak :
u
x
y
z
a
b
c
v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3
yb = 2
yc = 1
zy = 2
zc = 5
ab = 2
av = 3
bv = 3
cv = 3
• Kita mulai dengan simpul u sebagai simpul awal. Beri harga = 0. Ambil simpul dengan jarak terdekat dari u (dalam hal ini z = 2), kemudian lingkari uz. Semua ruas lain yang berakhir di z kita hapus (dalam hal ini tidak ada ruas lain yang berakhir di z. Beri nilai = 2 di belakang z. Simpul yang telah diberi harga ditandai dengan *.
u*(0)
x
y
z*(2)
a
b
c
v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3
yb = 2
yc = 1
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv = 3
cv = 3
• Dari simpul u dan z (yang telah ditandai *), dicari simpul lain yang jarknya terdekat dihitung dari u. Jadi harus diperhitungkan nilai yang tertulis di simpul (0 untuk u dan 2 untuk z). Disini ux = 4 dan uzy = 2 + 2 = 4 merupakan nilai minimal. Boleh dipilih salah satu, misalnya uzy. Beri nilai = 4 pada y. Lingkari zy dan hapus ruas yang lain yang menuju y, yaitu uy dan xy.
u*(0)
x
y
z*(2)
a
b
c
v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3
yb = 2
yc = 1
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv = 3
cv = 3
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 5
• Demikian proses dilanjutkan berturut-turut :
u*(0)
x
y*(4)
z*(2)
a
b
c
v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3
yb = 2(6)
yc = 1(5)
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv = 3
cv = 3
u*(0)
x*(4)
y*(4)
z*(2)
a
b
c
v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3(7)
yb = 2(6)
yc = 1(5)
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv = 3
cv = 3
u*(0)
x*(4)
y*(4)
z*(2)
a
b
c*(5)
v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3(7)
yb = 2(6)
yc = 1(5)
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv = 3
cv = 3(8)
u*(0)
x*(4)
y*(4)
z*(2)
a
b*(6)
c*(5)
v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3(7)
yb = 2(6)
yc = 1(5)
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv = 3(9)
cv = 3(8)
u*(0)
x*(4)
y*(4)
z*(2)
a*(7)
b*(6)
c*(5)
v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3(7)
yb = 2(6)
yc = 1(5)
zy = 2(4)
zc = 5(7)
ab = 2
av = 3(10)
bv = 3(9)
cv = 3(8)
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 6
u*(0)
x*(4)
y*(4)
z*(2)
a*(7)
b*(6)
c*(5)
v*(8)
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3(7)
yb = 2(6)
yc = 1(5)
zy = 2(4)
zc = 5(7)
ab = 2
av = 3(10)
bv = 3(9)
cv = 3(8)
• Diperoleh jalur minimal dari simpul u ke simpul v yang panjangnya = 8 dengan urutan
v ← c ← y ← z ← u
Algoritma diatas dapat pula dikenakan untuk Graf tidak berarah.
PROBLEMA ALIRAN MAKSIMAL
Tujuan dari Problema Aliran Maksimal adalah :
Mengatur jadwal pengiriman barang agar jumlah barang yang dikirimkan dari suatu simpul ke simpul lain (yang tertentu) adalah maksimum.
Simpul yang mengirimkan (simpul awal) disebut Sumber (Source).
Simpul yang menerima kiriman (simpul akhir) disebut Muara (Sink).
Antara Sumber dan Muara terdapat pula simpul lain yang disebut Simpul Perantara.
Dalam hal ini ditetapkan bahwa simpul perantara tidak dapat menyimpan barang.
Perharikan Graf diatas. Simpul a adalah Sumber. Simpul d adalah Muara. Sedangkan simpul b dan c adalah Simpul Perantara. Angka pada masing-masing ruas menyatakan kapasitas ruas tersebut.
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 7
Jadi, misalkan dari a dapat dikirimkan 10 buah/unit barang ke b, sedangkan dari b tidak dapat dikirimkan barang ke a.
Untuk menyelesaikan problema aliran maksimal diatas, dapat kita gunakan suatu algoritma.
Algoritma Problema Aliran Maksimal adalah sebagai berikut :
1) Cari suatu jalur dari Sumber ke Muara yang dapat membawa aliran barang yang positif.
Kalau tak ada, langsung ke langkah (4). Tentukan aliran maksimal jalur tersebut.
Contoh : Pada problema diatas dapat diambil jalur ad.
Aliran maksimum jalur tersebut adalah 8.
2) Pada graf berikutnya kapasitas ruas pada jalur kita kurangi dengan aliran maksimum, dan kapasitas ruas yang berlawanan bertambah dengan aliran maksimum tersebut.
Contoh : Pada contoh kita, kapasitas ruas ad menjadi 8 – 8 = 0
Dan kapasitas ruas da menjadi 0 + 8 = 8
3) Kembali ke langkah (1).
4) Aliran Maksimum adalah jumlah semua barang yang diterima oleh Muara.
Berikut ini adalah penyelesaian problema di atas :
Jalur ad, aliran maksimal = 8
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 8
Jalur acbd, aliran maksimal = 4
Jalur abcd, aliran maksimal = 9
Jalur acd, aliran maksimal = 1
Tak ada lagi Jalur dari Sumber ke Muara yang dapat membawa aliran positif. Jadi diperoleh aliran maksimal dari jaringan adalah 22.
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 9
MESIN STATE HINGGA
Mesin State Hingga merupakan suatu struktur abstrak yang didefinisikan terdiri atas :
(1) Himpunan hingga A, berisi simbol input
(2) Himpunan hingga S, berisi internal state
(3) Himpunan hingga Z, berisi simbol output
(4) Sebuah fungsi f : S x A → S, disebut fungsi next-state
(5) Seubuah fungsi g : S x A → Z disebut fungsi output
⇒ M ( A, S, Z, f, g)
INPUT : Untai
OUTPUT : Untai
⇒ M (A, S, Z, q0, f, g)
Contoh : M ( A, S, Z, f, g) dengan :
(1) A = (a,b)
(2) S = (q0, q1, q2)
(3) Z = ( x, y, z)
(4) f : S x A → S, yang didefinisikan sebagai :
f (qo, a) = q1 f (q0, b) = q2
f (q1, a) = q2 f (q1, b) = q1
f (q2, a) = qo f (q2, b) = q1
(5) g : S x A → Z, yang didefinisikan sebagai :
g (q0, a) = x g (q0, b) = y
g (q1, a) = x g (q1, b) = z
g (q2, a) = z g (q2, b) = y
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 10
AUTOMATA HINGGA
Automata Hingga merupakan suatu struktur abstrak yang didefinisikan terdiri atas :
(1) Himpunan hingga A, berisi simbul input
(2) Himpunan hingga S, berisi internal state
(3) Himpunan T (dimana T ⊂ S), elemennya disebut state penerima
(4) State awal (biasanya q0), anggota S
(5) Fungsi next-state f : S x A → S
⇒ M (A, S, T, qo, f)
INPUT : Untai
OUTPUT : Diterima atau ditolak
Contoh : M (A, S, T, qo, f) dengan :
(1) A = { a, b }
(2) S = { q0, q1, q2 }
(3) T = { qo, q1 }
(4) State awal = q0
(5) Fungsi next-state f : S x A → S, yang didefinisikan sebagai tabel berikut :
f
a
b
q0
q1
q2
q0
q0
q2
q1
q2
q2
Graf Berarah ( Digraf)
Logika dan Algoritma – Yuni Dwi Astuti, ST 11
LATIHAN
1. Tentukan jalur terpendek dari G ke H!
2. Selesaikanlah problema aliran maksimal dari graph berikut. Simpul x merupakan sumber dan y merupakan muara!

ga tau ah.........

Pohon (Tree)
POHON (TREE)
Pohon (Tree) didefinisikan sebagai graph terhubung yang tidak mengandung sirkuit. Sedangkan Hutan (Forest) adalah graph yang tidak mengandung sirkuit. Jadi pohon adalah hutan yang terhubung.
Untuk itu perlu diingat kembali bahwa :
• Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari graf G selalu terdapat jalur yang menghubungkan kedua simpul tersebut.
• Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap simpul dua.
Contoh :
Sifat :
Suatu Graf G adalah Pohon jika dan hanya jika terdapat satu dan hanya satu jalur diantara setiap pasang simpul dari Graf G.
Pohon (Tree)
Teorema :
Suatu Graf G dengan n buah simpul adalah Pohon jika :
(1) G terhubung dan tak mengandung sirkuit, atau
(2) G tidak mengandung sirkuit dan mempunyai n - 1 buah ruas, atau
(3) G mempunyai n - 1 buah ruas dan terhubung
Teorema :
Pohon (dan hutan) adalah berwarna 2.
POHON RENTANGAN (SPANNING TREE)
Suatu pohon rentangan atau spanning tree adalah suatu subgraf dari graf G yang mengandung semua simpul dari G dan merupakan suatu pohon.
GRAF G
SPANNING TREE
n simpul
n simpul
m ruas
n – 1 ruas
Contoh :
Keterangan
Branch
Chord
Chord
m - (n - 1)
Cabang (Branch)
Logika dan Algoritma – Yuni Dwi Astuti, ST 2
Pohon (Tree)
Contoh :
Graf G
Spanning tree dari graf G
POHON RENTANGAN MINIMAL (MINIMAL SPANNING TREE)
Apabila G suatu Graf berbobot (Suatu Network), maka pohon rentangan minimal dari graf adalah pohon rentangan dengan jumlah bobot terkecil.
Logika dan Algoritma – Yuni Dwi Astuti, ST 3
Pohon (Tree)
Untuk mendapatkan pohon rentangan minimal dapat digunakan Algoritma berikut :
SOLIN
1. Urutkan ruas dari G menurut bobotnya, dari besar ke kecil.
2. Lakukan penghapusan ruas berdasarkan urutan yang sudah dilakukan, dengan ketentuan bahwa penghapusan ruas tersebut tidak menyebabkan graf menjadi tidak terhubung.
KRUSKAL
1. Urutkan ruas dari G menurut bobotnya, dari kecil ke besar.
2. Lakukan penambahan ruas berdasarkan urutan yang sudah dilakukan, dengan ketentuan bahwa penambahan ruas tersebut tidak menyebabkan adanya sirkuit.
PRIM’S
= Kruskal + menjaga graf tetap terhubung
Contoh :
Total bobot = 4 + 3 + 2 + 5 + 2 + 4 + 2 + 2 + 3 = 27
Logika dan Algoritma – Yuni Dwi Astuti, ST 4
Pohon (Tree)
POHON BERAKAR (ROOTED TREE)
Suatu pohon berakar R adalah suatu pohon bersama dengan suatu simpul r yang dirancang/ditunjuk sebagai akar (root) dari R.
• Seperti diketahui bahwa hanya terdapat satu jalur antara r dengan simpul lain v pada pohon pohon tersebut.
• Panjang jalur antara r dengan simpul v disebut level atau kedalaman simpul v.
• Simpul bukan akar, yang berderajat satu disebut daun. Jalur antara suatu simpul dengan suatu daun disebut cabang (branch).
Contoh :
• Simpul u dikatakan mendahului simpul v jika jalur dari akar r ke v melalui u.
• Dikatakan u mendahului langsung v bila u mendahului v serta simpul u dan v berdampingan.
• Pada contoh di atas, a mendahului d, mendahului e, dan mendahului h.
Suatu pohon berakar dapat digunakan untuk menelusuri semua kemungkinan dari kejadian, dengan masing-masing kejadian dapat muncul dalam sejumlah hingga cara.
Bebarapa contoh lain yang penting dari pohon berakar adalah pohon binar (binary tree) dan pohon sintaks (syntax tree) atau pohon derivasi (derivation tree).
Logika dan Algoritma – Yuni Dwi Astuti, ST 5
Pohon (Tree)
POHON BINAR (BINARY TREE)
Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur ini biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan hierarkykal antara elemen-elemen mereka.
Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah pohon binary. Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar T didefinisikan terdiri dari sebuah himpunan hingga elemen yang disebut simpul, sedemikian sehingga :
a. T adalah hampa (disebut pohon null) atau
b. T mengandung simpul R yang dipilih disebut akar (root) dari T, dan simpul sisanya membentuk 2 pohon binary T1 dan T2 yang saling lepas.
Setiap simpul didalam pohon binar hanya dapat mempunyai 0, 1 atau 2 successor (turunan langsung).
Untuk menyajikan pohon binar, simpul akar adalah simpul yang digambar pada bagian paling atas. Sedangkan suksesor kiri (left successor) digambarkan sebagai garis ke kiri bawah dan suksesor kanan (right successor) sebagai garis ke kanan bawah.
Contoh : Logika dan Algoritma – Yuni Dwi Astuti, ST 6
Pohon (Tree)
�� B adalah left successor dan C adalah right successor dari simpul A
�� Left subtree dari root A terdiri dari simpul B, D, E, F
�� Right subtree dari root A terdiri dari simpul C, G, H, J, K, L
�� F adalah left successor dari simpul E
�� L adalah right successor dari simpul J
�� Kedalaman atau ketinggian (depth/height) dari pohon binar T adalah banyak maksimum simpul dari cabang di T. Untuk pohon binar di atas, ketinggiannya adalah 5.
Pohon biner T dan T′ disebut similar jika strukturnya (bentuknya) sama.
Pohon biner T dan T′ disebut salinan (copy) jika strukturnya (bentuknya) sama dan nama simpulnya sama.
Contoh :
Gambar semua kemungkinan pohon biner yang non-similar dengan 3 simpul
POHON BINAR LENGKAP
Suatu pohon binar T dikatakan lengkap bila setiap tingkatnya, kecuali mungkin tingkat yang terakhir, mempunyai semua simpul yang mungkin, yaitu 2r simpul untuk tingkat ke-r, dan bila semua simpul pada tingkat terakhir muncul di bagian kiri pohon.
Kedalaman atau ketinggian pohon binar lengkap T dengan n simpul : INT(2log n) + 1
Logika dan Algoritma – Yuni Dwi Astuti, ST 7
Pohon (Tree)
Contoh :
POHON - 2
Pohon binar T dikatakan pohon-2 atau pohon binar yang diperluas (extended binary tree) bila setiap simpul mempunyai 0 atau 2 anak.
• Simpul dengan 2 anak disebut simpul internal, digambarkan sebagai lingkaran. Biasanya berfungsi sebagai operator.
• Simpul dengan 0 anak disebut simpul eksternal, digambarkan sebagai segi-empat. Biasanya berfungsi sebagai operand.
Contoh : Pohon-2 yang menyajikan ekspresi (a-b)/((c+d)*e) Logika dan Algoritma – Yuni Dwi Astuti, ST 8
Pohon (Tree)
POHON SINTAKS (SYNTAX TREE)
Untuk menjelaskan mengenai bahasa secara teoritis dan formal, kita lihat terlebih dahulu sebuah kalimat sehari-hari dalam bahasa Indonesia, yaitu :
Si kucing kecil menendang bola besar
Gambar penguraian kalimat di atas membentuk struktur pohon, yang disebut pohon sintaks dari kalimat. Disini kalimat dibagi-bagi berdasar jenis dan fungsi kata. Dari pelajaran bahasa Indonesia kita tahu bahwa kalimat di atas telah benar susunannya, atau telah benar tata bahasanya.
Pohon sintaks dari kalimat di atas dapat dilihat sebagai berikut :
Derivasi adalah proses pembentukan untai terminal dengan melakukan sederetan produksi menggunakan himpinan produksi yang ada.
Himpunan produksi dari pohon sintaks diatas adalah :
1.
2.
3.
4.
Logika dan Algoritma – Yuni Dwi Astuti, ST 9
Pohon (Tree)
5. → si
6. → kucing | bola
7. → kecil |besar
8. → menendang
Soal Latihan :
Lakukan derivasi terhadap untai terminal x1x2x3 dengan himpunan produksi sebagai berikut :
1. |
2.
3. → x | y | z
4. <> | | ^
5. → 0|1|2|3|4|5|6|7|8|9
6. |
7. → - |+
8. | ^
Logika dan Algoritma – Yuni Dwi Astuti, ST 10

kuliahan

LOGIKA DAN ALGORITMA
DASAR – DASAR TEORI GRAF
• Kelahiran Teori Graf
Sejarah Graf : masalah jembatan Königsberg (tahun 1736)
CABD
Gbr 1. Masalah Jembatan Königsberg
Graf yang merepresentasikan jembatan Königsberg :
Simpul (vertex) �� menyatakan daratan
Ruas (edge) �� menyatakan jembatan
Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?
• Perjalanan Euler adalah :
Perjalanan dari suatu simpul kembali ke simpul tersebut dengan melalui setiap ruas tepat satu kali.
• Perjalanan Euler akan terjadi, jika :
- Graf terhubung.
- Banyaknya ruas yang datang pada setiap simpul adalah genap.
Dasar Teori Graf
• Definisi Graf
Graf G (V, E), adalah koleksi atau pasangan dua himpunan
(1) Himpunan V yang elemennya disebut simpul atau titik, atau vertex, atau point, atau node.
(2) Himpunan E yang merupakan pasangan tak terurut dari simpul, disebut ruas atau rusuk, atau sisi, atau edge, atau line.
• Banyaknya simpul (anggota V) disebut order Graf G, sedangkan banyaknya ruas (anggota E) disebut ukuran (size) Graf G
G1 G2 G3 111234234243e1e2e3e4e5e6e7e1e2e3e4e5e6e7e8
Gbr 2. (G1) graf sederhana, (G2) multigraf, dan (G3) multigraf
Pada Gbr 2, G1 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }
G2 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }
= { e1, e2, e3, e4, e5, e6, e7}
Logika dan Algoritma – Yuni Dwi Astuti, ST 2
Dasar Teori Graf
G3 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7, e8}
• Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan ruas berganda atau ruas sejajar (multiple edges atau paralel edges), karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.
• Pada G3, sisi e8 = (3, 3) dinamakan gelung atau self-loop karena ia berawal dan berakhir pada simpul yang sama.
JENIS – JENIS GRAF
• Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graf).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana.
2. Graf tak-sederhana (unsimple-graf/multigraf).
Graf yang mengandung ruas ganda atau gelung dinamakan graf tak-sederhana (unsimple graf atau multigrapf).
• Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graf)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
Logika dan Algoritma – Yuni Dwi Astuti, ST 3
Dasar Teori Graf
2. Graf tak-berhingga (unlimited graf)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.
• Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graf)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.
2. Graf berarah (directed graf atau digraf)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. (a) G
Dua buah graf pada Gbr 3 adalah graf berarah.
Gbr 3 (a) graf berarah, (b) graf-ganda berarah
ERMINOLOGI GRAF
4 (b) G5 11234234
T
en Subgraf
raf. G1 = (V1, E1) adalah subgraf (subgraf) dari G
• Subgraf dan Komplem
Misalkan G = (V, E) adalah sebuah g
jika V1 ⊆ V dan E1 ⊆ E. Logika dan Algoritma – Yuni Dwi Astuti, ST 4
Dasar Teori Graf
Komplemen dari subgraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.
123456165312352
(a) Graf G1
(b) Subgraf
(c) Komplemen Subgraf (b)
• Subgraf yang Direntang (Spanning Subgraf)
Apabila E‘ mengandung semua ruas di E yang kedua ujungnya di V‘ , maka
G‘ adalah Subgraf yang dibentuk oleh V‘ (Spanning Subgraph)
Contoh :
• Derajat (Degree)
Derajat suatu simpul d(v) adalah banyaknya ruas yang menghubungkan suatu simpul.
Sedangkan Derajat Graf G adalah jumlah derajat semua simpul Graf G.
Logika dan Algoritma – Yuni Dwi Astuti, ST 5
Dasar Teori Graf
13241234512e1e2e3e4e53
Graf G1 Graf G2 Graf G3
graf G1 : d(1) = d(4) = 2
d(2) = d(3) = 3
graf G3 : d(5) = 0 �� simpul terpencil / simpul terisolasi
d(4) = 1 �� simpul bergantung / simpul akhir
graf G2 : d(1) = 3 �� bersisian dengan ruas ganda
d(3) = 4 �� bersisian dengan self-loop (derajat sebuah self-loop = 2)
Jumlah derajat semua simpul Graf (derajat Graf) = dua kali banyaknya ruas Graf (size/ukuran Graf).
• Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3,
simpul 1 tidak bertetangga dengan simpul 4.
• Bersisian (Incidency)
Untuk sembarang ruas e = (vj, vk) dikatakan :
e bersisian dengan simpul vj , atau
e bersisian dengan simpul vk
Logika dan Algoritma – Yuni Dwi Astuti, ST 6
Dasar Teori Graf
graf G1: ruas (2, 3) bersisian dengan simpul 2 dan simpul 3,
ruas (2, 4) bersisian dengan simpul 2 dan simpul 4,
tetapi ruas (1, 2) tidak bersisian dengan simpul 4.
• Simpul Terpencil (Isolated Vertex)
Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.
graf G3: simpul 5 adalah simpul terpencil.
• Graf Kosong (null graf atau empty graf)
Graf yang himpunan sisinya merupakan himpunan kosong (Nn).
Graf N5 :
12345
OPERASI GRAF
G1 = (E1,V1) , G2 = (E2,V2)
1. Gabungan G1 ∪ G2 adalah graf dgn himpunan ruasnya E1 ∪ E2.
2. Irisan G1 ∩ G2 adalah graf dgn himpunan ruasnya E1 ∩ E2.
3. Selisih G1 - G2 adalah graf dgn himpunan ruasnya E1 - E2.
4. Selisih G2 – G1 adalah graf dgn himpunan ruasnya E2 - E1.
5. Penjumlahan ring G1 ⊕ G2 adalah graf dgn himpunan ruasnya (E1 ∪ E2) - (E1 ∩ E2) atau (E1 - E2) ∪ (E2 - E1).
Logika dan Algoritma – Yuni Dwi Astuti, ST 7
Dasar Teori Graf
Contoh :
Graf G1 Graf G2
G1 ∪ G2 G1 ∩ G2
G1 - G2 G2 – G1
G1 ⊕ G2
Logika dan Algoritma – Yuni Dwi Astuti, ST 8
Dasar Teori Graf
DEKOMPOSISI
Suatu graf G dikatakan dikomposisikan menjadi K dan L bila G = K ∪ L dan K ∩ L = ∅
Contoh :
PENGHAPUSAN (DELETION)
Penghapusan dapat dilakukan pada simpul ataupun ruas.
1) Penghapusan Simpul .
Notasinya : G – {V}
Contoh :
2) Penghapusan Ruas .
Notasinya : G – {e}
Contoh :
e1
e5
e5
e4
e4
e3
e2
e2
e1
Logika dan Algoritma – Yuni Dwi Astuti, ST 9
Dasar Teori Graf
PEMENDEKKAN (SHORTING)
Pemendekan/Shorting adalah menghapus simpul yang dihubungkan oleh 2 ruas (simpul berderajat 2), lalu menghubungkan titik-titik ujung yang lain dari kedua ruas tersebut.
Contoh :
KETERHUBUNGAN
• Perjalanan (Walk)
Perjalanan atau walk pada suatu Graf G adalah barisan simpul dan ruas berganti-ganti
v1, e1, v2, e2, …,en-1, vn �� ruas ei menghubungkan vi dan vi+1
dapat hanya ditulis barisan ruas atau barisan simpul saja.
e1, e2, …,en-1 atau v1, v2, …, vn-1, vn
Dalam hal ini, v1 disebut simpul awal, dan vn disebut simpul akhir.
Perjalanan disebut perjalanan tertutup bila v1 = vn, sedangkan Perjalanan disebut perjalanan tebuka yang menghubungkan v1 dan vn. Panjang Perjalanan adalah banyaknya ruas dalam barisan tersebut.
• Lintasan (Trail)
Lintasan adalah Walk dengan semua ruas dalam barisan adalah berbeda.
• Jalur (Path)
Jalur adalah Walk yang semua simpul dalam barisan adalah berbeda.
• Sirkuit (Cycle)
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus. Panjang sirkuit adalah jumlah ruas dalam sirkuit tersebut.
Logika dan Algoritma – Yuni Dwi Astuti, ST 10
Dasar Teori Graf
Graf yang tidak mengandung sirkuit disebut acyclic.
Contoh :
Suatu graf G disebut terhubung jika untuk setiap simpul dari graf terdapat jalur yang menghubungkan kedua simpul tersebut.
Subgraf terhubung suatu graf disebut komponen dari G bila subgraf tersebut tidak terkandung dalam subgraf terhubung lain yang lebih besar.
Contoh :
Rank (G) = n – K
Nullity (G) = e – (n – k)
Dimana : n : Order graf G
e : Size graf G
K : banyaknya komponen graf G
Jarak antara 2 simpul dalam graf G adalah panjang jalur terpendek antara ke 2 simpul tersebut.
Diameter suatu graf terhubung G adalah maksimum jarak antara simpul G. Logika dan Algoritma – Yuni Dwi Astuti, ST 11
Dasar Teori Graf
Jarak maksimum dalam graf G adalah 3 (yaitu antara A – G atau B - G ataupun C - G), jadi diameter = 3
GRAF BERLABEL
Graf berlabel/ berbobot adalah graf yang setiap ruasnya mempunyai nilai/bobot berupa bilangan non negatif.
Contoh :
ISOMORFISMA
Dua buah graf atau lebih yang mempunyai jumlah ruas, simpul, dan derajat yang sama.
Contoh :
HOMOMORFISMA
Dua buah graf aau lebih yang penggambarannya sama, tetapi jumlah ruas dan simpulnya berbeda.
Logika dan Algoritma – Yuni Dwi Astuti, ST 12
Dasar Teori Graf
Contoh :
BEBERAPA GRAF SEDERHANA KHUSUS
a. Graf Lengkap (Complete Graph)
Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpul dilambangkan dengan Kn. Jumlah sisi pada graf lengkap yang terdiri dari n buah simpul adalah n(n – 1)/2.
b. Graf Lingkaran
Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan Cn.
Logika dan Algoritma – Yuni Dwi Astuti, ST 13
Dasar Teori Graf
c. Graf Teratur (Regular Graphs)
Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur adalah nr/2.
d. Graf Bipartisi (Bipartite Graph)
Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartisi dan dinyatakan sebagai G(V1, V2). Dilambangkan KMN.
e. Graf Platonik
Graf yang berasal dari penggambaran bangun ruang, dimana titik sudut merupakan simpul, dan rusuk meruakan ruas.
Logika dan Algoritma – Yuni Dwi Astuti, ST 14

BELAJAR ALGORITMA

Algoritma berisi langkah-langkah penyelesaian masalah. Langkah-langkah tersebut dapat
ditulis dalam notasi apapun, asalkan mudah dibaca dan dimengerti, karena memang tidak
ada notasi baku dalam penulisan algoritma. Tiap orang dapat membuat aturan penulisan
dan notasi algoritma sendiri. Agar notasi algoritma mudah ditranslasi ke dalam notasi
bahasa pemrograman, maka sebaiknya notasi algoritma tersebut berkorespnden dengan
notasi bahasa pemrograman secara umum.
Aturan Penulisan Algoritma
Setiap Algoritma akan selalu terdiri dari tiga bagian yaitu :
• Judul (Header)
• Kamus
• Algoritma
Pada setiap bagian tersebut apabila akan dituliskan komentar mengenai setiap bagian
tersebut dituliskan diantara tanda kurung kurawa contoh { Komentar }. Notasi algoritmis
yang dituliskan diantara tanda ini tidak akan dieksekusi oleh program.

Tidak ada komentar:

Poskan Komentar