6 bab ii landasan teori a. graf dan unsur-unsurnya suatu graf

6

BAB II

LANDASAN TEORI

A. Graf dan Unsur-unsurnya

Suatu graf (Mardiyono, 1996, hal:1) dapat dipandang sebagai

kumpulan dari titik yang disebut simpul dan segmen garis yang

menghubungkan 2 simpul yang disebut rusuk. Secara matematis, Goodaire dan

Parmenter (1998: 329), graf dapat dilambangkan dengan (V(G),E(G)), V(G)

yang unsur-unsurnya disebut simpul (vertek) dan E(G) mungkin kosong

yang unsur-unsurnya disebut rusuk (edge). Jika u dan v adalah sepasang

simpul yang berbeda di G, uv melambangkan rusuk di G, dan jika e = uv

adalah sebuah rusuk di G maka :

1. u dan v berdekatan (adjacent) di G

2. rusuk e menghubungkan (joining) simpul u dan v di G

3. u dan v adalah simpul-simpul ujung rusuk di e

4. rusuk e hadir (incident) di simpul u dan v atau sebaliknya dikatakan

simpul u dan v hadir pada rusuk e.

Sebuah graf G (Mardiyono, 1996, hal : 7) dapat digambarkan dengan

menggunakan noktah sebagai simpul dan rusuk digambarkan dengan segmen

garis (lurus atau lengkung) yang menghubungkan dua simpul yang berelasi.

Letak simpul dan jarak antara dua simpul serta bentuk garis penghubung

kedua simpul tersebut dapat digambarkan secara bebas.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

http://www.novapdf.com


7

Menurut Mardiyono, (1996: 12) dua simpul u dan v disebut berikatan

jika kedua simpul tersebut merupakan ujung suatu rusuk tertentu yang

menghubungkan simpul u dan v. Berikut contoh untuk 2 simpul yang saling

berikatan.

u e v

G

Gambar 1. Dua simpul u dan v berikatan pada graf G.

Pada Gambar 1 di atas, graf G terdiri atas 2 simpul u dan v yang saling

berikatan karena dihubungkan oleh rusuk e, sehingga simpul u dan v

merupakan ujung rusuk e pada graf G.

Suatu simpul dalam sebuah graf tidak selalu terhubung dengan simpul

lainnya. Simpul yang demikian ini disebut simpul terasing (simpul terisolasi).

Gambar 2. Graf dengan simpul terisolasi v3

Tampak pada Gambar 2, simpul v3 tidak terhubung dengan simpul

lainnya sehingga simpul v3 merupakan simpul terisolasi.

Pada suatu graf mungkin saja terdapat 2 rusuk atau lebih yang

menghubungkan 2 simpul tertentu. Rusuk yang semacam ini disebut rusuk

ganda (multiple edges). Rusuk yang menghubungkan simpul tertentu dengan

dirinya sendiri disebut gelang (loop). Graf yang memuat gelang dan rusuk

v3

e

v2

v1

G




8

ganda disebut graf ganda. Berikut ilustrasi sebuah graf ganda yang memuat

gelang dan rusuk ganda.

Gambar 3. Graf Ganda

Pada Gambar 3 di atas, pada graf G terdapat rusuk ganda yaitu e1, e2

dan pada graf H terdapat gelang e2. Selanjutnya graf yang tak berusuk ganda

dan tak bergelang disebut graf sederhana.

B. Derajat Simpul

Menurut Mardiyono (1996: 12) derajat simpul vi adalah banyaknya

ujung rusuk yang hadir pada simpul vi. Derajat minimum (terkecil) dan derajat

maksimum (terbesar) pada graf G dengan himpunan simpul V(G) berturut-

turut dilambangkan dengan δ(G) dan Δ(G). Berikut contoh derajat suatu

simpul pada graf G.

Gambar 4. Graf G

v1 v3

v2 v4

G

v w

H

e1 v2 v1

G

e1

e2

v3

e3

e2




9

Pada Gambar 4 terlihat bahwa d(v1) = d(v2) = 3, karena banyaknya

ujung rusuk yang hadir pada simpul v1 dan v2 masing-masing sebanyak 2

buah. Untuk d(v3) = 4, karena banyaknya ujung rusuk yang hadir pada v3 4

