Download - Graf tak berarah

Transcript
Page 1: Graf tak berarah

GRAF TAK BERARAH

Teori Graf – Matematika Diskrit

Page 2: Graf tak berarah

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.

Page 3: Graf tak berarah

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.

Page 4: Graf tak berarah

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.

Page 5: Graf tak berarah

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)

Page 6: Graf tak berarah

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)

Page 7: Graf tak berarah

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.

Page 8: Graf tak berarah

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}.

Page 9: Graf tak berarah

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.

Page 10: Graf tak berarah

Graf Tak Berarah (Undirected Graph)

Page 11: Graf tak berarah

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

.

Page 12: Graf tak berarah

Graf Tak Berarah (Undirected Graph)

Contoh soal:

Gambarlah K2, K3, K4, K5, K6 !

Page 13: Graf tak berarah

Graf Tak Berarah (Undirected Graph)

Penyelesaian :

K2

n = 2

Jadi banyak garisnya adalah 1, dan gambarnya

adalah :

K2

Page 14: Graf tak berarah

Graf Tak Berarah (Undirected Graph)

Penyelesaian :

K3

K4

Page 15: Graf tak berarah

Graf Tak Berarah (Undirected Graph)

Penyelesaian :

K5

K6

Page 16: Graf tak berarah

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 .

Page 17: Graf tak berarah

Komplemen Graf

Contoh Soal :

Gambarlah Komplemen graf G yang di

definisikan dalam Gambar di bawah ini !

Page 18: Graf tak berarah

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}

Page 19: Graf tak berarah

Komplemen Graf

Penyelesaian :

Jadi graf dapat digambarkan sebagai

berikut :

Page 20: Graf tak berarah

Komplemen Graf

Silakan gambar graf untuk gambar (b) dan

(c) !

Page 21: Graf tak berarah

Komplemen Graf

Soal Latihan :

Misalkan G adalah suatu graf dengan n buah

titik dan k buah garis. Berapa banyak garis

dalam ?

Page 22: Graf tak berarah

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.

Page 23: Graf tak berarah

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.

Page 24: Graf tak berarah

Sub-Graf

Perhatikan gambar di bawah ini, apakah H merupakan

subgraf G ??

a.

Page 25: Graf tak berarah

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.

Page 26: Graf tak berarah

Sub-Graf

Perhatikan Gambar – gambar di bawah berikut ini :

a.

Apakah H merupakan SubGraf dari G?

Page 27: Graf tak berarah

Sub-Graf

Perhatikan Gambar – gambar di bawah berikut ini :

b.

Apakah H merupakan SubGraf dari G?

Page 28: Graf tak berarah

Sub-Graf

Perhatikan Gambar – gambar di bawah berikut ini :

c.

Apakah H merupakan SubGraf dari G?

Page 29: Graf tak berarah

Sub-Graf

Perhatikan Gambar di bawah ini, gambarlah subgraf yang

mungkin d bentuk dari graf tersebut.


Top Related