matematika diskrit

POKOK BAHASAN

PENGERTIAN GRAPH

1.1 DEFINISI GRAPH

Suatu graph teridiri dari suatu himpunana tak kosong yang masing-masing

unsurnya disebut titik (vertex) dan suatu himpunan pasangan tak berurutan dari titik-

titik tersebut yang disebut sisi (edge).

Di sini G melambangkan suatu graph. Himpunan titik di graph G dinyatakan

dengan V(G) dan himpunan sisi di graph G dinyatakan dengan E(G). Jika banyak

titik dan banyak sisi di G terhingga, maka G disebut garaph terhingga. Kita hanya

akan membicarakan graph yang terhingga.

Jika u dan v titik-titik di G dan e = uv suatu sisi di G, maka dikatakan:

e menghubungkan u dan v,

u dan v terhubung langsung (adjacent),

u terkait (incident) dengan e,

e terkait (incident) dengan u,

u dan v disebut titik ujung dari e.

dua sisi atau lebih yang menghubungkan satu pasang titik disebut sisi rangkap

(multiple edges). Suatu sisi yang titik ujungnya sama disebut loop. Graph tanpa sisi

rangkap dan tanpa loop disebut graph sederhana (simple graph).

G H

Gambar 1. 1

Pada Gambar 1, graph G adalah sederhana, dengan

V(G) = {u, v, w, x},

E(G) = {uv, uw, xw, vx, wx},

|V(G)| = 4,

|E(G)| = 5,

Graph H tidak sederhana karena memuat loop dan sisi rangkap.

------------------------------------------------------------Hand Out/ Matematika Diskrit/ tEdy_M - 1

Misalkan G suatu graph dengan himpunan titik V(G) dan himpunan sis E(G).

graph bagian (subgraph) dari G adalah suatu graph yang setiap titiknya adalah

anggota V(G) dan setiap sisinya adalah anggota E(g). Jika H suatu graph bagian dari

G dan V(H) = V(G), maka H disebut graph bagian rentangan (spaninng subgraph)

dari G.

G H1

H2 H3

Gambar 1. 2

Pada Gambar 2, terhadap G, H1 adalah graph bagian rentangan, H2 adalah graph

bagian tetapi bukan graph bagian rentangan, dan H3 bukan graph bagian.

1.2. DERAJAT TITIK

Derajat suatu titik v di G, dinyatakan dengan d(v), adalah banyak sisi G yang

terkait dengan v dengan masing-masing loop dihitung sebagai dua sisi yang terkait

dengan v. Derajat minimum dan derajat maksimum titik-titik di G berturut-turut

dinyatakan dengan (G) dan (G).

Gambar 1. 3

Untuk graph G pada Gambar 3,


d (s) = 3, d (v) = 6, (G) = 0,

d (t) = 3, d (w) =1, (G) = 6.

d (u) = 3, d (x) = 0,

Graph yang semua titiknya berderajat sama disebut graph beraturan (regular

graph). Suatu graph dikatakn beraturan-r (r-reguler) jika setiap titiknya berderajat r.

Pada Gambar 4, G1 beraturan-3 dan G2 beraturan-0.

* *

*

* *

G1 G2

Gambar 1. 4

Pada suatu graph masing-masing sisi bertitik ujung dua, sewaktu derajat titik-

titiknya dijumlahkan masing-masing sisi dihitung dua kali. Maka diperoleh lema

sebagai berikut.

Lema jabat tangan dapat dinyatakan dengan: untuk suatu graph G berlaku:

d(v)=2|E(G)|.

Akibat Lema jabat Tangan.

a) Pada graph, jumlah semua derajat titik adalah genap.

b) Pada graph, banyak titik berderajat ganjil adalah genap.

c) Jika G suatu graph beraturan-r, maka = r

1.3. GRAPH TERHUBUNG

Misalkan titik u dan v (tidak harus berbeda) pada suatu graph G. jalan (walk)

(u,v) di G adalah barisan

voe1v1e2v2 …vn-1envn

dengan vo = u, vn = v, vi adalah titik, ei adalah sisi, dan ei menghubungkan titik


Lema: (Lema Jabat Tangan). Jumlah semua derajat semua titik pada

semua graph sama dengan dua kali banyak sisinya.

v i-1 dan vi, i = 0, 1, 2,…, n. Pada jalan tersebut bilangan n menyatakan panjang jalan.

Kadang-kadang, kalau tidak timbul masalah, jalan tersebut dinyatakan dengan

(u, v) = vo v1 v2 … vn-1 vn.

Lebih lanjut, (u,v) dikatakan menghubungkan u dan v, serta u dan v disebut titik-titik

ujung.

Jalan yang tidak memuat sisi, yang terdiri dari satu titik, disebut jalan trivial.

Jika semua sisi pada suatu jalan berbeda, maka jalan tersebut disebut trail. Jika

semua titik pada suatu jalan berbeda, maka jalan tersebut disebut lintasan (path).

Jalan (u,v) dengan u = v disebut jalan tertutup. Sikel adalah jalan (vo, vo) = v o v 1 v 2