buah, sedangkan pada v4 karena tidak ada rusuk yang hadir disimpul itu maka

d(v4) = 0. Sehingga graf G di atas mempunyai δ(G) = 0 dan Δ(G) = 4. Jika

d(vi) = d untuk setiap vi V(G) atau δ(G) = Δ(G) = d, maka dapat dikatakan

G adalah graf teratur berderajat d, disingkat teratur-d.

C. Jenis-jenis Graf

Sesuai dengan kekhasan strukturnya, graf dapat diklasifikasikan dalam

beberapa jenis (Mardiyono, 1996, hal: 32), yaitu :

1. Jenis graf berdasarkan ada tidaknya gelang dan rusuk ganda.

Berdasarkan ada tidaknya gelang dan rusuk ganda graf dapat dibedakan

menjadi 2 jenis, yaitu :

a. Graf sederhana

Graf sederhana adalah graf yang tidak memuat rusuk ganda dan gelang.

Beberapa graf sederhana dapat ditunjukkan sebagai berikut :

1) Graf nol adalah graf yang tidak memiliki rusuk atau himpunan rusuknya

merupakan himpunan kosong. Gambar 5 berikut ini menunjukkan graf nol

dengan 2 buah simpul.

Gambar 5. Graf nol dengan banyak simpul 2

v1 v2 G




10

2) Graf lengkap adalah graf sederhana yang setiap pasang simpulnya saling

berikatan. Notasi graf lengkap dengan n simpul adalah Kn.

Contoh graf lengkap dengan n gasal (K3) dan n genap (K4) ditunjukkan

oleh Gambar 6 berikut ini.

Gambar 6. Graf K3 dan K4

3) Graf bipartit adalah graf sederhana yang himpunan simpulnya dapat

dipartisi menjadi 2 bagian, misal X dan Y sehingga setiap rusuknya

mempunyai simpul ujung di X dan simpul ujung yang lain di Y. Contoh

graf bipartit terlihat pada Gambar 7 berikut.

Gambar 7. Graf Bipartit

4) Graf bipartit lengkap adalah suatu graf bipartit yang semua simpul di

partisi satu dihubungkan ke semua simpul di partisi yang lain. Notasi graf

bipartit lengkap dengan banyaknya simpul di bagian yang satu m dan

bagian yang lain n adalah Km,n. Gambar 8 berikut ini ilustrasi dari sebuah

graf bipartit lengkap Km,n dengan m = 2 dan n = 3.

G

Y

X

K3 K4




11

Gambar 8. Graf bipartit lengkap

b. Graf tidak sederhana

Graf tidak sederhana adalah graf yang memiliki gelang atau rusuk ganda.

Contoh graf tidak sederhana seperti terlihat pada Gambar 9 dibawah ini.

Gambar 9. Graf tidak sederhana G dan H

Tampak pada Gambar 9 bahwa graf G memuat rusuk ganda dan

pada graf H memuat gelang/loop sehingga keduanya merupakan graf tidak

sederhana.

2. Jenis graf berdasarkan keteraturan derajat simpulnya.

Berdasarkan keteraturan derajat dari setiap simpulnya graf dapat

dibedakan menjadi 2 jenis, yaitu :

a. Graf teratur

Graf teratur adalah graf yang setiap simpulnya berderajad sama.

v1 v3

v2 G

v1

v2

H

G = K2,3




12

Berikut ilustrasi dari graf teratur.

Gambar 10. Graf G teratur-2 dan graf H teratur-1

Tampak pada Gambar 10 bahwa setiap simpul pada graf G mempunyai

derajat yang sama yaitu 2 dan setiap simpul pada graf H juga mempunyai

derajat yang sama yaitu 1, sehingga dapat disimpulkan bahwa graf G dan

H keduanya merupakan graf teratur.

b. Graf tidak teratur

Graf tidak teratur adalah graf yang tidak setiap simpulnya mempunyai

derajad yang sama. Sebagai contoh terlihat pada Gambar 11 berikut.

Gambar 11. Graf tidak teratur G

Dari Gambar 11 di atas tampak bahwa d(v1) = d(v4) = 3 dan d(v3) = d(v2)

= 2. Karena dalam satu graf terdapat derajat simpul yang berbeda maka

