TEORI GRAF V

Derajat (Degree)
Derajatsuatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi: d(v)
Tinjau graph G1:
d(1) = d(4) = 2
d(2) = d(3) = 3

Derajat (Degree)
Tinjau graph G3:
d(5) = 0 = simpul terpencil
d(4) = 1 = simpul anting-anting (pendant vertex)
Tinjau graph G2:
d(1) = 3 = bersisian dengan sisi ganda
d(2) = 4 = bersisian dengan sisi gelang (loop)





Derajat (Degree)
Pada graph berarah,
d in(v) = derajat-masuk (in-degree) = jumlah busur yang masuk ke simpul v
d out(v) = derajat-keluar (out-degree) = jumlah busur yang keluar dari simpul v
d(v) = d in(v) + d out(v)

Derajat (Degree)
Tinjau graph :
d in(1) = 2; d out(1) = 1
d in(2) = 2; d out(2) = 3
d in(3) = 2; d out(3) = 1
d in(4) = 1; d out(4) = 2





Lemma Jabat Tangan
Jumlah derajat semua simpul pada suatu graph adalah genap, yaitu dua kali jumlah sisi pada graph tersebut.
Dengan kata lain, jika G= (V, E), maka

Lemma Jabat Tangan
Tinjau graph G1:
d(1) + d(2) + d(3) + d(4) =
2 + 3 + 3 + 2 = 10 =
2 jumlah sisi = 2 x 5
Tinjau graph G2:
d(1) +d(2) + d(3)
= 3 + 3 + 4 = 10
= 2 jumlah sisi = 2 x 5




Lemma Jabat Tangan
Tinjau graph G3:
d(1) + d(2) + d(3) + d(4) + d(5)
= 2 + 2 + 3 + 1 + 0
= 8
= 2 jumlah sisi
= 2 x 4

Lemma Jabat Tangan
Contoh.
Diketahui graph dengan lima buah simpul. Dapatkah kita menggambar graph tersebut jika derajat masing-masing simpul adalah:
(a) 2, 3, 1, 1, 2
(b) 2, 3, 3, 4, 4
Penyelesaian:
(a) tidak dapat, karena jumlah derajat semua simpulnya
ganjil
(2 + 3 + 1 + 1 + 2 = 9).
(b) dapat, karena jumlah derajat semua simpulnya
genap
(2 + 3 + 3 + 4 + 4 = 16).

TEORI GRAF IV

Contoh Terapan Graph

Contoh Terapan Graph

• Transaksi konkuren pada basis data terpusat

• Transaksi T0menunggu transaksi T1dan T2

• Transaksi T2menunggu transaksi T1

• Transaksi T1menunggu transaksi T3

• Transaksi T3menunggu transaksi T2

Contoh Terapan Graph
. Pengujian program
read(x);
whilex <> 9999 do
begin
ifx < 0 then
writeln(‘Masukan tidak boleh negatif’)
else
x:=x+10;
read(x);
end;
writeln(x);


Contoh Terapan Graph

Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau graph :
simpul 1 bertetangga dengan simpul 2 dan 3, simpul 1 tidak bertetangga dengan simpul 4.

Bersisian (Incidency)
Untuk sembarang sisi e= (vj, vk) dikatakan e bersisian dengan simpul vj, atau e bersisian dengan simpul vk
Tinjau graph :
sisi (2, 3) bersisian dengan simpul 2 dan simpul 3,
sisi (2, 4) bersisian dengan simpul 2 dan simpul 4,
tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

Simpul Terpencil (Isolated Vertex)
Simpul terpencilialah simpul yang tidak mempunyai sisi yang bersisian dengannya.
Tinjau graph : simpul 5 adalah simpul terpencil

Graph Kosong (null graphatau empty graph)
Graph yang himpunan sisinya merupakan himpunan kosong (Nn).

TEORI GRAF III

Jenis-Jenis Graph
Berdasarkan jumlah simpul pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis:
1. Graph berhingga(limited graph)
2. Graph tak-berhingga(unlimited graph)

Graph berhingga(limited graph)
Graph berhingga adalah graph yang jumlah simpulnya, n, berhingga.

Graph tak-berhingga(unlimited graph)
Graph yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graph tak-berhingga.

Berdasarkan orientasi arah pada sisi, maka secara umum graph dibedakan atas 2 jenis:
1. Graphtak-berarah(undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah. Tiga buah graph pada Gambar2 adalah graph tak-berarah.
2. Graph berarah(directed graphatau digraph)
Graph yang setiap sisinya diberikan orientasi arah disebut sebagai graph berarah. Dua buah graph pada Gambar 3 adalah graph berarah.

Graph tak-berarah(undirected graph)
Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak-berarah. Graph G1, G2, dan G3 adalah graph tak-berarah.

Graph berarah (directed graph atau digraph)
Graph yang setiap sisinya diberikan orientasi arah disebut sebagai graph berarah.

TEORI GRAF II

Jenis-Jenis Graph
Berdasarkan ada tidaknya gelang atau sisi
ganda pada suatu graph, maka graph
digolongkan menjadi dua jenis:
1. Graph sederhana (simple graph).
2. Graph tak-sederhana (unsimple-graph).

Graph sederhana (simple graph)
Graph yang tidak mengandung gelang
maupun sisi-ganda dinamakan graph
sederhana. G1 adalah contoh graph
sederhana

Graph tak-sederhana (unsimple-
graph)
Graph yang mengandung sisi ganda atau
gelang dinamakan graph tak-sederhana
(unsimple graph). G2 dan G3 adalah contoh
graph tak-sederhana

TEORI GRAF

Graph

• Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

• Gambar berikut ini sebuah graph yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.

 

 GraphSejarah 

• Graph: masalah jembatan KÖnigsberg (tahun 1736)

 

Graph yang merepresentasikan jembatan KÖnigsberg:
Simpul (vertex) : menyatakan daratan
Sisi (edge) : menyatakan jembatan

Bisakah melalui setiap jembatan tepat sekali dan kembali lagi ke tempat semula?

Definisi Graph
Graph G= (V, E), yang dalam hal ini:
V= himpunan tidak-kosong dari simpul-simpul
(vertices) = { v1 , v2 , ... , vn}
E= himpunan sisi (edges) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en}