.

.

.

.

.

.

u

zw

y

e1

e2

v

x

e3

e6

e5

e4

e7

KONSEP DASAR TEORI GRAPH

1. Definisi dan Terminologi

Sebuah graph G berisikan dua himpunan yaitu himpunan hingga tak kosong

V(G) yang elemen-elemennya disebut titik dan himpunan (mungkin kososng)

E(G) yang elemen-elemennya disebut sisi, sedemikian hingga setiap elemen e

dalam E(G) adalah sebuah pasangan tak berurutan dari titik-titik V(G). V(G)

disebut himpunan titik dari G dan E(G) disebut himpunan sisi dari G.

Misal u dan v adalah titik-titik G dan sisi e = {u , v } (sering ditulis e = uv)

adalah sisi dari G. Kita katakan : sisi e menghubungkan titik-titik u dan v

berhubungan langsung (adjacent) di G ; u dan v adalah titik-titik akhir dari sisi e

terkait (incident) dengan u atau v.

Sebuah graph G dapat dipresentasikan dalam bentuk diagram dimana setiap

titik G digambarkan dengan sebuah noktah dan setiap sisi yang menghubungkan

dua titik di G digambarkan dengan sebuah kurva sederhana (ruas garis) dengan

titik-titik akhir di kedua titik tersebut.

Contoh 1

Misal G adalah sebuah graph dengan

V (G )= {u , v , w , x , y , z } dan E (G )= {e1 , e2 , e3 , e4 , e5 , e6 , e7 }Dimana

e1=uv , e2=uw , e3=ux , e4=vx ,e5=wx , e6=xy , e7=xz

Kita dapat presentasikan graph ini dalam bentuk diagram seperti terlihat pada

gambar 1 berikut ini:

Gambar 1. Graph G dengan enam titik dan tujuh sisi

1

.

we3

v

y

x

u.

. . .

e2

e1

e4 e5 e6e7

e8

Sebuah sisi dalam graph G yang menghubungkan sebuah titik v dengan

dirinya sendiri disebut gelung (loop). Dalam suatu graph, apabila terdapat lebih

dari satu sisi yang menghubungkan dua titik, maka sisi-sisi tersebut disebut sisi

rangkap (multipleedges).

Contoh 2

Diagram graph G dengan V (G )= {u , v , w , x , y } dan

E (G )= {e1 , e2 , e3, e4 , e5, e6 , e7 , e8 } dimana

e1=uv , e2=ux , e3=xw , e4=vw , e5=vw , e6=vw ,e7=uy , e8=xx; dapat dilihat pada

gambar 2. Dalam contoh ini, sisi e8 adalah sebuah loop sedangkan sisi-sisi e4, e5,

e6 adalah sisi rangkap dalam G.

Gambar 2. Graph G dengan 5 titik dan 8 sisi.

Sisi e8 adalah sebuah gelung (loop)

Sedangkan sisi-sisi e4, e5, e6 adalah sisi rangkap

Sebuah graph yang tidak memiliki gelung dan tidak memiliki sisi rangkap

disebut graph sederhana. Sedangkan sebuah graph yang memilki sisi rngkap tetapi

tidak memilki gelung disebut graph rangkap (multi graph). Sebagai contoh, graph

G pada gambar 1, adalah graph sederhana, sedangkan graph G pada gambar 2

bukan graph sederhana. Dalam banyak hal, kita akan membatasi diri pada graph-

graph yang sederhana.

2

. .

(a) (b) (c) (d)

..

.. . .

..

. .

...

.

.. .

. ..

2. Beberapa Jenis Graph

Sebuah graph komplit (graph lengkap) dengan n titik, dilambangkan

dengan Kn, adalah graph sederhana dengan n titik dan setiap dua titik berbeda

dihubungkan dengan sebuah sisi. Selanjutnya graph yang tidak memiliki sisi

disebut graph kosong atau graph nol. Graph nol dengan n titik dilambangkan