graf G tersebut dikatakan graf tidak teratur.

v1

v3

v2

v4 G

v1

v3

v2

v4 v1 v2

G H




13

D. Graf Bagian dan Gabungan Graf

Graf bagian H dari graf G, ditulis H G adalah suatu graf yang

memenuhi V(H) V(G) dan E(H) E(G) (Mardiyono, 1996, hal: 34).

Gambar 12 berikut ini menunjukkan contoh graf bagian H dari graf G.

Gambar 12. Graf bagian H G

Gabungan dari dua graf H dan F yang dinotasikan dengan H F

adalah graf yang mempunyai himpunan simpul V(H) V(F) dan himpunan

rusuk E(H) E(F) (Wilson, 1979, hal: 17). Contoh gabungan graf H dan F

terlihat pada Gambar 13 berikut.

hasilnya :

Gambar 13. Gabungan 2 buah graf

F 1 5

2 4

3 3

H 5

4 2

1

G H

d

c b

a a d

b c

H F 1

2

3

5

4

e e




14

E. Komplemen suatu Graf

Komplemen suatu graf sederhana G, ditulis Gc, adalah suatu graf yang

mempunyai himpunan simpul V(G) dan setiap dua simpul di Gc saling

berikatan jika dan hanya jika keduanya tidak berikatan di G (Mardiyono, 1996,

hal : 32). Contoh komplemen graf sederhana terlihat pada Gambar 13 berikut.

Gambar 14. Komplemen Graf Sederhana

Gambar 14 di atas menujukkan bahwa G adalah komplemen dari H,

dan sebaliknya H adalah komplemen dari G.

Definisi komplemen suatu graf memberikan beberapa akibat, yaitu :

1. jika G suatu graf lengkap maka Gc adalah graf nol

2. untuk setiap graf G maka berlaku G Gc adalah graf lengkap.

F. Trayek, Jejak, Lintasan, Sirkuit dan Sikel

Trayek (walk) pada graf G dengan V(G) = {v1,v2,v3, …,vn} dan

E(G) = {e1,e2,e3, …, em} merupakan barisan berhingga W=(v1,e1,v2,e2,…,

en-1,vn) yang suku-sukunya berupa simpul dan rusuk secara bergantian

sedemikian sehingga vi dan vi+1 adalah simpul ujung dari ei. Simpul v1 dan vn

berturut-turut disebut simpul awal dan simpul akhir dari W. Suatu trayek

4 3

5

1

2

G 4 3

5 2

1

H = Gc




15

dikatakan trayek tertutup jika simpul awal dan simpul akhirnya sama. Sebagai

contoh, (perhatikan Gambar 15) W1 = (v1,e1,v2,e6,v3,e5,v2) merupakan sebuah

trayek (walk) pada graf G. Trayek W2 = (v1,e1,v2,e6,v3,e5,v2,e1,v1) merupakan

sebuah trayek tertutup karena simpul awal dan simpul akhirnya sama.

Gambar 15. Graf G

Jejak (trail) adalah trayek tanpa rusuk berulang. Sebagai contoh

perhatikan Gambar 15, J = (v1,e2,v3,e6,v2,e5,v3) merupakan sebuah jejak (trail)

pada graf G, karena tidak memuat rusuk berulang.

Lintasan (path) adalah trayek tanpa rusuk dan simpul berulang.

Sebagai contoh perhatikan Gambar 15, L = (v1,e1,v2,e6,v3,e4,v4) merupakan

sebuah lintasan (path) pada graf G, karena tidak memuat simpul dan rusuk

berulang.

Sirkuit (circuit) adalah jejak tertutup. Perhatikan Gambar 15,

C = (v1,e1,v2,e5,v3,e6,v2,e3,v4,e4,v3,e2,v1) merupakan sebuah sirkuit pada graf G.

Sikel (cycle) adalah jejak tertutup yang simpul awal dan semua simpul

internalnya (simpul selain simpul awal dan simpul akhir ) berbeda. Perhatikan

Gambar 15, S = (v1,e2,v2,e5,v2,e1,v1) merupakan sebuah sikel pada graf G

karena simpul awal dan semua simpul internalnya berbeda. H disebut sikel

Hamilton jika H adalah sikel yang memuat semua simpul dari G.

v3

e6