… v n vo dengan n 1 dan vi vj jika i j. suatu sikel dikatakan genap (ganjil)

panjangnya genap (ganjil).

Gambar 1. 5

Pada Gambar 5 v1 v2 v3 v2 v4 v4 adalah jalan; v1 v2 v3 v4 adalah trail yang juga berupa

trail tetutup.

Pada graph juga didefinisikan jarak, radius, diameter, dan titik pusat.

Misalkan G suatu graph. Jarak titik u dan v di G, dinyatakan dengan d(u,v) , adalah

panjang minimum lintasan (u,v) di G. Eksentrisitas(eccenticity) titik v, dinyatakan

dengan e(v), didefinisikan sebagai e(v) = d(u.v). Radius G, dinyatakan

dengan r(G), didefinisikan sebagai r (G) = ; sedangkan diameter G,

dinyatakan dengan d(G), didefinisikan sebagai d (G) = . Suatu titik v

di G disebut sebagai titik pusat jika e(v) = r(G). Sebagai contoh, untuk graph G pada

Gambar 5, d(v1, v5) = 2, e(v1) = 2, e(v2) = 1, r(G) = 1, d(G) = 2, titik v2, v3 dan v4

adalah titik pusat.

Hubungan antara r(G) dan d(G) dinyatakan sebagai berikut.


Graph dikatakan terhubung (connected), jika untuk setiap pasang titik u dan v

di G ada lintasan (u,v) di G; sebaliknya G dikatakan tak terhubung (disconnected).

Komponen dari graph G adalah graph bagian maksimal yang terhubung. Graph

terhubung terdiri dari satu komponen. Suatu komponen dikatakan genap (ganjil) jika

banyak titiknya genap (ganjil).

Perhatikan Gambar 1.12 berikut ini. Graph G1, terhubung; graph G2 tak

terhubung, graph G2 terdiri dari empat komponen, satu komponen genap dan tiga

komponen ganjil.

*

* *

G1 G2

Gambar 1.6

1.4. ISOMORFISME

Graph G1 isomorfik denga graph G2, dinyatakan dengan G1 G2, jika ada

pemetaan yang satu-satu dan pada dari V(G1) ke V(G2) yang melestarikan sifat

keterhubungan langsung, yaitu u dan v di G1 dihubungkan oleh k sisi jika dan hanya

jika (u) dan (v) di G2 dihubungkan oleh k sisi. Untuk graph-graph yang titik-

titiknya tidak bernama, dua graph dikatakan sama jika keduanya isomorfik.

G1 G2

Gambar 1.7

Pada gambar 1.7, G1 G2 karena ada pemetaan

: V(G1) (G2)


Teorema: Untuk setiap graph terhubung g berlaku r(G) d(G) 2 r(G).

t c

u d

v a

w b,

yang satu-satu dan pada serta melestarikan keterhubungan.

1.5. GRAPH DENGAN NAMA TERTENTU

Graph yang hanya terdiri dari satu titik disebut graph trivial (trivial graph).

Graph kosong (empty graph) adalah graph yang tidak mempunyai sisi.

Graph komplit (complete graph) adalah graph sederhana dengan setiap pasang

titik yang berbeda dihubungkan oleh suatu sisi. Graph komplit dengan n titik

dinyatakan dengan Kn. Graph K1, K2, K3 dan K5 ditunjukan pada gambar 1.8.

*

K1 K2 K3 K5

Gambar 1. 8

Graph bipartisi (bipartite graph) adalah graph yang himpunan titiknya dapat

dipisahkan menjadi dua himpunan tak kosong X dan Y sehingga masing-masing sisi

di graph tersebut menghubungkan satu titik di X dan satu titik di Y; X dan Y disebut

himpunan partisi. Sebagai contoh, pada gambar 1.9. G adalah graph bipartisi dengan

himpunan partisi X = {u1, u2, u3 u4} dan Y = {v1, v2, v3, v4, v5).

*

Gambar 1. 9

Graph bipartisi komplit (complete bipartite graph) adlah graph bipartisi dengan

himpunan partisi X dan Y sehingga masing-masing titik di X dihubungkan dengan


masing-masing titik di Y oleh tepat satu sisi, jika = m dan = n, maka graph

bipartisi tersebut dinyatakan dengan Km,n. Graph K1,n disebut bintang. Graph K1,3, K2,3,

dan K3,3 ditunjukan pada Gambar 1.10.

K1,3 K2,3 K3,3

Gambar 1. 10

Graph sikel adalah graph yang terdiri dari satu sikel. Graph lintasan adalah

graph yang terdiri dari satu lintasan. Gambar 1.11 menunjukan contoh tiga graph

sikel dan tiga lintasan.

*

Gambar 1.11

Hutan (forest) adalah graph yang tidak memuat sikel. Hutan yang terhubung

disebut pohon (tree). Pada Gambar 1.12, graph T1 adalah hutan, graph T2 adalah

pohon, yang tentu saja juga berupa hutan.

* *

T1 T2

Gambar 1.12