dengan Nn. Misalnya graph komplit dengan 4 titik, atau 5 titik, dan graph kosong

dengan 5 titik, seperti pada gambar.

Sebuah graph G disebut graph bipartisi jika himpunan titik G V(G) dapat

dipartisi menjadi dua himpunan bagian A dan B sedemikian hingga setiap sisi dari

G menghubungkan sebuah titik di A dan sebuah titik di B. Kita sebut (A, B)

bipartisi dari G. Selanjutnya, apabila G sederhana dan bipartisi dengan bipartisi

(A, B) sedemikian hingga setiap titik di A berhubungan langsung dengan setiap

titik di B, maka G disebut graph bipartisi komplit, dilambangkan dengan Km,n

dimana |A|=m dan |B|=n .

Gambar 3

(a) K5 graph komplit (b) Graph kosong dengan 5 titik

(c) Graph bipartisi (d) K3,2 graph bipartisi komplit

3. Graph Bagian

Sebuah graph H disebut graph bagian G (ditulis H ⊂G), jika V ( H )⊂V (G )

dan E ( H )⊂E (G ) . Jika H ⊂G dan V ( H )=V (G ), maka H disebut graph bagian

rentang (spanning subgraph) dari G. Misalkan V 1⊂V (G). Graph bagian dari G

yang dibangun oleh V1, dilambangkan dengan G [V 1 ], adalah sebuah graph bagian

dari G yang himpunan titiknya adalah V1 dn himpunan sisinya beranggotakan

semua sisi G yang mempunyai titik-titik akhir di V1. Dalam gambar 4 graph H2

adalah graph bagian rentang dari graph G, graph H1 adalah graph bagian (bukan

3

.

u u

u

w

v v

w

y

zz

xy xy

zu

v

w

x

..

.

...

.

.

..

.

..

..

..

..

.

x

H3

z

G H1 H2

rentang) dari graph G dan H3 adalah graph bagian dari G yang dibangun oleh

V 1= {u , v , w , z }.

Gambar 4

H1 adalah graph bagian dari G

H2 adalah graph bagian rentang dari G

H 3=G { ⟨u , v , v , z ⟩ }

4. Jalan, Jejak, Lintasan, Sirkit, Sikel

Misalkan G adalah sebuah graph. Sebuah jalan (walk) di G adalah sebuah

barisan berhingga (tak kosong) W =(v0 ,e1 , v1 , e2 , v2 , …, ek , vk) yang suku-

sukunya bergantian titik dan sisi, sedemikian hingga vi−1 dan vk adalah titik-titik

akhir sisi e i, untuk 1 ≤i ≤ k. Kita katakan W adalah sebuah jalan dari titik v0 ke titik

vk, atau jalan-(v0, vk). Titik v0 dan titik vk berturut-turut disebut titik awal dan

titik akhir W. Sedangkan titik-titik v1, v2, ..., vk-1 disebut titik-titik internal W;

dan k disebut panjang jalan W (banyaknya sisi dalam W). Sebuah titik di G

mungkin saja muncul lebih dari satu kali dalam jalan W, begitu juga dengan

sebuah sisi di G, boleh muncul lebih dari satu kali pada jalan W.

Jika semua sisi e1, e2, e3, ..., ek dalam jalan W berbeda, maka W disebut

sebuah jejak (trail). Jika semua titik v0, v1, v2, ..., vk dalam jalam W juga

berbeda, maka W disebut lintasan (path). Sebuah jalan W dengan panjang positif

disebut tertutup, jika titik awal dan titik akhirnya dari W identik (sama). Jejak

tutup disebut sirkit. Sebuah sirkit di graph G yang memuat semua sisi G disebut

sirkit Euler. Sebuah Graph yang memuat sirkit Euler disebut graph Euler.

4

Sebuah sikel (cycle) adalah sebuah jejak tertutup (closed trail) yang titik awal dan

semua titik internalnya berbeda. Banyaknya sisi dalam suatu sikel disebut

