7/26/2019 5-8.doc

1/7

a b c d e

(a) (b)

Gambar 5.1

Diketahui bahwa relasi biner pada Gambar 5.1.a dan Gambar 5.1.b menampilkan hasil

secara umum. Kita amati calon a lebih popular dari calon e karena pasangan (a,b), (b,d), (d,e)

pada R. Satu kemungkinan akan didapat bahwa graik menun!ukkan relasi biner di R pada

gambar 5.1 "ang lebih berguna dalam membandingkan popularitas dua kandidat, karena disana

harus # diurutkan dengan anak panah$ memimpin$ mewakili dari hubungan titik pada calon "ang

lebih popular untuk menghubungkan dengan calon "ang kurang popular.

(1) Gambar %&1 (a) menggambarkan suatu masalah dimana mesin elektrik diharapkan akan

membangun suatu ' keping$ pada tiga pertemuan dimana tiap kawat pada tiga pertemuanlainn"a. asalahn"a, dapatkah ini dilakukan sehingga tidak ada kawat "ang terlewati

Gambar %&1(b) menggambarkan gambar dasar.

**

* ** *

Y1

X3X2

a

b

cd

e

e

dc

b

a

X1

Y2 Y3

7/26/2019 5-8.doc

2/7

Dalam kota Konigsberg ada tu!uh !embatan "ang melewati kota +regel (lihat gambar %&(a)).

ereka menggabungkan dua pulau satu dengan lainn"adan dengan tepi&tepi "ang berlawanan.

Kumpulan !embatan&!embatan ini adalah teka teki berikut- pakah mungkin mengambil !alan

melalui kota, memulai dan berakhir pada tempat "ang sama , dan melewati setiap !embatantertentu sekali

Gambar %& (b) mengilustrasikan gambar dasar.

b sungai

a c

sungai sungai

d(a) (b)Gambar 6-2

(/)+encatatanstatistic industryikan memantau populasi ikan di Gul, e0ico.

Setiap hari memilih titik&titik di Gul dan kemudian mengirim orang&orang keluar dalam kapal

untuk mengambil contoh ikan dan segera pada tiap titik (lihat gambar %&/a). asalahn"aapakah rute terpendek kapal dapat mengambil dan masih melewati setiap titik Gambar %&

/(b) mengilustrasikan gambar dasar.

a

400 350450 e 100 b

400

170 170 100 100

e b d 100 c d c a

(a) (b)Gambar 6-3

a

b

C

d

7/26/2019 5-8.doc

3/7

Gambaran dasar kita membagi dalam beberapa itur. ereka membuat sebuah koleksi dari

titik&titik dan sebuah koleksi dari sisi&sisi "ang menggabungkan pasanngan 2pasangan

tertentu dari titik&titik. 3umlah titik&titik adlah terbatas, sehingga adalah sebuah himpunan

terbatas. 4tu mungkin pertemuan titik&titik dimana, du titik mungkin digabungkan oleh lebihdari satu sisi& oleh karena itu 6 adalah himpunanganda. Sekarang ada dua pertan"aan 2

pertan"aan tentang sisi&sisi. pakah setiap sisi mempun"ai arah pakah kita mengi!inkan