Ada hubungan antara banyak titik dan banyak sisi pada pohon. Pada Gambar

1.12 terlihat bahwa = - 1. Secara umum, hubungan tersebut di atas

diberikan pada teorema berikut

Misalkan G graph sederhana. Komplemen dari G, dinyatakan dengan , adalah

graph sederhana dengan himpunan titik V( ) = V(G) dan dua titik di terhubung

langsung di G. Gambar 1.13 memperlihatkan graph dan komplemennya.

*

G

Gambar 1.13

Jelas bahwa komplemen dari Kn adalah graph kosong dengan n titik. Oleh

karenanya graph kosong dengan n titik dapat dinyatakan dengan n. graph Kn,

dengan n = 1,2,3, diperlihatkan pada Gambar 1.14.

*

* * * * * * *

K1 K2 K3

Gambar 1.14

Suatu graph G dikatakan komplemen diri (self complementary) jika G.

pada Gambar 1.15, graph H adalah komplemen diri.


Teorema: Misalkan T adalah suatu pohon. Maka = - 1.

1.6. OPERASI PADA GRAPH

Ada banyak catra untuk melakukan operasi pada beberapa graph untuk

menghasilkan suatu graph yang baru . disi akan disampaikan beberapa operasi binar.

Pada definisi berikut ini dianggap G1 dan G2 adalah dua graph dengan V(G1) V(G2)

= .

Graph terhubung G = G1 G2 adalah graph dengan V(G) =V(G1) V(G2) dan

E(G) = E(G1) E(G2). Jika graph G terdiri atas n copy graph H, n 2, maka ditulis G

= nH. Jelas bahwa n = nK1. Gambar 1.15 memperlihatkan graph K3 2K3 K2,3.

Gambar 1.15

Graph join G = G1 + G2 adalah graph dengan V(G) = V(G1) V(G2) dan E(G)

= E(G1) E(G2) {uv: u V(G1) dan v V(G2)}.

Jelas bahwa Km,n = Km + Kn dan Kn = Kn-1 + Kn, n 2. contoh lain diberikan

pada gambar 1.16

G1 K3 G1 + K3

Gambar 1.16

Graph hasil kali cartesius G = G1 x G2 adalah graph dengan V(G) = V(G1) x

V(G2) dan sisi (u1, u2) (v1, v2) E(G) jika dan hanya jika:

U1 = v1 dan u2v2 E(G2)

atau U1 = v1 dan u2v2 E(G2).


Misalkan G suatu graph. Untuk suatu sisi e di G, G – e E(G) – {e}. jembatan

(bridge) pada suatu graph terhubung G adalah sisi e dan G sehingga G-e tak

terhubung. Sebagai contoh, untuk graph pada Gambar 1.17, sisi v1v2 adalah jembatan

dan v5v6 adalah jembatan, sedangkan sisi v4v5 bukan jembatan

Gambar 1.17

Ada berapa sifat yang berhubungan dengan jembatan pada suatu graph yang

perlu kita kemukakan. Sifat tersebut adalah sebagai berikut.

Dari uraian di atas jelas bahwa pohon tidak orientable, dan graph terhubung

yang setiap titiknya berderajat genap adalah orientable karena graph tersebut tidak

memuat jembatan.


Teorema:

a) Setiap sisi pada pohon adalah jembatan.

b) Pada graph terhubung yang tidak memuat jembatan, setiap sisi

termuat dalam suatu sikel.

c) Graph terhubung yang setiap titiknya berderajat genap tidak

memuat jembatan.

Teorema: suatu graph terhubung G adalah orientable jika dan hanya

jika G tidak memuat jembatan.

SOAL LATIHAN

1. Tuliskan himpunan titik dan himpunan sisi dari graph berikut ini.

G H

2. Pada soal no.1, graph mana yang

a. memuat sisi rangkap?

b. memuat loop?

c. sederhana?

d. tidak sederhana?

3. Untuk graph pada soal nomor 1, tuliskan derajat titik-titiknya

4. Pada graph di samping ini temukan:

a. Jalan (u,w) dengan panjang 7

b. Lintasan dengan panjang maksimum

c. Jalan tertutup yang bukan tarail

d. Sikel-sikel dengan panjang 1,2,3, dan 4,

5. Apakah dua graph berikut ini isomorfik? Jelakan

G H

6. Pada soal nomor 4, ada berapa lintasan (v,x)?

7. Gambarlah graph

a. K1,3 K2,2

b. K1,3 + K2,2

c. K1,3 x K2,2


POKOK BAHASAN

GRAPH EULER DAN GRAPH HAMILTON

2.1. DEFINISI

Misalkan G suatu graph. Trail Euler pada G adalah trail yang memuat setiap

sisi di G. Graph G di sebut Graph Euler (Eulerian ) jika G memuat trail Euler yang

tertutup. Sikel Hamilton G adalah sikel yang memuat setiap titik di G. Graph G di

sebut Graph Hamilton (Hamiltonian) jika G memuat sikel Hamilton. Lintasan