panjang sikel. Sikel dengan panjang k disebut k-sikel, disimbolkan dengan Ck.

Semua sikel yang memuat titik semua graph disebut sikel Hamilton. Graph yang

memuat sikel Hamilton disebut graph Hamilton.

Contoh:

Gambar 5: Graph G

Perhatikan graph G di atas.

a. Barisan (v1,e1,v2,e2,v3,e5,v6,e5,v3) adalah sebuah jalan (v1,v3) di graph G yang

panjangnya 4.

Karena dalam barisan ini sisi e5 muncul lebih dari sekali, maka barisan ini

bukanlan sebuah jejak.

b. Barisan (v1,e3,v4,e6,v5,e9,v8,e11,v7,e8,v4) adalah sebuah jejak buka di G dengan

panjang 5. Karena titik v4 muncul lebih dari sekali, maka jejak tersebut

bukanlah lintasan.

c. Barisan (v1,e3,v4,e8,v7,e11,v8,e9,v5) adalah sebuah lintasan di G dengan panjang

4

5

d. Barisan (v1,e1,v2,e4,v5,e9,v8,e12,v9,e10,v6,e7,v5,e6,v4,e3,v1) adalah sebuah jejak

tutup (sirkit) di G dengan panjang 8.

Jejak tutup ini bukan sikel karena titik internal v5 muncul lebih dari sekali.

Sirkit

(

v1,e1,v2,e2,v3,e13,v2,e4,v5,e14,v3,e5,v6,e7,v5,e9,v8,e16,v6,e10,v9,e12,v8,e11,v7,e8,v4,e6,v5,e

15,v4, e3,v1) adalah sebuah sirkit Euler di G. Jadi G adala graph Euler.

e. Barisan (v1,e3,v4,e6,v5,e4,v2,e1,v1) adalah sebuah sikel di G dengan panjang 4.

Sikel (v1,e1,v2,e2,v3,e14,v5,e7,v6,e10,v9,e12,v8,e11,v7,e8,v4,e3,v1) memuat semua titik

G, jadi sikel tersebut merupakan sikel Hamilton. Dengan demikian graph G

merupakan graph Hamilton.

5. Graph Terhubung dan Komponen Graph

Sebuah graph G dikatakan terhubung (connected) jika untuk setiap dua titik

G yang berbeda terdapat sebuah lintasan yang menghubungkan kedua titik

tersebut. Sebaliknya graph G dikatakan tidak terhubung (disconnected). Sebuah

komponen graph G adalah sebuah graph bagian terhubung maksimal 9titik dan

sisi) dari G.

Graph H dikatakan graph bagian terhubung maksimal dari graph G, jika tidak

ada graph bagian lain dari G yang terhubung dan memuat H. Jadi graph terhubung

memiliki tepat satu komponen sedangkan graph tak terhubung memiliki paling

sedikit dua komponen.

Gambar 6: a. G graph terhubung

6

b. H graph tidak terhubung dengan 3 komponen, yaitu G1, G2, G3

Perhatikan graph G dan H di atas, (a) merupakan graph terhubung, karena

setiap dua titik yang berbeda di G dihubungkan oleh sebuah lintasan. Sedangkan,

graph H pada (b) merupakan graph tidak terhubung, karena tidak ada lintasan dari

v1 ke v6 di H. Dalam hal ini G1, G2, G3 adalah komponen-komponen di H.

6. Komplemen Graph

Misalkan G graph sederhana. Komplemen G dilambangkan dengan G,

adalah grapah sederhana yang himpunan titiknya sama dengan himpunan titik G

dan dua titik u dan v di G berhubungan langsung jika dan hanya jika di G titik u

dan v tidak berhubungan langsung.

Misalkan G = (V(G), E(G)) dan H = (V(H),E(H)) dua graph, maka

gabungan G dengan H, dinotasikan G∪H, adalah graph dengan himpunan titik

V (G )∪V (H ) dan himpunan sisi E (G )∪E (H ). Dengan demikian, jika G graph