e5

v1 v2

v4

e3 e2

e4

e1




16

H = (v1,e1,v2,e3,v4,e4,v3,e2,v1) merupakan sebuah sikel Hamilton karena sikel

H memuat semua simpul pada graf G.

G. Keterhubungan

Sebuah graf G dikatakan terhubung jika untuk setiap dua simpul di G

selalu terdapat lintasan (path) yang menghubungkan kedua simpul tersebut

(Rossen, 1999, hal: 468). Sebaliknya graf G disebut graf tidak terhubung jika

tidak ada lintasan (path) yang menghubungkan u dan v di G. Contoh dari graf

terhubung dan tidak terhubung ditunjukkan dengan Gambar 15 berikut ini.

Gambar 16. (a) Graf G1 tidak terhubung dan (b) Graf G2 terhubung

Suatu subgraf terhubung yang tidak termuat pada subgraf lainnya

disebut komponen graf (Ross dan Wright, 1985, hal: 358). Graf pada Gambar

16(a) G1 mempunyai dua komponen, sedangkan graf pada Gambar 16(b) G2

mempunyai 1 komponen. Selanjutnya, komponen graf dengan cacah simpul

ganjil disebut komponen ganjil.

H. Matching

Menurut L. Cacceta, dkk (1992: 232) matching M pada graf G adalah

himpunan rusuk dari graf G yang tidak hadir pada simpul yang sama. Sebagai

(a) (b)

G1 G2




17

contoh, pada Gambar 17 dibawah ini, M1 = {ab, cd} adalah matching pada

graf G yang terdiri dari dua rusuk dan M2 = {ef} adalah matching yang terdiri

dari satu rusuk.

Gambar 17. M1 = {ab, cd}, M2 = {ef} suatu matching pada G

Menurut Mardiyono (2001 : 91) apabila matching pada graf G

melibatkan semua simpul pada graf G, maka matching tersebut disebut

sebagai faktor-1 (perfect matching). Sebagai contoh perhatikan Gambar 17,

faktor-1 yang terdapat pada graf G tersebut adalah :

F1 = ab cd ef

F2 = bc de fa

I. Faktor -1

Menurut Mardiyono (1997 : 6) faktor-1 dari graf G adalah graf bagian

teratur dan berderajat satu yang memuat semua simpul G. Dengan demikian

jika suatu graf memiliki faktor-1 atau perfect matching, maka banyaknya

simpul harus genap. Tetapi hal ini tidak menjamin berlaku sebaliknya. Suatu

graf G yang banyaknya simpul genap tidak menjamin adanya faktor-1.

e

a

c

d

f

b




18

Berikut ilustrasi dari tidak adanya faktor-1 pada graf G meskipun

memiliki jumlah simpul n(G) genap

Gambar 18. Graf G dengan n(G) = 10 tidak memiliki faktor-1

Tampak pada Gambar 18, graf G tidak memiliki faktor-1 meskipun

n(G) genap.

Dekomposisi graf merupakan penggambaran dari suatu graf menjadi

sejumlah pasangan-pasangan himpunan bagian yang saling asing. Dua faktor-1

dikatakan saling asing jika keduanya tidak mempunyai rusuk persekutuan. Jika

setiap rusuk G dapat dikelompokkan menjadi sejumlah faktor-1 yang saling

asing (tanpa rusuk persekutuan) maka G dikatakan memiliki faktorisisasi-1.

Dari definisi faktorisasi-1 dapat dikatakan bahwa suatu graf yang

memiliki faktorisasi-1 pasti merupakan graf teratur yang banyak simpulnya

genap, akan tetapi tidak setiap graf teratur dengan banyaknya simpul genap

selalu memiliki faktorisasi-1. Berikut contoh mengenai mengenai hal tersebut.

Gambar 19. Graf teratur G yang tidak memiliki faktorisasi-1

G d c

a b e f

j i

g h

j

e

g

f

h

i

c a

b d

G




19

Misalkan dari graf G pada Gambar 18 diambil faktor-1 yaitu

F1 = ab cd ef gh ij

Sisa rusuk dari graf G setelah pengambilan F1 sudah tidak bisa dibuat faktor-1,

hal ini mengakibatkan bahwa graf G tidak memiliki faktorisasi-1