Hamilton di G adalah lintasan yang memuat setiap titik di G. Perhatikan graph pada

gambar 2.1 berikut ini:

G1 G2 G3

Gambar 2.1

Terlihat bahwa :

uvywxyuxz adalah trail Euler(tidak tertutup ) di G1’

uyvwyxu adalah trail Euler tertutup di G2’

uvywxz adalah lintasan Hamilton di G1’ dan

uvwxyu adalah sikel Hamilton di G3.

Dapat diperika bahwa :

G1 bukan Graph Euler dan bukan Graph Hamilton,

G2 Graph Euler tetapi bukan Graph Hamilton dan

G3 adalah graph Euler yang juga graph Hamilton


Teorema: Misalkan G suatu graph terhubung. Maka G adalah graph Euler jika

hanya jika setiap titik di G berderajat genap.

Berikut ini adalah algoritma Fleury untuk mencari suatu trail Euler tertutup

pada suatu graph Euler.

Algoritma Fleury. Misalkan G graph Euler. Langkah-langkah berikut ini akan

menghasilkan suatu trail tertutup di G.

1. Misalkan i = 0 dan pilih sembarang titik v0 di G dan definisikan T0 = V0

2. Trail Ti = v0e1v1e2…ei vi sudah dihasilkan. Pilih suatu sisi e i+1 di E(G) –

{e1,e2,…,e1} dengan syarat

a. ei +1 terkait dengan vi

b. ei+1 bukan jembatan pada G -{e1,e2 …, e1} kecuali tidak ada pilihan lain.

Jika tidak ada sisi ei+1 yang memenuhi, maka stop.

3. Definisikan Ti+1 = v0 e1 v1 e2…ei +1 vi +1 dengan ei +1 =vi vi +1.

4. Ganti i dengan i + 1 dan kembali ke langkah 2.

Jaminan bahwa algoritme Fleury menghasilkan suatu trail Euler tertutup pada

suatu graph Euler diberikan oleh teorema berikut:

Perhatikan graph G berikut ini.

Gambar 2.2

Dengan menggunakan Algoritma Fleury dapat ditemukan suatu trail Euler

tertutup di G misalnya v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v10 v8 v11 v9 v7 v5 v2 v4 v6 v3 v1.

Suatu graph terhubung yang bukan graph Euler (tidak memuat trail Euler

tertutup) mungkin memuat trail Euler tidak tertutup. Berikut ini syarat cukup dan

perlu agar graph terhubung memuat trail Euler tidak tertutup.


Teorema: Sembarang trail yang terbentuk dengan algoritme Fleury pada suatu

graph Euler adalah trail Euler tertutup.

Contoh: carilah trail Euler pada graph berikut ini.

Gambar 2.3

Jawab:Trail Eulernya vwxyzuvxuy

Selanjutnyaakan disampaikan syarat cukup agar suatu graph adalah graph

Hamilton. Pada kedua teorema berikut, teorema Ore lebih kuat dari teorema Dirac.

Teorema Ore adalah generalisasi dari Teorema Dirac, karena jika untuk setiap v

V(G) berlaku d(v) ½ n, (syarat cukup teorema Dirac), maka untuk semua u, v

V(G), berlaku d(u) + d(u) n (syarat cukup Teorema Ore). Oleh karenanya cukup

dibuktikan teorema Ore.


Teorema: Misalkan G suatu graph terhubung.maka G memuat trail Eurel tidak

tertutup jika dan hanya jika G memuat dua dan hanya dua titik berderajat

ganjil. Lebih lanjut, setiap titik berderajat ganjil tersebut merupakan titik ujung

trail Eurelnya.

Teorema: (Direc). Misalkan G suatu graph sederhana dengan n titik,n 3.jika d(v) ½ n untuk setiap v V (G), maka G adalah graph Hamilton.

Teorema: (Ore). Misalkan G suatu graph sederhana dengan n titik, n 3. Jika

d(u) + d(v) n untuk setiap titik u dan v yang berlainan dan tidak terhubung

langsung di G, maka G adalah graph Hamilton.

2.2. GRAPH BERMUATAN

Seorang tukang pos akan mengantar surat ke jalan-jalan yang menjadi

daerahnya dan harus kembali ke kantor pos. Bagaimana rutenya agar jalan yang

ditempuh terpendek? Problem tersebut terkenal dengan nama problem pak pos cina

(chinese postman problem)

Untuk menjawab permasalahan ini dapat di buat model graphnya sebagai

berikut. Persimpangan jalan dinyatakan dengan titik, jalan dinyatakan dengan sisi,

dan setiap sisi di beri muatan yang dapat menyatakan panjang jalan. Graphnya

disebut graph bermuatan. lebih formal didefinisikan sebagai berikut. Graph

bermuatan (weighted graph) adalah graph yang setiap sisinya diberi muatan atau

nilai. Graph yang tidak bermuatan dianggap setiap sisi bermuatan 1.

Dengan defenisi tersebut, problem pak pos cina dapat dinyatakan menjadi:

Pada suatu graph bermuatan, temukan suatu jalan tertutup yang memuat setiap sisi

