TEORI GARAPH (MATEMATIKA DISKRIT)

TEORI GARAPH (MATEMATIKA DISKRIT)
……………matematika perasaan


R E L A S I
Hubungan antara dua elemen himpunan

Definisi : Jika terdapat himpunan A dan himpunan B, maka relasi R dari A ke B adalah
Sub himpunan A X B
....atau :
RAB A X B

RELASI REFLEKSIF :
Setiap elemen A berhubungan dengan dirinya sendiri

a A ( a,a ) R atau a A a R a

Contoh : “ x selalu bersama y “ atau x = y

RELASI IREFLEKSIF :
Setiap elemen A tidak berhubungan dengan dirinya sendiri.

a A ( a,a ) R atau a A ( a R a )

Contoh : 1. “ x tidak bersama y “
2. ” x mampu mencukur rambut y dengan rapi sempurna ”
3. Dalam himpunan bilangan bulat,relasi kurang dari ( < ) dan relasi
lebih dari ( > )

RELASI SIMETRIK :
Relasi R dalam A , setiap pasangan anggota berhubungan satu sama lain.
Jika a terhubung b, maka b terhubung a ( hubungan timbal balik ).

a,b A ( a,b ) R ( b,a ) R
....... ATAU.........
a,b A a R b b R a

Contoh : relasi “ x + y genap “




RELASI ANTI SIMETRIK :
Jika setiap a dan b hanya terhubung salah satunya saja.

a,b A a b [ ( a,b ) R (b,a) R ]
................ATAU................
a,b A a b [ a R b ( bRa ) ]

Contoh : Relasi seperti 5 6 ( 6 5 )
RELASI TRANSITIF
Jika a berhubung b terhubung c maka a terhubung c
Contoh : 5 < 6 dan 6 < 7 maka 5 < 7
RELASI EKIVALEN
Bersifat : - Refleksif
- Simetrik
- Transitif
POSET atau Orde Parsial
Bersifat : - Refleksif
- Anti Simetrik
- Transitif
Definisi : (P, ) adalah sebuah poset, jika berlaku atau maka (P, ) disebut rantai.
Contoh : (P, )
P = {1,2,3,.............,100} dan x y jika dan hanya jika x.y 200
Apakah ini rantai?
Jawaban : (P, ) bukan rantai
Sebab : 90.90 | 200

DIAGRAM HASSE
Diagram Hasse yang dikenal dalam teori graf, merupakan himpunan dari :
Verteks (Node) digambarkan sebagai titik/ noktah atau lingkaran kecil .
Edge (arc) digambarkan sebagai simpul atau garis.
Contoh :