Eksistensi faktorisasi-1 dalam graf lengkap K2n telah ditunjukkan oleh

Wallis (Wallis, 1987, hal : 117). Eksistensi faktorisasi-1 tersebut disajikan

pada Teorema 1 berikut ini .

Teorema 1:

Untuk setiap bilangan asli n, K2n mempunyai faktorisasi-1.

Bukti :

Salah satu teknik yang digunakan untuk menunjukkan adanya

faktorisasi-1 pada K2n dengan himpunan simpul {1,2,3,…,2n-2,2n-1,2n}adalah

sebagai berikut. Andaikan faktorisasi-1 pada K2n adalah F={F1,F2,…,F2n-1}.

Pertama dibuat konstruksi segi (2n-1) beraturan. Kemudian dibuat konstruksi

salah satu faktor-1 anggota F, misal F1, dengan menempatkan semua simpul

K2n tersebut secara berurutan pada titk-titik sudut segi (2n-1) kecuali simpul

ke-2n yang harus ditempatkan pada pusat segi (2n-1). Penempatan semua

simpul yang lain harus sedemikian rupa sehingga semua rusuk dari F1 dalam

posisi mendatar, kecuali rusuk (1,2n) yang posisinya tegak. Sebagai ilustrasi

dari konstruksi F1 F tersebut perhatikan Gambar 20 berikut.




20

Gambar 20. Sebuah faktor-1 pada K2n

Dari Gambar 20 di atas diperoleh faktor-1 yang pertama yaitu

F1 = 1(2n) 2(2n-1) 3(2n-2) … n(n+1)

Kemudian untuk mendapatkan faktor-1 yang lain, dapat diperoleh

dengan melakukan rotasi simpul-simpul selain simpul 2n dengan

menggunakan sudut perputaran .

Untuk putaran yang pertama misal diperoleh

F2 = (2n-1)(2n) (2n-2)1 (2n-3)2 … n(n-1)

sampai diperoleh faktor-1 sebanyak (2n-1) faktor-1 F = {F1,F2,…,F2n-1} pada

K2n. Terbukti K2n memiliki faktorisasi-1.

Teorema 2: (Caccetta, dkk, 1979: 219)

Graf bipartit lengkap Kv,v mempunyai faktorisasi yang Hamilton.

Bukti :

Misalkan Kv,v adalah graf bipartit yang mempunyai himpunan simpul

dengan partisi X = {1,2,3,…,v} dan partisi Y = {1,2,3,…,v}. Kemudian

1

2n. .

.

3(2n-2)

2(2n-1)

2n+1

. . .2n

123600

n

n-1 n+2




21

dimisalkan H1,H2,H3,…Hv adalah faktor-1-faktor-1 pada Kv,v yang

didefinisikan sebagai berikut :

H1 : 11 22 … i i … vv

H2: 12 23 … i(i+1) … v1 . . . Hv : 1v 21 … i(i+v-1) … v(v-1)

Maka diperoleh

Hj : 1j 2(j+1) … i(j+i-1) … v(j+v-1)

Selanjutnya dengan menganggap 1,2,3,…,v sebagai bilangan modulo v

adalah bentuk faktorisasi-1 pada Kv,v dan H1 H2 adalah sikel Hamilton.

Terbukti graf bipartit mempunyai faktorisasi-1 yang Hamilton.

Pengambilan faktorisasi-1 pada K2n apabila dilakukan secara acak

(random) maka ada dua kemungkinan hasil yang diperoleh yaitu pertama

berhasil didapatkan suatu faktorisasi-1 dan yang kedua tidak diperoleh

faktorisasi-1 pada K2n (gagal). Untuk hasil faktorisasi-1 yang gagal, ada dua

kemungkinan yang diperoleh yaitu :

1. Diperoleh himpunan faktor-1 yang komplemen dari gabungan semua

anggota-anggotanya (daun dari G) masih memuat minimal satu faktor-1

tetapi tidak memiliki faktorisasi-1. Himpunan faktor-1 semacam ini

disebut dengan himpunan prematur faktor-1 yang sebenarnya. Untuk

selanjutnya himpunan ini dikatakan himpunan prematur faktor-1.

2. Diperoleh himpunan faktor-1 yang komplemen dari gabungan semua

