GRAF TAK BERARAH

Teori Graf – Matematika Diskrit

Jenis – jenis Graf

Berdasarkan jenis garis – garisnya, graf

dibedakan dalam 2 kategori, yaitu :

1.Graf Tak Berarah (Undirected Graph)

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

2.Graf Berarah (Directed Graph = Digraph)

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.

Graf Tak Berarah (Undirected Graph)

Definisi 2

Graf Sederhana (Simple graf) adalah graf yang tidak

mengandung Loop maupun Garis Paralel. Graf di 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.

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.

Graf Tak Berarah (Undirected Graph)

2. Graf Semu (Pseudograph), adalah graf yang

mengandung Loop. Contoh geaf di bawah ini

disebut graf semu walaupun memiliki sisi ganda

sekalipun.

Graf Tak Berarah (Undirected Graph)

Graf Tak Berarah (Undirected Graph)

Contoh soal:

Gambarlah sebuah graf sederhana yang dapat

di bentuk dari 4 titik {a, b, c, d} dan 2 garis.

Graf Tak Berarah (Undirected Graph)

Penyelesaian :

Sebuah garis dalam graf sederhana selalu

berhubungan dengan 2 titik. Oleh karena ada 4

titik, maka ada C(4,2) = 6 garis yang mungkin

di buat. Yaitu garis – garis dengan titik ujung

{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}.

Graf Tak Berarah (Undirected Graph)

Penyelesaian :

Dari keenam garis yang mungkin tersebut,

selanjutnya dipilih 2 garis diantaranya. Jadi ada

C(6,2) = 15 buah graf yang mungkin di bentuk

dari 4 buah titik dan 2 buah garis.

Graf Tak Berarah (Undirected Graph)

Graf Tak Berarah (Undirected Graph)

Definisi 3

Graf Lengkap (Complete Graph) dengan n titik (simbol Kn)

adalah graf sederhana dengan n titik, di mana setiap 2 titik

berbeda dihubungkan dengan suatu garis.

Teorema 1

Banyaknya garis dalam suatu graf lengkap dengan n titik adalah

.

Graf Tak Berarah (Undirected Graph)

Contoh soal:

Gambarlah K2, K3, K4, K5, K6 !

Graf Tak Berarah (Undirected Graph)

Penyelesaian :

K2

n = 2

Jadi banyak garisnya adalah 1, dan gambarnya

adalah :

K2

Graf Tak Berarah (Undirected Graph)

Penyelesaian :

K3

K4

Graf Tak Berarah (Undirected Graph)

Penyelesaian :

K5

K6

Komplemen Graf

Definisi 3

Komplemen suatu graf G (Simbol ) dengan n titik adalah

suatu graf sederhana dengan :

1. Titik – titik sama dengan titik – titik G. Jadi, V ( ) = V(G)

2. Garis – garis adalah komplemen garis – garis G terhadap

graf lengkapnya (Kn).

Titik – titik yang dihubungkan dengan garis dalam G tidak

terhubung dalam . . Sebaliknya, titik – titik yang

terhubung dalam G menjadi tidak terhubung dalam .

Komplemen Graf

Contoh Soal :

Gambarlah Komplemen graf G yang di

definisikan dalam Gambar di bawah ini !

Komplemen Graf

Penyelesaian :

Titik – titik dalam sama dengan titik – titik

dalam G, sedangkan garis – garis dalam

adalah garis – garis yang tidak berada dalam

G. Pada gambar (a), titik – titik yang tidak

dihubungkan dengan garis dalam G adalah

garis dengan titik – titik ujung {a,d}, {a,e},

{b,c}, dan {b,e}

Komplemen Graf

Penyelesaian :

Jadi graf dapat digambarkan sebagai

berikut :

Komplemen Graf

Silakan gambar graf untuk gambar (b) dan

(c) !

Komplemen Graf

Soal Latihan :

Misalkan G adalah suatu graf dengan n buah

titik dan k buah garis. Berapa banyak garis

dalam ?

Sub-Graf

Definisi 4

Misalkan G adalah suatu graf. Graf H dikatakan sub-graf G

bila dan hanya bila :

a. V(H) V (G)

b. E(H) E (G)

c. Setiap garis dalam H memiliki titik ujung yang sama

dengan garis tersebut dalam G.

Sub-Graf

Dari definisi di atas, ada beberapa hal yang dapat diturunkan :

1. Sebuah titik dalam G merupakan Sub-Graf G.

2. Sebuah garis dalam G bersama- sama dengan titik – titik

ujungnya merupakan sub-graf G.

3. Setiap graf merupakan subgraf dari dirinya.

4. Dalam subgraf berlaku sifat transitif : Jika H adalah Subgraf G

dan G adalah Subgraf K, maka K adalah subgraf K.

Sub-Graf

Perhatikan gambar di bawah ini, apakah H merupakan

subgraf G ??

a.

Sub-Graf

Penyelesaian :

a. V (H) = {v2, v3} dan V (G) = {v1 , v2, v3} sehingga V(H)

V (G).

E(H) = {e4} dan E(G)= {e1,e2, e3, e4} sehingga E(H) E

(G). Garis e4 di H merupakan Loop pada v2 dan Garis e4

juga merupakan loop pada v2 di G. Dengan demikian, H

merupakan subgraf G.

Sub-Graf

Perhatikan Gambar – gambar di bawah berikut ini :

a.

Apakah H merupakan SubGraf dari G?

Sub-Graf

Perhatikan Gambar – gambar di bawah berikut ini :

b.

Apakah H merupakan SubGraf dari G?

Sub-Graf

Perhatikan Gambar – gambar di bawah berikut ini :

c.

Apakah H merupakan SubGraf dari G?

Sub-Graf

Perhatikan Gambar di bawah ini, gambarlah subgraf yang

mungkin d bentuk dari graf tersebut.