dan dengan jumlah muatan minimum (terpendek).

Problem tersebut mudah diselesaikan jika setiap titiknya berderajat genap.jika

tidak, setiap titik harus dibuat berderajat genap, beberapa sisi dibuat rangkapnya

dengan syarat jumlah muatannya minimum.

Contoh: Pada graph G berikut ini, temukan suatu jalan tertutup yang memuat setiap

sisi dan dengan jumlah muatan minimum.

Gambar 2. 4

Jawab: Untuk mencari jalan tertutup terpendek yang memuat setiap sisi dan dengan

jumlah muatan minimum pada graph G, sisi uv, ux, dan sisi yx perlu dibuat rangkap

(jelaskan alasan nya). Salah satu jalan yang dicari adalah uvuxuyxvwxyzu.


SOAL LATIHAN

1. Dari graph-graph berikut ini manakah yang merupakan graph Euler atau graph

Hamilton? Jelaskan

2. Untuk graph-graph pada soal no.1, graph mana saja yang memuat trail Euler?

3. Carilah jalan terpendek (dengan jumlah muatan minimum) dan tertutup untuk

graph-graph berikut ini:

G1 G2


POKOK BAHASAN

KESEBIDANGAN GRAPH

3.1. GRAPH PLANAR

Suatu graph dapat digambarkan dengan beberapa cara. Sebagai contoh, graph

komplit K4, graph bipartit komplit K3,3, Dan graph Petersen dapat digambarkan

seperti pada gambar 4.1 kadang-kadang

Atau atau

K4 K3,3

atau

Graph Petersen

Gambar 3.1

Kadang-kadang kita memerlukan menggambar graph dengan tidak ada dua sisi

yang saling “berpotongan” seperti gambar K4 yang sebelah kanan pada gambar 3.1.

Sayangnya, penggambaran tersebut belum tentu dapat dilakukan. Kita akan

membicarakan permasalah ini.

Suatu graph G dikatakan planar jika dapat digambar dalam suatu bidang

tanpa ada dua sisi saling bertemu kecuali pada simpul persekutuan, gambar tersebut

disebut gambar bidang untuk G. Sebagai contoh, graph K4 adalah planar, ada lebih

dari satu gambar bidang untuk K4, seperti pada gambar 3.2. Sebaliknya,graph bipartit

komplit K3,3 tidak planar karena setiap gambar K3,3 pasti memuat paling sedikit satu

perpotongan sisi. Hal ini dapat di tunjukan sebagai berikut. Graph K3,3 memuat suatu

cycle dengan panjang 6, sebutlah axbzcya yang harus muncul pada gambar dalam

bentuk segi enam,lihat gambar 4.3. masih perlu ditambah tiga sisi az, xz, dan by.


Gambar untuk bidang K4

Gambar 3.2

Gambar 3.3

Agar tidak ada perpotongan sisi, tidak lebih satu dari dari ketiga sisi tersebut

yang dapat digambar didalam (diluar) segi enam, lihat gambar 3.4. Akibatnya tidak

mungkin menambahkan tiga sisi az, xz, dan by tanpa menimbulkan perpotongan sisi.

Dengan cara seperti di atas dapat ditunjukan bahwa K5 tidak planar

Gambar 3.4

3.2. RUMUS EULER

Jika G adalah graph planar, maka semua gambar bidang untuk graph G

mungkin membagi bidang menjadi beberapa daerah, satu dari daerah ini daerah tidak

terhingga. Jika w adalah suatu daerah, maka derajat dari w, dinyatakan dengan d(w),

adalah banyak sisi pada jalan tertutupnya mengililinginya. Jika semua daerah

mempunyai daerah yang sama, misalnya g, maka G dikatakan beraturan daerah

dengan derajat g. Sebagai contoh gambar untuk graph komplit K4 mempunyai empat

daerah yang masing-masing berderajat 3. sedangkan graph pada gambar 3.5

mempumyai lima daerah w1, w2, w3, w4, dan w5 dengan d(w1) = 9,d(w2) = 9, d(w3) =

3, d(w4) = 9, dan d(w5) = 4.


Gambar 3.5

Perhatikan bahwa, pada gambar bidang graph planar, jumlah semua derajat

daerah sama dengan dua kali banyak sisi. Hal ini di sebabkan karena pada waktu

menjumlah semua derajat setiap sisi dihitung dua kali. Hasil ini dapat dipandang

sebagai lema jabat tangan untuk graph planar.

Pada gambar bidang graph planar yang terhubung antara banyak titik, banyak

sisi dan banyak daerah. Hubungan tersebut seperti pada teorema berikut.


Teorema: (Rumus Euler). Misalkan G adalah graph planar terhubung n,m dan f berturut-turut menyatakan banyak titik, banyak sisi, dan banyak daerah pada gambar bidang untuk graph G. Maka n - m + f = 2.

SOAL LATIHAN

Dengan menggambar gambar bidangnya, tunjukkan bahwa graph berikut ini adalah

planar.

1. 2.

3.


POKOK BAHASAN