anggotanya (daun dari G) bukan graf nol dan tanpa faktor-1 yang disebut




22

dengan himpunan prematur faktor-1 yang tidak sebenarnya. Untuk

selanjutnya himpunan semacam ini disebut himpunan maksimal faktor-1.

J. Himpunan Maksimal Faktor -1

Himpunan faktor-1 S di graf G disebut maksimal (Cacetta, dkk, 1979, hal :

217) jika

i) faktor-faktor-1 di S saling asing

ii) tidak ada faktor-1 dari G yang saling asing dengan semua anggota S

iii) gabungan semua anggota S tidak sama dengan G

Dengan kata lain, jika adalah komplemen dari gabungan anggota-anggota

S, maka S maksimal jika dan hanya jika adalah bukan graf nol dan tanpa

faktor-1. ini disebut daun (leave) dari S.

Berikut ini diberikan ilustrasi mengenai himpunan maksimal faktor-1

pada K6 dengan himpunan simpul {A,B,C,D,E,F}. Andaikan setelah dilakukan

pemilihan faktor-1 secara acak diperoleh himpunan faktor-1 sebagai berikut :

F1 = AB CD EF

F2 = AD BE CF

F3 = AF BC DE

Komplemen himpunan maksimal faktor-1 di atas adalah Gc :

Gambar 21. Gc

S

S

S

C

A

F

E

D

B




23

Setelah dilakukan pengecekan pada Gc, ternyata sudah tidak memuat

faktor-1 lagi. Karena sudah tidak memuat faktor-1, maka himpunan F={Fi ,

i=1, 2, 3} di atas merupakan himpunan maksimal faktor-1.

Lemma yang berkaitan dengan himpunan maksimal faktor-1 adalah sebagai

berikut :

Lemma 1: (Wallis, 1981)

Jika G adalah graf teratur-d yang tidak memuat faktor-1 dan komponen ganjil,

maka berlaku :

(3d+7), untuk d ganjil > 3

V(G) > (3d+4), untuk d genap > 6

22, untuk d = 4

Lemma tersebut tidak berlaku untuk d = 1, atau d = 2

K. Himpunan Prematur Faktor -1

Himpunan prematur faktor-1 (Rosa dan Wallis, 1982, hal: 292) adalah

himpunan faktor-1 yang komplemennya memuat faktor-1 tetapi tidak memiliki

faktorisasi-1. Jika adalah komplemen dari himpunan faktor-1 F, maka F

dikatakan himpunan prematur faktor-1 yang sebenarnya, jika memiliki

paling sedikit 1 faktor-1. Untuk selanjutnya himpunan ini dikatakan himpunan

prematur faktor-1. dinamakan daun dari G, dan derajat keteraturan dari

daun disebut defisiensi. Banyaknya faktor-1 pada himpunan prematur

faktor-1 dengan defisiensi d adalah (2n-d-1).

F

F

F

F




24

Berikut disajikan suatu Lemma yang sangat berguna untuk penelitian

tentang himpunan prematur faktor-1 (Cacetta dan Mardiyono, 1992),

Eksistensi Himpunan Prematur faktor-1 pada graf lengkap (Mardiyono, 1991).

Lemma 2 : (Cacetta dan Sugeng Mardiyono, 1990)

Jika G suatu graf yang memiliki c.k rusuk dan c > χ' (G), maka himpunan

rusuk G dapat dikomposisikan kedalam c matching, setiap matching memuat k

rusuk.

Bilangan kromatik dari graf G, dinotasikan χ'(G) adalah banyaknya

warna minimal yang dibutuhkan untuk mewarnai rusuk di G sedemikian

sehingga tidak ada dua rusuk yang hadir pada sebuah simpul mempunyai

warna yang sama. (Robin J.Wilson dan John J. Watkins, 1990, hal : 240).

Lemma 3 : (Cacetta dan Mardiyono, 1992)

Jika G adalah suatu graf teratur-d dengan 2n simpul yang mempunyai tepat 1

faktor-1 maka berlaku :

d + 2, jika d adalah ganjil n >

+ 2, jika d adalah genap

Teorema 3 : (Cacetta dan Mardiyono, 1992)

Jika ada himpunan prematur sebenarnya k faktor-1 pada K2n, maka ada