sederhana dengan n titik, maka G∪G=K n. Contoh graph G, G dan G∪G dapat

dilihat pada gambar 7 berikut.

Gambar 7: Graph G, Komplemen G (G), dan G∪G

7

7. Derajat Titik

Misalkan G sebuah graph dan v sebuah titik di G. Derajat titik v

dilambangkan dengan dg(v) atau d(v), adalah banyaknya sisi G yang terkait

dengan titik v (dengan catatan setiap gelung dihitung dua kali). Derajat

minimum G, dilambangkan dengan δ (G), didefinisikan sebagai:

δ (G )=minimum{d ( v )/v∈V (G )}

Sedangkan derajat maksimum G, dilambangkan dengan ∆ (G), didefinisikan

sebagai: ∆ (G )=maksimum {d ( v ) /v∈V (G )}.

Graph G disebut graph beraturan-k jika setiap titik G berderajat k.

Misalnya, graph komplit dengan n titik adalah graph beraturan-(n-1). Graph H

pada gambar berikut adalah graph beraturan-3. Perhatikan bahwa, jika G graph

beraturan, maka δ (G )=¿ ∆ (G).

Gambar 8: a. Graph G dengan d(u) = 3, d(v) = 1, d(w) = 5, d(x) = 5, δ (G )=1,

Δ (G )=5

b. Graph H beraturan-3, δ (H )=3=Δ ( H )

Karena dalam menghitung jumlah derajat semua titik di sebuah graph, setiap

sisi graph dihitung tepat dua kali, maka jumlah derajat semua titik graph selalu

sama dengan dua kali banyaknya sisi graph tersebut. Sehingga diperoleh sebuah

teorema yang dikenal dengan Teorema jabat tangan.