PEWARNAAN GRAPH

4.1. PEWARNAAN TITIK

Akan membicarakan permasalahan yang berhubungan dengan pewarnaan titik.

Masalah tersebut erat kaitannya dengan masalah pewarnaan peta, yaitu masalah

menentukan banyak warna minimum yang diperlukan untuk mewarnai peta sehingga

dua daerah yang bertetangga mempunyai warna yang berlainan.

Misalkan G graph tanpa loop. Suatu pewarnaan –k untuk graph G adalah

suatu penggunaan sebagian atau semua k warna untuk mewarnai semua titik di G

sehingga setiap pasang titik yang terhubung langsung diberi warna yang berbeda.

Jika G mempunyai pewarnaan-k, maka G dikatakan dapat diwarnai dengan k warna.

Bilangan khromatik (chromatic number) dari graph G, dinyatakan dengan

(G), adalah bilangan k terkecil sehingga G dapat diwarnai dengan k warna. Biasanya

warna-warna yang digunakan untuk mewarnai graph dinyatakan dengan 1, 2, 3,…, k.

Jelas bahwa (G) |v(G)|. Sedangkan cara yang mudah untuk menentukan batas

bawah dari (G) adalah dengan mencari graph bagian komplit yang terbesar di G.

Contoh: Perhatikan gambar 4.1 untuk graph G1, karena |v(G1)| = 3, maka (G1)

3. untuk G2, karena |v(G2)| = 4, maka (G2) 4. Sedangkan semua titik pada G1

atau G2 saling terhubung langsung, akibatnya (G1) 3 dan (G2) 4. jadi (G1) =

3 dan (G2) = 4. Untuk graph G3, (G3) 3 karena 3 warna cukup untuk

mewarnainya seperti pada gambar. Karena G3 memuat graph komplit K3, maka

(G3) 3. akibatnya (G3) = 3.

G1 G2 G3

Gambar 4.1

Pada definisi di atas kita hanya memperhatikan graph tanpa loop, sebab dua

titik yang terhubung langsung (adjacent) harus diberi warna yang berlainan,

sedangkan pada loop suatu titik terhubung langsung ke dirinya sendiri, tidak

mungkin satu titik di beri dua warna yang berlainan. Perhatian kita dapat di batasi


pada graph tanpa sisi rangkap, sebab ada sisi rangkap atau sisi bukan rangkap yang

menghubungkan dua titik tidak mempengaruhi bilangan khromatik.

Batas atas (G) di atas tidak begitu baik, ada batas yang lebih bagus, seperti

pada teorema berikut ini:

4.2. SUKU BANYAK KROMATIK

Pada pembahasan sebelumnya, terlihat bahwa batas atas dan batas bawah yang

kita bicarakan tidak selalu memberikan perkiraan yang baik untuk bilangan

khromatik. Akan dibahas suatu cara untuk menentukan bilangan khromatik suatu

graph. Cara ini melibatkan pengertian suku banyak khromatik yang di definisikan

sebagai berikut. Misalkan G suatu graph sederhana. Suku banyak khromatik

(chromatic polynomial) dari graph G, dinyatakan dengan PG (k), adalah banyak cara

pewarnaan-k untuk graph G.

Sebagai contoh, perhatikan gambar 4.2. graph komplit K3 akan diwarnai

dengan k warna. Titik pertama dapat di warnai dengan k cara, titik kedua dapat di

warnai dengan k-1 cara, dan titik ketiga dapat diwarnai dengan k-2 cara. Akibatnya