Ditulis : V = {1,2,3,6
E = {(1,2),(1,3),(2,6),(3,6)}




Contoh : dan
Tak ada anggota lain yang mengakibatkan
Maka : b

a
Contoh : x = {2,3,6,12,24,36}
relasi didefinisikan sebagai x y
jika x membagi y. (x membagi habis y).
dimana (x,y x)
Jawaban : v = {2,3,6,12,24,36}
E = {(2,6),(3,6),(6,12),(12,24),(12,36)}
Diagram Hasse :













Contoh : A Semua factor bilangan bulat positif m
Didefinisikan x y habis dibagi oleh x.
Buat diagram Hasse, Untuk :
a. m = 12
b. m = 45
Jawaban : a. A = {1,2,3,4,6,12}
V = {1,2,3,4,6,12}
E = {(1,2),(1,3),(2,4),(2,6),(3,6),(4,12),(6,12)}
Diagram Hasse :








b. A = {1,3,5,9,15,45}
V = {1,3,5,9,15,45}
E = {(1,3),(1,5),(3,9),(5,15),(9,45),(15,45)}
Diagram Hasse :





Contoh : A Sebuah himpunan hingga P(A) adalah himpunan kuasanya
Misalkan : merupakan relasi inklusi pada elemen – elemen dari P(A)
Gambar : diagram Hasse dari (P(A), ), jika :
1. A = {a}
2. B = {a,b}
3. C = {a,b,c}
Jawaban : 1. P(A) ={a} .Himpunan kuasanya {
V = {
E = {({a}, )}
Diagram Hasse :







2. V = { ,{a},{b},{a,b}}
E : {( ,{a}), ( ,{b}),({a},{a,b}), ({b},{a,b})}
Diagram Hasse :







3. V = { ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}
E = {( ,{a}),( ,{b}),( {c}),({a},{a,b}),({a},{a,c},({b},{a,b}),({b},{b,c}
({c},{a,c}), ({c},{b,c}), ({a,b},{a,b,c}), ({a,c},{a,b,c}),({b,c},{a,b,c})
Diagram Hasse :














Batas atas dan Batas Bawah

Batas atas yaitu agka – angka atau hal lain yang ada di atas himpunan diketahui
Batas bawah yaitu angka-angka atau hal lain yang ada dibawah himpunan diketahui



Batas bawah Batas atas


Supremium dan Infirium

Supremium yaitu angka-angka atau hal lain terkecil yang ada di atas himpunan diketahui
Infirium yaitu angka-angka atau hal lain terbesar yang ada di bawah himpunan diketahui





Infirium Supremium




Graf Trivial
Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisipun.
Jadi sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada minimal satu.
Dengan demikian dinyatakan V tidak bolh kosong, sedangkan E boleh kosong.
V, sebagai himpunan simpul
E, sebagai himpunan sisi.
Sisi ganda (Multiple edges atau paralel edges).
V = {1,2,3,4}
E = {(1,2),(2,3),(1,3),(2,4),(3,4),(3,4)}

Sisi (1,3) dan Sisi (3,4)
Dinamakan sisi ganda




Gelang, kalang atau loop.
V= {1,2,3,4}
E={(1,2),(2,3),(1,3),(1,3),(2,4),(3,4),(3,4),(3,3)}
E = {e1,e2,e3,e4,e5,e6,e7,e8}
e4
e1 e3 Sisi e8, dinamakan gelang/kalang/loop
e2 e8
e5 e6
e7


Jenis – Jenis Graf berdasarkan sisinya.
1. Graf sederhana (Simple Graph)
Tidak mengandung gelang (loop)maupun sisi ganda (multiple edges).
Contoh : (1) (2)





(4) (3)
Graf Complete atau graf lengkap, jika graf tersebut simpel dan setiap pasangan simpul yang berbeda dihubungkan oleh satu busur.
Graf Complete yang mempunyai n titik dinotasikan Kn.
Kn punya busur.
Bukti :
2. Graf tak sederhana (Unsimple Graph)
Mengandung sisi ganda atau gelang.
Terdiri 2 macam graph :
a. graph ganda (multigraph)
mengandung sisi ganda
b. graph semu (pseudograph)
Mengandung gelang
Jenis – jenis Graf berdasarkan jumlah simpul
1. Graf berhingga (limited graph)
Graf yang jumlah simpulnya n, berhingga
2. Graf tak terhingga (Unlimited graph)
Graf yang jumlah simpulnya n, tak terhingga
Jenis – jenis Graf berdasarkan arah sisi.
1. Graf tak berarah (Undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah
2. Graf berarah (directed- graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah
Terminologi / Istilah dasar.
1. Bertetangga (Adjacent)
Dua buah simpul terhubung langsung dengan sebuah sisi.

1 bertetangga dengan 2
3 tidak bertetangga dengan 1



2. Bersisian (Incient)
Sisi yang berhubungan langsung dengan simpul awal dan simpul akhir.

Sisi (2,3) bersisian dengan simpul 2 dan simpul 3
Sisi (1,2) tidak bersisian dengan simpul 4





3. Simpul terpencil (Isolated Vertex)
Simpul yang tidak mempunyai sisi yang bersisian dengannya atau simpul yang tidak sarupun bertetangga dengan simpul lainnya.

Simpul 5 adalah simpul terpencil





4. Graf kosong (Null graph atau Empty graph).
Graf yang himpunan sisinya merupakan himpunan kosong, ditulis sebagai Nn, dimana n = jumlah simpul.
Contoh : Graf N5








5. Derajat (Degree)
Jumlah sisi yang bersisian dengan Simpul

d(1) = d(4) = 2
d(2) = d(3) = 3




Simpul terpencil derajat 0
Sisi gelang atau loopderajat 2
Simpul yang berderajat 1 disebut anting – anting (pendant vertex)
6. Lintasan (Path)
Lintasan yang panjangnya n dari simpul awal ke simpul akhir.
Lintasan sederhana (siple path) adalah lintasan jika semua simpulnya berbeda (setiap sisi yang dilalui hanya satu kali)
Lintasan tertutup (Closed path) adalah lintasan yang berawal dan berakhir pada simpul yang sama.
Lintasan terbuka (open path) adalah lintasan yang tidak berawal dan berakhir pada simpul yang sama.
Contoh :







Lintasan 1,2,4,3 adalah lintasan sederhana juga lintasan terbuka
Lintasan 1,2,4,3,1 lintasan sederhana, juga lintasan tertutup.
Lintasan 1,2,4,3,2 bukan lintasan sederhana, tetapi lintasan terbuka.
7. Siklus (Cycle) atau Sirkuit (Circuit)
Lintasan yang berawal dan berakhir di simpul yang sama.
Panjang sirkuit adalah jumlah sisi didalam sirkuit terebut.
Sirkuit sederhana (Simple Circuit) jika setiap sisi yang dilaluinya berbeda.
Contoh :





Sirkuit 1,2,3,4 memiliki panjang 3
Sirkuit 1,2,,3,1 adalah sirkuit sederhana
Sirkuit 1,2,4,3,2,1 bukan sirkuit sederhana, karena sisi(1,2) dilalui dua kali.
8. Terhubung (Connected)
Dua buah simpul akan terhubung apabila terdapat lintasan antara keduanya.









Terhubung Tidak terhubung














Terhubung kuat Terhubung lemah
( Perhatikan garis 2 ke 1 )

9. Upagraf ( subgraf ) dan komplemen upagraf.
UPAGRAF :
Jika G = ( V , E ) dan G1 = ( V1 , E1 )

Maka : V1 V dan E 1 E


KOMPLEMEN DARI UPAGRAF :
Jika G = ( V , E ) ; G1 = ( V1 , E1 ) dan G2 = ( V2 , E2 )
M a k a : E2 = E - E1
C O N T O H :








G = (V,E) Upagraf, G1 = (V1,E1)














Komplemen dari Upagraf, G2 = (V2, E2)


10. Upagraf merentang (Spanning Subgraph)
Jika G1 = (V1, E1) dan G= (V,E)
Upagraf merentang jika V1 = V atau G1 mengandung semua simpul dari G
Contoh :
a. b. c.








b.Upagraf merentang dari a
c. Bukan upagraf merentang dari a

11. Cut – Set (jembatan/ bridge)
Himpunan yang apabila dibuang menjadi tidak terhubung.
Contoh :






=>






Sisi (2,4),(3,5),(4,6),(5,6) adalah Cut Set atau bridge.


12. Graf Berbobot (Weighted Graph)
Graf yang setiap sisinya diberi sebuah bobot.
Contohnya :


10 12
8


15 11
9



13. Graf Bipartite
Graf yang memiliki himpunan simpul yang dapat di partisi menjadi dua himpunan x dan y
Notasi : Km.n dimana dan
Contoh :


K 1.3 K 2.3 K 3.3 Graf tripartite

14. Colourable
Simpul – simpulnya dapat diwarnai dengan tidak ada dua simpul berdampingan diwarnai yang sama
Di tulis G.K- Colourable
Contoh :

G.2 Colourable






15. Eksentrisitas
Jarak (distance ) terjauh (maksimal lintasan terpendek)
Notasi : e (v)
Contoh : Eksentrisitas V1= e (V1) = 3 dengan titik eksentrik V4
e (V2) = 2 dengan titik eksentrik V4 dan V5
e (V3) = 2 dengan titik eksentrik V1 dan V6
e (V4) = 3 dengan titik eksentrik V1



14