himpunan prematur sebenarnya (2n+k-2t) faktor-1 pada K4n-2t untuk setiap

bilangan bulat t, 0 < t < (k/2).

d23




25

Bukti :

Graf K4n-2t dapat dituliskan sebagai K2n-2t K2n. Andaikan (Fi : i = 1, 2, 3,

…, k) adalah himpunan prematur k faktor-1 pada K2n dengan himpunan titik

(1,2,3,…, 2n) dan komplemennya = ( memuat paling sedikit satu faktor-

1 tetapi tidak memiliki faktorisasi-1). Selanjutnya dipilih 2t himpunan faktor-1

H = (Fs : s = 1,2,3,…,2t) dari k faktor-1 (Fi : i = 1,2,3,…,k) sehingga sisanya

adalah himpunan S = (Fj : j = 1,2,3,…,k-2t). Jika diterapkan lemma 2 pada H

(dengan c = 2n dan k = t) H dapat dikomposisikan menjadi 2n matching

M1,M2,M3,…,M2n masing-masing memuat t sisi.

Kemudian dipilih sembarang himpunan (k-2t) faktor-1, misalnya T = Tj :

j = 1,2,3,…,k-2t) pada K2n-2t dengan himpunan titik (2n+1,2n+2,2n+3,…,4n-

2t) dan komplemennya memuat paling sedikit satu faktor-1. Hal ini selalu

dapat dilakukan karena K2n-2t memiliki faktorisasi-1. Tidak perlu membentuk

himpunan prematur, dengan demikian T dapat memiliki faktorisasi-1.

Jika Vi melambangkan himpunan titik pada K2n yang tidak saturated oleh

matching Mi maka setiap titik dari K2n akan termuat dalam (2n-2t) macam Vi

yang berbeda karena dH (v) =2t. Sedangkan setiap Vi memuat tepat (2n-2t)

titik pada K2n.

Selanjutnya dari graf K2n-2t,2n diperoleh 2n matching yang saling asing,

yaitu N1,N2,N3,…,N2n (Ni menghubungkan titik-titik dari Vi dengan titik-titik

pada K2n-2t). Kemudian dibentuk himpunan 2n faktor-1 Li = Mi Ni,

i=1,2,3…,2n dan perkawanan 1-1 antara himpunan (k-2t) faktor-1 pada S

F F

T




26

dengan himpunan (k-2t) faktor-1 pada T. Hasil perkawanan tersebut adalah

1, 2 , 3 , …, k-2t.

Akhirnya himpunan (Li : i = 1,2,3,…, 2n) ( j : j = 1,2,3,…,k-2t)

membentuk suatu himpunan prematur (2n+k-2t) faktor-1 pada K4n-2t dengan

komplemen . Komplemen ini mempunyai paling sedikit satu faktor-1,

karena baik maupun memiliki paling sedikit satu faktor-1. ( )

tidak memiliki faktorisasi-1 karena memuat yang tidak memiliki

faktorisasi-1.

Terbukti

Corollary 1:

Jika terdapat himpunan prematur k faktor-1; k bilangan genap, dan k>n-1 pada

K2n, maka untuk setiap bilangan genap m, dengan m>4n-k, Km mempunyai

himpunan prematur (m-2n+k) faktor-1.

Bukti :

Corollary diatas dibentuk dari aplikasi Teorema 3 secara berualang-ulang.

Andaikan K2n memiliki himpunan prematur k faktor-1 dan k genap. Maka

Teorema 3 berimplikasi bahwa K4n-2t memiliki himpunan prematur (2n+k-2t)

faktor-1 untuk setiap 0< t < ½ k. Jadi pernyataan adalah benar untuk setiap m,

4n-k < m < 4n. Sekarang anggaplah graf K4n-k memiliki himpunan prematur

2n faktor-1. Dengan mengaplikasikan Teorema 3, dapat disimpulkan bahwa

K8n-2k-2t' memiliki himpunan prematur (6n-k-2t') faktor-1 untuk setiap 0 < t' <n.

Terbukti bahwa k > n-1 berakibat 6n – 2k < 4n + 2.

Terbukti

L

L L L

L

F T

F T F T

F




27




6 bab ii landasan teori a. graf dan unsur-unsurnya suatu graf

Documents