K3 dapat diwarnai dengan k((k-1) (k-2) cara atau PK3 (k) = k(k-1) (k-2).

K3 G

Gambar 4.2

Graph G akan diwarnai dengan k warna. Titik pertama dapat diwarnai dengan k

cara, titik ke dua dapat diwarnai dengan k-1 cara, dan titik ke tiga dapat diwarnai

dengan k-1 cara. Akibatnya G dapat diwarnai dengan k(k-1) (k-1) cara, atau PG (k) =

k(k-1) (k-1) = k(k-1) = k (k-1)2

Dengan cara seperti di atas, mudah di pahami bahwa untuk sembarang pohon T

dengan n titik berlaku


Teorema: Jika G graph sederhana dengan derajat titik maksimum

maka (G) + 1.

PT(k) = k(k-1)n-1.

4.3. PEWARNAAN SISI

Misalkan G graph tanpa loop. Suatu pewarnaan –sisi-k untuk graph G adalah

suatu penggunaan sebagian atau semua k warna untuk mewarnai semua sisi di G

sehingga setiap pasang sisi yang mempunyai titik persekutuan diberi warna yang

berbeda. Jika G mempunyai pewarnaan –sisi-k, maka dikatakan sisi-sisi di G

diwarnai dengan k warna.

Indeks khromatik (chromatic index) dari graph G, di nyatakan dengan ’(G),

adalah bilangan k terkecil sehingga sisi di G dapat diwarnai dengan k warna.

Biasanya warna-warna yang digunakan untuk mewarnai sisi-sisi suatu graph

dinyatakan dengan 1, 2, 3,…, k. Jelas bahwa ’(G) |E(G)|, dan jika derajat titik

maksimum di G adalah (G), maka ’(G) (G). Untuk graph cycle dengan n titik

, sebutlah Cn, jelas bahwa ’(Cn) = 2 untuk n genap dan ’(Cn) = 3 untuk n ganjil.

Contoh: Tentukan indeks khromatik untuk graph pada gambar 4.3

G1 G2 G3

Gambar 4.3

Jawab: Perhatikan gambar 4.4. Untuk graph G1, jelas bahwa ’(G1) = 3.

Untuk G2, ’(G2) 3 karena (G2) = 3, dan ’(G2) 3 karena sisi-sisi di G2 dapat

diwarnai dengan 3 warna seperti pada gambar. Akibatnya ’(G2 ) = 3. Untuk G3,

’(G) 4 karena (G3) = 4, dan (G3) 4 karena sisi-sisi di G2 dapat di warnai

dengan 4 warna seperti pada gambar. Akibatnya (G3 ) = 3.


G1 G2 G3

Gambar 4.4

Seperti pada pewarnaan titik, definisi di atas hanya untuk graph dengan tanpa

loop. Tetapi disini kita juga memperhatikan ggraph dengan sisi rangkap. Selanjutnya

jelas bahwa jika adalah derajat titik maksimum di G, maka ’(G) .juga jelas

bahwa (G) |E(G)|


SOAL LATIHAN

1. Warnailah graph berikut ini dengan empat warna sehingga tidak ada dua titik

terhubung langsung yang berwarna sama

(a) (b)

G H

2. Tentukan bilangan khromatik (G) dari graph berikut ini. Jelaskan jawab anda.

(a) (b)


POKOK BAHASAN

FUNGSI PEMBANGKIT

Suatu permasalahan persamaan pada himpunan bilangan bulat

mempertanyakan, ada beberapa banyak selesaian dari

X + X + … + X = r

Dengan persyaratan tertentu pada Xi.

Contoh: Tentukan banyak selesaian bulat dari X + X = r, dengan 0 X 2 dan 1

X 2.

Jawab: X1 : X2 : r

0 : 1 : 1

0 : 2 : 2

1 : 1 : 2

1 : 2 : 3

2 : 1 : 3

2 : 2 : 4

Dari daftar di atas terlihat bahwa: ada satu cara untuk mendapatkan jumlah 1,

ada dua cara untuk mendapatkan jumlah 2, ada dua cara untuk mendapatkan jumlah

3, dan ada satu cara untuk mendapatkan jumlah 4.

Cara penyelesaian seperti di atas adalah sangat sederhana tetapi dapat menjadi

sangat panjang. Cara tersebut dapat dipersingkat dengan memperhatikan dan

menghitung banyak pengerjaan yang menghasilkan jumlah yang sama. Kita

perhatikan contoh berikut ini.

Contoh: Kalikan (x 0 + x + x ) dengan (x + x ).

Jawab: Dengan menggunakan sifat distributif dan kemudian suku-suku dengan

pangkat dari x yang sama dikumpulkan. diperoleh.

(x + x + x ) (x + x ) = x + 2x + 2x + x .

Dari dua contoh di atas terlihat bahwa koofisien x pada (x + x + x ) (x + x

) adalah banyak selesaian bulat dari X + X = r, dengan 0 X 2 dan 1 X 2.

Berikut ini adalah contoh yang lain.

Contoh: Banyak selesaian bulat tidak negative dari X + X = r adalah r +1, yaitu

X = 0 dan X = r,


X = 1 dan X = r - 1,

X = 2 dan X = r – 1,

…

X = r dan X = 0.

Sekarang perhatikan (x + x + x + …) ( x + x + x + …). Koofisien dari x

pada perkalian tersebut adalah banyak selesaian bulat dari persamaan X + X = r di

atas, yaitu x diperoleh dari x di faktor pertama dan x di faktor kedua,

di faktor pertama dan x di faktor kedua,

di faktor pertama dan x di faktor kedua,

…

xr di faktor pertama dan x di faktor kedua.

Akibatnya

(x + x + x + …) (x + x + x + …) = x + 2x + 3x + …

Dengan alasan seperti pada contoh di atas diperoleh bahwa banyak selesaian

bulat dari

X + X + X + …+ Xn = r

Dengan X = b , b , b , … adalah koofisien x pada ( + + +

…) ( + + + …)….

( + + + …).

Uraian ini mengilhami definisi berikut ini.


Definisi:.

a. Suatu deret kuasa formal (formal power series) adalah suatu ekspresi dalam bentuk

a + a + a 2 + …,

a adalah koofisien ke i, i = 1, 2, 3, …

b. Identitas konvolusi (convolution identity); perkalian

(a + a +a + …) (b + b + b + …)

didefinisikan dengan penerapan

+ + …+

sebagai koofisien dari x .

c. Penjumlahan

(a + a +a + …) + (b + b + b + …)

didefinisikan dengan penerapan a + b sebagai koefisien dari x .

Mudah ditunjukkan bahwa pada definisi perkalian dan penjumlahan di atas

berlaku sifat komutatif, asosiatif, distributif dan sifat-sifat sederhana yang lain.

Biasanya x dinyatakan dengan 1, x dinyatakan dengan x, 1x dinyatakan dengan x

, dan suku dengan faktor 0 tidak ditulis.

Contoh: Kalikan dan jumlahkan

1 + 2x dengan x + 2x + 3x + …

Jawab: (1 +2x) (x + 2x + 3x + …)

= x + (2+2)x + (3 + 4)x + …+ (r + 2(r + 2(r – 1)) +…

= x + 4x + 7x + … + (3r – 2)x + … , dan

(1 + 2x) + (x + 2x + 3x + …) = 1+ 3x + 2x + 3x +

4x + …

Kita telah membicarakan polinom dan deret kuasa dengan koefisien x

merupakan selesaian dari suatu permasalahan kombinatorik. Dengan memperhatikan

hal itu kemudian dibuat definisi berikut ini.

Definisi: Misalkan ar adalah suatu selesaian dari suatu permasalahan kombinatorika,

r = 1, 2, 3, … . Maka fungsi pembangkit dari selesaian tersebut adalah

g(x) = a + a x + a x + a x + …

juga dikatakan bahwa g(x) adalah fungsi pembangkit dari barisan a , a , a , …

Contoh: Perhatikan permasalahan mencari banyak selesaian bulat dari X1 + X2

= r, dengan 0 X 2 dan 1 X 2. Jika ar adalah banyak selesaiannya, maka a


= 1, a = 1, a = 2, a = 2, a = 1, dan a = 0 untuk r 5. Jadi fungsi pembangkit

dari permasalahan tersebut adalah

0 + 1x + 2x + 2x + x + 0x + 0x + …

= x + 2x + 2x + x

= (1 + x + x ) (x + x ).

Contoh: Tentukan fungsi pembangkit dari banyak combinari-r obyek yang

diambil dari n obyek.

Jawab. Fungsi pembnagkitnya adalah

1 + x + + + … = (1 + x)

Contoh: Tentukan fungsi pembangkit dari banyak banyak selesaian bulat dari X

+ 2X + 2X + 5X = r, dengan X 0.

Jawab. Misalkan Y = X , Y = 2X , Y = 2X, dan Y = 5X .

Maka Y + Y + Y + Y = r,

Dengan Y = 0, 1, 2, 3, …,

Y = 0, 2, 4, 6, …,

Y = 0, 2, 4, 6, …,

dan Y = 0, 5, 10, 15, ..,

Fungsi pembangkitnya adalah

(1 + X + X + X +…) (1 + X + X + X +…) 2 (1 + X + X + X +…)

Contoh: Tentukan fungsi pembangkit pada permasalahan menentukan banyak

cara pengelompokan 12 bola yang identik menjadi tiga kelompok yang masing-

masing berisi sebanyak genap bola (setiap kelompok tidak boleh kosong.

Jawab. Persamaan bilangan bulat yang sesuai adalah X1+X2+X3 =12 dengan X1

= 2,4,6,8,…, fungsi pembangkitannya adalah (X2+X4+X6+X8+…)3.

Contoh: Tentukan fungsi pembangkit dari banyak selesaian bulat dari

X1+X2+X3+…+Xn r, dengan 1 Xk 4.

Jawab. Persamaan X1+X2+X3+…+Xn r dengan Xk 4. ekivalen dengan

X1+X2+X3+…+Xn +Xn+1 = r dengan 1 Xk 4 untuk 1 k 4, dan Xn+1 0.

sehingga fungsi pembangkitnya adalah

(x + x (1+X+X2+X3+…).


Contoh: Tentukan fungsi pembangkit dari banyak memilih empat bilangan

berbeda pada 1,2,3,4, …,n tanpa ada dua bilangan berurutan.

Jawab. Misalkan bilangan-bilangan yang pilih adalah b1,b2,b3 dan b4, dengan 1

b1 < b2 < b3 < b4 n. misalkan X1 = b1 X2 = b2-b1, X3 = b3-b2, X4 = b4-b3, X5 = n-b4.

karena tidak ada dua bilangan berurutan,maka X1 2 untuk 2 i 4. persamaan

bilangan bulat yang sesuai adalah

X + X +X + X + X = n

dengan X 1, X 2, dan X 0. Fungsi pembangkitnya adalah (x + x + x

+ …) (x + x + x + …) (1 + x + x + x + …)


SOAL LATIHAN

1. Tentukan fungsi pembangkit dari

a) barisan a, a, a, a, …

b) 1, a, a , a , …

c) Banyak barisan binar yang memuat r unsur

2. Dengan menggunakan definisi lakukanlah perkalian berikut ini.

a) (1 + x + x + x + …) (1 + 2x + 4x + 6x + …)

b) (x + x + x 5 + …) (1 + 2x + 4x + 6x + …)


matematika diskrit

Documents

Transcript of matematika diskrit