isomorfisme pada graph

Teori Graph Halaman 0

TEORI GRAPH

Dosen Pengampu :

Dyani Primaningsih, S.Pd.

Disusun oleh :

Kelompok 2

1. HERI CAHYONO ( 08411.145 )

2. AGUNG DWI CAHYONO ( 08411.056 )

3. RUDI HARTONO ( 08411.248 )

4. MIKI ARIF NUGROHO ( 08411.188 )

5. AGUS DWI PRASETYO ( 08411.059 )

6. ARDHIE KUSUMA ( 08411.073 )

PROGRAM STUDI PENDIDIKAN MATEMATIKA

FAKULTAS PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN

ALAM

IKIP PGRI MADIUN

2011


1. Graph bipartisi

Sebuah graph dikatakan bipartisi jika himpunan titik 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 dan dilambangkan dengan

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

Contoh:

Gambar diatas adalah contoh graph G bipartisi, sebagai akibat dari

definisi graph bipartisi mungkin saja mempunyai sisi rangkap, tetapi tidak

mungkin memuat gelung. Begitu juga banyaknya titik graph bipartisi komplit

Km.n adalah m+n dan banyaknya sisi adalah mn.

2. Isomorfisme pada Graph

Dua graph G dan H dikatakan isomorfik, ditulis G ≡ H, jika : (i)

terdapat korespondensi satu-satu antara V(G) dan E(G); (ii) banyaknya sisi

yang menghubungkan dua titik u dan v di G, sama dengan banyaknya sisi yang

menghubungkan dua titik di H yang berkorespondensi dengan titik u dan titik

v. Misalnya pada gambar berikut, graph G1 isomorfik dengan graph G2 lewat

korespondensi berikut a↔t, b↔s, c↔r, d↔q, e↔p, f↔u. Sedangkan graph G3

memuat sikel dengan panjang 3, yaitu (k,z,m,x), tetapi di graph G1 maupun di

graph G2 tidak ada sikel dengan panjang 3.

G1 G2 G3

a

d

c b

f e

t s r

u p q

n

m k

l

z x

G K3.2


Sebagai akibat dari definisi diatas, diperoleh pernyataan berikut. Jika G dan H

dua graph isomorfik, maka |V(G)| = |V(H)| dan |E(G)| = |E(H)|. Tetapi,

konversi pernyataan tersebut tidak benar.

3. Derajat titik graph

Misalkan G sebuah graph dan v sebuah titik 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 berikut :

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

Sedangkan deajat maksimum G, dilambangkan dengan Δ(G), didefinisikan

sebagai berikut :

Δ(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). Sikel

dengan n titik, Cn adalah graph beraturan-2. Graph H pada gambar dibawah

adalah graph bertauran-3. Perhatikan bahwa jika G graph beraturan, maka δ(G)

= Δ(G).

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. Pernyataan ini merupakan

teorema pertama dalam teori graph, dan dikenal dengan sebutan “ teorema

jabat tangan “.

G H

v

u

w x


Teorema 1.1 :

(teorema jabat tangan). Jika G sebuah graph maka

= 2|E(G)|

Sebagai akibat dari teorema tersebut adalah teorema berikut.

Teorema 1.2 :

Banyaknya titik berderajat ganjil pada sebuah graph adalah genap.

Bukti: Pandang sembarang graph G. Misalkan A dan B, berturut-turut adalah

himpunan semua titik G yang berderajat genap dan ganjil. Jelas bahwa

V(G)=A B, sehingga

(Teorema 1.1)

Selanjutnya, karena untuk setiap v A, d(v) genap, maka genap.

akibatnya, genap. Padahal untuk setiap titik v B, d(v) ganjil.

Akibatnya banyaknya titik di B atau |B| genap. (Terbukti)

Perhatikan bahwa jika graph G beraturan-k, dengan n titik maka nk

genap. Kiranya jelas bahwa tidak ada graph beraturan-k dengan n titik jika n

dan k kedua-duanya bilangan ganjil.

Misalkan G sebuah graph. Barisan monoton turun dari derajat titik-titik

G disebut barisan derajat graph G, jika G sederhana maka barisan derajat G

disebut graphik. Barisan derajat suatu graph dilambangkan dengan π Misalnya,

barisan derajat graph G pada gambar di atas adalah π1 = (5,5,3,1), karena

graph G tersebut bukan graph sederhana, maka π1 bukan graphik. Pikirkan

graph bipartisis komplit K3.2 graph ini memiliki 5 titik, dua diantaranya

masing-masing berderajat 3 dan sisanya masing-masing berderajat 2 titik.

Sehingga barisan derajat K3.2 adalah π2 = (3,3,2,2,2). karena K3.2 graph

sederhana maka π2 adalah graphik.

Jika diberikan sebuah graph, dengan mudah kita bisa menentukan

barisan derajatnya. Yang menjadi pertanyaan adalah apakah syarat dari sebuah

barisan agar barisan tersebut merupakan barisan derajat sebuah graph? jawaban

atas pertanyaan tersebut disajikan dalam teorema berikut.


Teorema 1.3 :

Barisan bilangan bulat non negatif (d1, d2, . . ., dn) adalah barisan derajat

sebuah graph jika dan hanya jika genap.

Untuk menentukan apakah barisan bilangan bulat non negatif merupakan suatu

graphik atau bukan, dapat digunakan teorema berikut.

Teorema 1.4 :

misalkan π = (d1, d2, . . . dn) barisan bilangan bulat non negatif monoton turun.