Barisan derajat (dilambangkan dengan π ¿ dari graph G adalah barisan

monoton turun dari derajat titik-titik G. Sedangkan barisan derajat dari sebuah

8

graph sederhana disebut graphik. Misalnya, barisan derajat graph G pada gambar

diatas adalah π1=(5,5,3,1). Karena graph G bukan graph sederhana, maka π

bukan graphik. Perhatikan lagi graph bipartisi komplit K3,2 pada gambar 5 (d).

Graph ini memiliki 5 titik, dua diantaranya masing-masing berderajat 3 dan

sisanya masing-masing berderajat 2. Sehingga barisan derajat graph bipartisi

komplit K3,2 adalah π2=(3,3,2,2,2). Karena K3,2 graph sederhana, maka π2

adalah graphik.

8. Penyajian Graph dalam Matriks

Ada beberapa cara untuk menyajikan sebuah graph di dalam matriks yang

akan digunakaan; yaitu: “matriks berhubungan langsung” (adjacency matrix) dan

“matriks keterkaitan” (incindence matrix).

Misal G adalah sebuah graph dengan V(G)={v1,v2,...,vn}. Matriks

berhubungan langsung dari G adalah matriks bujur sangkar berordo n,

A(G)=(aij) dimana elemen a ij menyatakan banyaknya sisi yang menghubungkan

titik vi dan titik vj.

Perhatikan bahwa A(G) adalah matriks simetris. Kalau graph G tidak punya

gelung (loop), maka setiap unsur A(G) yang teletak pada diagonal utama adalah

nol. Kalau G graph sederhana, maka unsur-unsur dari A(G) nol atau satu.

9

v1

v2v3

v4

v5

[0 1 0 3 01 0 1 0 00 1 0 1 13 0 1 0 00 0 1 0 1

]

Jika diberikan sebuah matriks simetris A berordo n × n dimana setiap unsur A

adalah bilangan bulat non negatif, maka pasti terdapat sebuah graph G dengan

matriks berhubungan langsung A(G) = A.

Sekarang, kalikan matriks A dengan dirinya sendiri diperoleh.

Perhatikanlah bahwa unsur A2 yang terletak di baris ke i dan kolom ke j

menyatakan banyaknya jalan-(vi ,v j ) di graph G dengan panjang dua. Misalnya,

unsur A2 yang terletak di baris ke 1 dan kolom ke 2 adalah 4. Jadi ada 4 jalan-(v1 ,

v2) di graph G dengan panjang 2; yaitu: v1 e1 v1 e2 v2 , v1 e2 v2 e6 v2 , v1 e3 v3 e5 v2 ,

v1 e4v3 e5 v2 . Ada 5 jalan-(v3 ,v3) di G dengan panjang 2; yaitu: v3e5 v2e5v3 ,

v3 e4 v1 e4 v3 , v3 e3 v1 e3 v3 , v3e3 v1 e4 v3 , v3e4 v1 e3 v3 .

Selain dengan matriks berhubungan langsung, kita juga dapat menyajikan

sebuah graph dengan matriks keterkaitan.

10

A=[1 1 2 01 1 1 12 1 0 00 1 0 0 ]

A2=[6 4 3 14 4 3 13 3 5 11 1 1 1 ]

Misalkan graph G mempunyai n titik: v1 , v2 , .. . , vn dan s sisi: e1 , e2 ,. . ., en .

Matriks keterkaitan (incidence matrix) dari G adalah matriks M(G) = (mij) berordo n ×

s, dimana

mij={ 0 , jika sisi e j tidak terkaitan dengan titik v i

1 , jika e j terkait dengan v i dan e j bukan gelung2 , jika e j terkait dengan vi dan e j bukan gelung

Sebagai contoh, matriks keterkaitan dari graph G pada gambar 1.10 adalah

e1 e2 e3 e4 e5 e6 e7

M(G) =

v1

v2v3

v4

[2 1 1 1 0 0 00 1 0 0 1 2 10 0 1 1 1 0 00 0 0 0 0 0 1 ]

Perhatikan bahwa jumlah semua unsur M(G) yang terletak di baris 1

menyatakan derajat dari titik vi di graph G, sedangkan jumlah semua unsur M(G)

yang terletak di suatu kolom selalu 2.

9. Lintasan Terpendek

W(e) disebut bobot (weight) dari e jika sisi e dalam graph G dikaitkan dengan

sebuah bilangan real. W(G) merupakan lambang dari bobot dari sebuah graph, dan

merupakan jumlah bobot semua sisi G.

Panjang lintasan dalam sebuah graph-bobot adalah jumlah bobot dari

semua sisi dalam lintasan tersebuat. Misalkan u dan v adalah dua titik di graph G.

Lintasan (u,v) di G dengan panjang minimum disebut lintasan terpendek antara

u dan v. Sedangkan jarak dari u ke v, dinotasikan dengan dG(u,v) atau d(u,v), di

defenisikan sebagai panjang lintasan terpendek antara titik-titik u dan v di G.

11

Misalanya, lintasan terpendek yang menghubungkan titik v1 dan v5 di graph G

adalah lintasan (v1, v4, v7 ,v6, v5 ) yang panjangnya 1 + 2 + 2 + 2 = 7. Dengan

demikian W(v1, v5) = 7.

Perhatikan gambar graph G di atas, andaikan titik dalam graph tersebut

mewakili kota, sisi mewakili jalan antara dua kota, dan bobot sisi menyatakan

panjang jalan yang diwakili oleh jalan tersebut. Misalkan kita berada pada kota v1

dan ingin berpergian dengan mobil ke kota v11. Ada berapa lintasan yang bisa kita

tempuh, misalnya panjang

P1 = (v1, v2, v5, v8, v11);

P2 = (v1, v3, v6, v9, v11);

P3 = (v1, v4, v7, v10, v11); atau

P4 = (v1, v4, v7, v6, v9),

yang secara berturut-turut panjangnya 14, 15, 14, dan 13. Tentu saja dari segi

aplikasi di antara keempat lintasan tersebut, lintasan P4 yang paling

menguntungkan.

12