loop&loop(sisi&sisi menggabungkan sebuah titik pada dirin"a) 7ntuk tu!uan pada bab ini,

!awaban dari pertan""an pertama adalah tidak, !awaban pertan"aan kedua adlah "a. 4ni

membimbing kita pada deinisi&deinisi berikut, Sebuah gra, kadang&kadang disebut gra tak

langsung , terdiri dari sebuah himpunan terbatas dari titik&titik dan sebuah himpunan ganda

6 dari sisi&sisi, dimana setiap sisi merupakan sebuah himpunan ganda terdiri dari dua unsurepada . 8itik&titik "ang terdapat dalam sebuah sisi "ang diberikan disebut berhubungan

langsung. 3ika sebuah sisi memuat titik 9, kemudian kita katakan bahwa sisi terbentuk dengan

9 dan 9 adlah sebuah titik akhir dari sebuah sisi. Sisi&sisi ganda dipandang dari "ang lainn"a.

3ika adalah kosong, kemudian kita katakana gra "ang gagal, tapi tu!uan dari buku ini kita

berasumsi bahwa tidak ada gra kita "ang gagal.

+erhatikan G : (,6) dimana : ;a, b, c < dan 6 : ;;a,d

7/26/2019 5-8.doc

4/7

Dari waktu ke waktu, kita mungkin mengatakan tentang perubahan pada sebuah bentuk

gra. 4ni berarti kita mengubah han"a pada satu sisi, bukan titik&titik "ang terbentuk. 8entu kita

mengubah sebuah titik, kemudian kita perlu mengubah sembarang sisi "ang terbentuk. Sebuah

gra dengan tanpa loop dan tanpa sisi ganda disebut gra sederhana. aka dari itu, gra!embatan Konigsberg bukan sederhana. 3ika kita menandai setiap sisi berarah (itu, men!adikan

6 sebuah sisi ganda "ang merupakan pasangan terurut), kemudian kita mempun"ai gra

langsung. 3ika setiap sisi ditandai dengan bobot bilangan riil, maka kita mempun"ai gra

berbobot. Kita akan memperhatikan gra langsung dan berbobot kemudian. +ada titik ini,

pembaca seharusn"a diingatkan terlebih dahulu bahwa tidak ada kesepakatan umum diantara

pencetus&pencetus istilah. Sebagai contoh, apa "ang kita sebut sebuah gra "ang kadang&

kadang disebut grasemu apa "ang kita sebut sebuah gra tanpa loop "ang kadang&kadangdisebut graganda dan kita sebut gra sederhana "ang kadang&kadang disebut gra.

Dalam bela!ar diskrit, harus meneruskan menggunakan gambar&gambar atau diagram

untuk melukis gra seperti sembarang gambar "ang han"a satu dari ban"ak "ang dapat

digunakan untuk men"a!ikan gra. =erdasar deinisi gra mengi!inkan atau memberi peluang

pada kemungkinan dari beberapa sisi menggabungkan pasangan "ang sama dari titik&titik, atau

sebuah sisi "ang menggabungkan sebuah titik pada dirin"a sendiri. 4stilah berikut berguna

ketika mendiskusikan gra.

D6@4A4S4.

Dua atau lebih sisi menggabungkan pasangan "ang sama dari titik&titik "ang disebut sisi&sisi

ganda, dan sebuah sisi "ang menggabungkan sebuah titik pada dirin"a disebut sebuah loop.

Sebuah gra dengan tanpa loop atau sisi ganda disebut sebuah gra sederhana.

D6@4A4S4.Sebuah dalam satu bagian dikatakan terhubung sementara satu "ang membagi dalam beberapa

bagian disebut tidak terhubung.

Deinisi ini diilustrasikan oleh

7/26/2019 5-8.doc

5/7

U z !"

sisi ganda C # G$ % &

' bu*an gra+ seder,ana ang er,ubung gra+seder,ana ida* er,ubung

Diperlukan konsep dari sebuah subgra dari sebuah gra. Suatu hal umum bahwa

keduan"a "aitu matematika dan teknologi mempela!ari ob!ek&ob!ek rumit "ang tampak seperti

ob!ek sederhana di dalamn"a, dan ob!ek kecil ini seringkali diindikasikan dengan prei0 'sub.$

Sebagai contoh lain tentang #sub,B bela!ar subhimpunan dari himpunan, subsistem dari sistem,

subgrup dari grup, dan sebagain"a.

D6@4A4S4. isalkan G sebuah gra dengan himpunan titik&titik (G) dan datar sisi 6(G).

Sebuah subgra dari G adalah sebuah gra "ang mempun"ai titik&titik "ang berada sepan!ang

(G) dan semua "ang sisin"a berada sepan!ang 6 (G).

Sebagai contoh, !ika G dihubungkan dra di atas, dimana

(G) : ;u,9,w,C< dan 6(G) adalah (u9, uw, 99, 9w, wC, wC),

Kemudian gra&gra berikut adalah merupakan semua subgra dari G.

z

U z u %u

U & z

7/26/2019 5-8.doc

6/7

/ & % & z% &

imunan ii* u%&z u%& %z u&z

u%&z !a+ar sisi u& %% %& &z u% u& %& %% u& &z &zu% u& %% %& &z&z

Caaan ba,&a suau subgra+ dari G ,arus naa sebua, gra+ danba,&a G dinaa*an sebagai sebua, subgra+ ada dirina sendiri.

!" 8! 9"#U ::;a' ang berguna unu* memunai sebua, benu* ada

7/26/2019 5-8.doc

7/7

%a'ensi 4 am *sigen memunai %a'ensi 2 dan seia am ,drgenmemunai %a'ensi 1. =es*iun semua enemu mengembang*an e*ni**imia ini mengguna*an %a'ensi *aa ada gra+ *ia se,arusnamengguna*an *aa dera