Barisan π graphik jika dan hanya jika barisan (d2-1, d3-1,......dd1+1-1, dd1+2-

1....dn) graphik.

4. Representasi graph dalam matriks

Selain dengan gambar, sebuah graph dapat disajikan dalam bentuk

matriks. Ada dua jenis matriks yang digunakan, yaitu matriks berhubungan

langsung (adjacency matrix) dan matriks keterkaitan (incidence matrix).

Misalkan G sebuah graph dengan G(G) = {v1, v2, .., vn}. Matriks

berhubungan langsung graph G adalah matriks bujur sangkar A(G) = (aij)

berordo n x n yang baris dan kolomnya dilabel dengan label titik-titik graph G

sedemikian hingga elemen aij menyatakan banyaknya sisi G yang

menghubungkan titik vi dan vj.

A(G) =

Perhatikan bahwa A(G) adalah matriks simetris dan unsur-unsurnya

bilangan bulat non negatif. Jika G tidak memiliki gelung, maka setiap unsur

A(G) yang terletak di diagonal utama adalah nol. Kalau G graph sederhana,

maka unsur-unsur A(G) nol atau satu. Jika diberikan sebuah matriks simetris A

berordo nxn dan unsur-unsurnya bilangan bulat non negatif, maka pasti ada

graph G dengan titik n dan matriks berhubungan langsung A(G) = A.

V1

V2

V3

V4

V1 V2 V3 V4

V1

V2

V3

V4

e1 e2

e3

e4

e5

e8

e6

e7

G


Perhatikan bahwa derajat titik graph G diperoleh dengan menjumlahkan semua

unsur A yang terletak di baris yang bersesuaian dengan titik tersebut, setelah

unsur pada diagonal utama di baris itu dikalikan dua. Misalnya:

d(v1) = 2x0 + 2 + 1 + 0 = 3

d(v2) = 2 + 2x0 + 1 + 0 = 3

d(v3) = 1 + 1 + 2x1 + 3 = 7

d(v4) = 0 + 0 + 3 + 2x0 = 3

Secara umum diperoleh sebagai berikut. Jika A = (aij) matriks berhubungan

langsung graph G, maka

D(vi) = aii +

Jika matriks A(G) = A dikalikan dengan dirinya sendiri, maka diperoleh

A2 =

Perhatikan unsur A2 yang terletak di baris ke-i dan kolom-j menyatakan

banyaknya jalan-(vi, vj) di graph G dengan panjang 2. Misalnya unsur A2 yang

terletak pada baris ke-1 dan kolom ke-4 adalah 3. Jadi ada 3 jalan-(v1, v4) di

graph G dengan panjang 2, yaitu : (v1, e3, v3, e6, v4), (v1, e3, v3, e7, v4), (v1, e3,

v3, e6, v4). Ada 5 jalan-(v1, v1) di graph G dengan panjang 2, yaitu: (v1, e1, v2,

e1, v1), (v1, e1, v2, e2, v1), (v1, e2, v2, e1, v1), (v1, e2, v2, e2, v1), (v1, e3, v3, e3, v1).

Begitu juga terdapat 3 jalan di (v3, v2), generalisasi dari observasi ini diberikan

pada teorema berikut:

Teorema 1.5:

Misalkan G adalah graph dengan V(G) = {v1, v2, …., vn). Jika A adalah

matriks berhubungan langsung graph G, maka untuk suatu bilangan bulat

positif k, unsur matriks Ak yang terletak di baris ke-i dan kolom ke-j

menyatakan banyaknya jalan yang menghubungkan titik vi dan titik vj di graph

G dengan panjang k.

V1 V2 V3 V4 V1

V2

V3

V4


Dari teorema 1.5 dapat dibuktikan pula teorema berikut:

Teorema 1.6:

Misalkan G sebuah graph dengan V(G)={v1, v2, . . . , vn}. misalkan A adalah

matriks berhubungan langsung graph G dan B = (bij) adalah matriks dengan B

= A + A2 + . . . + A

n-1. Graph G terhubung jika dan hanya jika bij ≠ 0, untuk

setiap i dan j, i ≠ j.

Selain dengan matriks berhubungan langsung, sebuah graph dapat pula

disajikan dalam matriks keterkaitan. Misalkan graph G mempunyai n buah titik

: v1, v2, . . ., vn dan t buah sisi : e1, e2, . . ., et. Matriks keterkaitan graph G

adalah matriks M(G) = (mij) berordo n x t yang barisnya dilabel dengan label

titik-titik G dan kolomnya dilabel dengan label sisi-sisi G, sedemikian hingga

0 , Jika sisi ej tidak terkait dengan titik vi

Mij = 1 , Jika sisi ej terkait dengan titik vi dan ej bukan gelung

2 , Jika sisi ej terkait dengan titik vi dan ej gelung

Contoh : perhatikan gambar graph G berikut

Matriks keterkaitan dari graph tersebut adalah sebagai berikut

M(G) =

Jumlah semua unsur M(G) yang terletak pada baris ke-I menyatakan derajat

titik vi di graph G, sedangkan jumlah semua unsur M(G) yang terletak pada

setiap kolom selalu 2.

V1

V2

V3

V4

e1 e2 e3 e4 e5 e6 e7 e8

V1

V2

V3

V4

e1 e2

e3

e4

e5

e8

e6

e7

G


DAFTAR PUSTAKA

isomorfisme pada graph

Documents