modul 1. pengetahuan dasar teori graf (1x pert)

8/18/2019 Modul 1. Pengetahuan Dasar Teori Graf (1x Pert)

1/33

Pengetahuan Dasar Teori Graf

Prof. Dr. H. Didi Suryadi, M.Ed.Prof. Dr. H. Nanang Priatna, M.Pd.

ada bagian ini Anda akan mempelajari sejarah singkat perkembangan

teori graf serta beberapa pengertian dasar teori graf mencakup definisi

teori graf; graf hingga dan graf tak hingga; insidensi dan ajasensi; titik

(simpul) terisolasi, titik anting, serta derajat suatu titik. Setelah Anda

mengenal beberapa pengertian teori graf, selanjutnya akan disajikan materi

graf sebagai model matematika dan aplikasinya yang mencakup graf sebagai

model matematika, graf berarah sebagai model matematika, jaringan kerja,

silsilah keluarga, sistem komunikasi, jaringan transportasi, desain arsitektur,dan ikatan kimia.

P

Mengingat materi yang akan Anda pelajari ini merupakan landasan

utama dalam mempelajari modul-modul berikutnya, maka pemahaman yang

baik tentang materi yang disajikan merupakan langkah yang tepat dalam

upaya memahami materi setiap modul secara keseluruhan.

Setelah mempelajari modul ini Anda diharapkan mengenal sejarah

singkat munculnya teori graf, beberapa pengertian dasar teori graf, serta

aplikasi teori graf.

Setelah mempelajari modul ini, secara khusus Anda diharapkan mampu

!. menjelaskan sejarah perkembangan teori graf;

". menjelaskan beberapa pengertian dasar teori graf;

#. menggambar graf sebagai model matematika.

PENDAHULUAN


2/33

Kegiatan Belajar 1

Sejarah Singkat dan BeberapaPengertian Dasar Teori Graf

A. SEJARAH SINGKAT TEORI GRAF

$eori graf lahir pada $ahun !%#& melalui tulisan 'uler yang berisi

tentang upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal

di 'ropa. urang lebih seratus tahun setelah lahirnya tulisan 'uler tersebuttidak ada perkembangan yang berarti berkenaan dengan teori graf.

$ahun !*%, +.. irchoff (!"* !%) berhasil mengembangkan teori

pohon (Theory of trees) yang digunakan dalam persoalan jaringan listrik.

Sepuluh tahun kemudian, A. oyley (!"! !/0) juga menggunakan

konsep pohon untuk menjelaskan permasalahan kimia yaitu hidrokarbon.

1ada masa irchoff dan oyley juga telah lahir dua hal penting dalam

teori graf. Salah satunya berkenaan dengan konjektur empat warna, yang

menyatakan bah2a untuk me2arnai sebuah atlas cukup denganmenggunakan empat macam 2arna sedemikian hingga tiap negara yang

berbatasan akan memiliki 2arna yang berbeda.

1ara ahli teori graf berkeyakinan bah2a orang yang pertama kali

mengemukakan masalah empat 2arna adalah A.3. Mobius (!%/4 !&)

dalam salah satu kuliahnya di $ahun !*4. Sepuluh tahun kemudian, A. 5e

Morgan (!4& !%!) kembali membahas masalah ini bersama ahli-ahli

matematika lainnya di kota 6ondon. 5engan demikian tulisan 5e Morgan

dianggap sebagai referensi pertama berkenaan dengan masalah empat 2arna.Masalah empat 2arna ini menjadi sangat terkenal setelah oyley

mempublikasikannya $ahun !%/ dalam Proceedings of the Royal

Geographic Society 7olume pertama.

8al lain yang penting untuk dibicarakan sehubungan dengan

perkembangan teori graf adalah apa yang dikemukakan oleh Sir 9..

8amilton (!40 !&0). 1ada $ahun !0/ dia berhasil menemukan suatu

permainan yang kemudian dijualnya ke sebuah pabrik mainan di 5ublin.

1ermainan tersebut terbuat dari kayu berbentuk dodecahedron beraturanyakni berupa sebuah polihedron dengan !" muka dan "4 pojok. $iap muka

berbentuk sebuah pentagon beraturan dan tiap pojoknya dibentuk oleh tiga


3/33

sisi berbeda. $iap pojok dari dodecahedron tersebut dipasangkan dengan

sebuah kota terkenal seperti 6ondon, :e2 ork, 1aris, dan lain-lain. Masalah

dalam permainan ini adalah, kita diminta untuk mencari suatu rute melaluisisi-sisi dari dodecahedron sehingga tiap kota dari "4 kota yang ada dapat

dilalui tepat satu kali. 9alaupun saat ini masalah tersebut dapat dikategorikan

mudah, akan tetapi pada saat itu tidak ada seorang pun yang bisa menemukan

syarat perlu dan cukup dari eksistensi rute yang dicari.

urang lebih setengah abad setelah masa 8amilton, akti7itas dalam

bidang teori graf dapat dikatakan relatif kecil. 1ada $ahun !/"4-an kegiatan

tersebut muncul kembali yang dipelopori oleh 5. onig. onig berupaya

mengumpulkan hasil-hasil pemikiran para ahli matematika tentang teori graf termasuk hasil pemikirannya sendiri, kemudian dikemasnya dalam bentuk

buku yang diterbitkan pada $ahun !/#&. @7!, 7

", ... yang disebut himpunan titik, dan

sebuah himpunan lain ' > @e!, e

", ... yang merupakan himpunan sisi

sedemikian hingga tiap sisi ek dikaitkan dengan suatu pasangan tak terurut(7

i, 7

j). $itik 7

i, 7

j yang berkaitan dengan e

k disebut titik-titik ujung sisi e

k .

ara merepresentasikan sebuah graf yang paling umum adalah berupa

diagram. 5alam diagram tersebut, titik-titik dinyatakan sebagai noktah dan

tiap sisi dinyatakan sebagai segmen garis yang menghubungkan tiap dua titik.

Bntuk lebih jelasnya perhatikan contoh graf pada +ambar !.! di ba2ah ini.


4/33

Gabar !.!.Graf dengan "ia titik dan tujuh sisi

5alam sebuah graf, seperti terlihat pada contoh di atas, dimungkinkan

adanya suatu sisi yang dikaitkan dengan pasangan (7!, 7

"). Sisi yang dua titik

ujungnya sama disebut loop. 5alam graf pada +ambar !.!, e! merupakan

sebuah loop. 5ari contoh di atas juga perlu dicatat bah2a dalam sebuah graf

dimungkinkan adanya lebih dari satu sisi yang dikaitkan dengan sepasang

titik. Sebagai contoh, e* dan e

0 pada graf di atas dikaitkan dengan pasangan

titik (7!, 7

#). 1asangan sisi semacam ini disebut sisi-sisi paralel atau sejajar .

Sebuah graf yang tidak memiliki loop dan sisi paralel disebut graf

sederhana. 5alam beberapa literatur teori graf, pembahasan hanya dibatasi

pada graf sederhana, akan tetapi dalam banyak aplikasi teknik, penggunaan

loop dan sisi paralel sangat diperlukan. Bntuk membedakan antara graf yang

memuat loop dan sisi paralel dengan graf yang tidak memuat kedua hal

tersebut, sebagian penulis menggunakan istilah graf sederhana untuk graf

yang tidak memuat loop dan sisi paralel, serta graf umum untuk yang lainnya.

5alam sebuah graf mungkin terdapat dua sisi atau lebih yang

menghubungkan dua titik yang berlainan. edua sisi tersebut dinamakan sisi

rangkap atau sisi ganda. +raf yang mengandung loop atau sisi rangkap

dinamakan graf ganda.

ontoh

5alam menggambar sebuah graf, bentuk sisi dapat berupa garis lurus

atau garis lengkung. 5emikian pula ukurannya, dalam penggambaran sebuah

Graf Sederhana Graf Tak SederhanaGabar !.#


5/33

graf tidaklah diperhatikan. 8al yang penting untuk diperhatikan dalam

sebuah graf adalah insidensi antara titik-titik dengan sisi-sisinya. Sebagai

contoh, dua graf yang disajikan pada +ambar !.# di ba2ah inimenggambarkan graf yang sama, karena insidensi antara sisi-sisi dan titik-

titik pada graf tersebut adalah sama.

Gabar !.$.Graf yang saa

Sekarang perhatikan +ambar !.* di ba2ah ini. 1ada gambar tersebut

sisi e dan f nampaknya seperti berpotongan, akan tetapi perpotongannya tidak

berupa titik. edua sisi seperti itu harus dipandang sebagai dua ruas garis

yang terletak pada dua bidang berbeda, sehingga kedua sisi itu tidak

berpotongan.

Gabar !.%.Sisi e dan f tidak berpotongan

C. GRAF HINGGA DAN GRAF TAK HINGGA


6/33

9alaupun dalam definisi graf tidak disebutkan secara eksplisit bah2a

himpunan titik ? dan himpunan sisi ' tidak perlu merupakan sebuah

himpunan hingga, akan tetapi dalam kebanyakan aplikasi teori graf keduahimpunannya tersebut kebanyakan merupakan himpunan hingga. Sebuah graf

+ > (?, ') dengan ? dan ' hingga disebut graf hingga atau graf terhingga

dan jika sebaliknya yakni jika ? dan ' tak hingga, maka + disebut graf tak

hingga. ontoh graf hingga dapat dilihat pada +ambar !.!, +ambar !.",

+ambar !.# dan +ambar !.*. Sedangkan +ambar !.0 di ba2ah ini merupakan

contoh dari bagian graf tak hingga.

Gabar !.&.Bagian dari graf tak hingga

Bntuk pembahasan selanjutnya, yang dimaksud dengan graf dalam

modul ini adalah graf hingga.

D. INSIDENSI DAN AJASENSI

Cika sebuah titik 7! merupakan titik ujung dari suatu sisi e

j , maka 7

! dan

e j disebut saling berinsidensi atau titik 7

! insiden dengan sisi e

j. Sebagai

contoh, pada +ambar !.! di atas sisi e", e

&, dan e

% adalah sisi-sisi yang insiden

dengan titik 7*. 5ua sisi yang tidak paralel disebut ajasen, bila kedua sisi

tersebut insiden dengan titik yang sama. Sebagai contoh, e"

dan e%

dalam

+ambar !.! merupakan dua sisi yang ajasen. Selain itu, dua buah titik disebut

ajasen jika kedua titik tersebut merupakan titik-titik ujung dari sisi yang


7/33

sama. 5alam +ambar !.!, 7* dan 7

0 adalah dua titik yang saling ajasen,

sedangkan titik 7! dan 7

* merupakan dua titik yang tidak saling ajasen.

Cumlah atau banyaknya sisi yang insiden dengan suatu titik 7 i (loop

dihitung dua kali), disebut derajat (degree) dari titik tersebut, dinotasikan

d(7i). Sebagai contoh, dalam +ambar !.!, d (7

!) > d (7

*) > #, d (7

") > *, dan

d (70 ) > !. 5erajat suatu titik sering juga disebut valensi dari titik tersebut.

Selanjutnya pandang sebuah graf + dengan e sisi dan n titik 7!,

7", ..., 7

n. arena tiap sisi menyumbangkan dua derajat, maka jumlah derajat

dari semua titik dalam + sama dengan dua kali jumlah sisi dalam +.

5engan demikian,

( ) "id v e= (!)

Sebagai contoh, pada +ambar !.!

d (7!) D d (7

") D d (7

#) D d (7

*) D d (7

0) > # D * D # D # D ! > !*

> dua kali jumlah sisi


8/33

( )k d vå > sebuah bilangan genap. (#)

arena dalam persamaan (#) tiap d (vk ) adalah bilangan ganjil, maka jumlah

keseluruhannya pastilah genap. (terbukti)

Sebuah graf dengan semua titiknya berderajat sama disebut graf reguler .

Selanjutnya akan dibahas bagaimana graf dapat digunakan untuk

menunjukkan hubungan tertentu antara objek-objek sembarang. Bntuk

mempelajari keterhubungan objek-objek itu secara lebih mendalam, maka

kita perlu mempelajari teori graf secara lebih mendetil. ita memerlukan

istilah tertentu untuk menunjukkan bagaimana kedudukan titik dan garisdalam graf itu. Estilah ini berlaku untuk semua graf.

5ua titik P dan Q yang dihubungkan dengan sebuah garis e dikatakan

ajasen. $itik P dan Q yang terletak pada garis e atau titik P dan Q merupakan

titik ujung garis e dikatakan insiden pada garis e atau garis e insiden pada

titik P dan Q. 1ada graf berikut, titik a ajasen dengan titik b, tetapi titik a

dan c tidak ajasen, demikian pula titik b dan c tidak ajasen. $itik a insiden

pada sisi e, titik c tidak insiden pada sisi e. 1ada graf ! tidak ada pasangan

titik yang ajasen.

Gabar !.'.

E. TITIK TERISOLASI DAN TITIK ANTING/JNG

Sebuah titik yang tidak memiliki sisi insiden disebut titik terisolasi.

5engan kata lain, titik terisolasi adalah titik yang berderajat nol. $itik 7* dan

7% dalam +ambar !.% di ba2ah ini adalah dua contoh titik terisolasi. Sebuah

titik berderajat satu disebut titik anting"ujung . $itik 7# dalam +ambar !.%

merupakan contoh titik anting. 5ua sisi yang saling berajasensi atau


9/33

berbatasan disebut seri jika titik sekutunya berderajat dua. 5alam +ambar

!.%, dua sisi yang insiden dengan 7! adalah seri.

Gabar !.(.Graf yang euat titik teriso"asi, sisi seri, dan titik anting

!) $eori graf lahir pada $ahun !%#& melalui tulisan 'uler yang mengupas

masalah ....

") +.. irchoff berhasil mengembangkan salah satu cabangFbagian teori

graf yang disebut teori ....

#) 1ara ahli teori graf berkeyakinan bah2a yang pertama kali

mengembangkan atau membahas masalah empat 2arna adalah ....

*) 1ada +ambar !.!, sebutkan sebuah sisi yang dua titik ujungnya samaG

0) 1erhatikan kembali graf pada +ambar !.!. Apakah graf tersebut

memiliki sisi sejajarH

&) Apa yang dimaksud dengan graf sederhanaG

%) 1erhatikan kembali graf pada +ambar !.!. Sebutkan sisi-sisi yang

insiden dengan titik 7#G

) Cika dua buah sisi yang tidak paralel insiden di sebuah titik yang sama,

maka kedua sisi itu disebut .....

LATIHAN

Bntuk memperdalam pemahaman Anda mengenai materi di atas,

kerjakanlah latihan berikutG


10/33

/) (?, '), himpunan mana yang dimungkinkan

merupakan sebuah himpunan kosongH

Petunjuk #awaban $atihan

!)Cembatan onigsberg

")$eori pohon

#)Mobius

*)Sisi e

!

0)a, yaitu e

* dan e

0

&)+raf sederhana adalah graf yang tidak memuat loop dan sisi paralel

%)Sisi-sisi yang insiden dengan 7

# adalah e

*, e

0, dan e

&

)Ajasen

/)+enap

!4)8impunan sisi '


11/33

. +raf sederhana adalah sebuah graf yang tidak memuat loop dan sisi

paralel.

/. Sebuah graf + > (?, ') dengan ? dan ' berupa himpunan hingga

disebut graf hingga, dan jika sebaliknya disebut graf tak hingga.

!4. 5ua sisi yang tidak paralel disebut ajasen, jika kedua sisi tersebut

insiden dengan titik yang sama.

!!. 5ua buah titik disebut ajasen, jika kedua titik tersebut merupakan

titik-titik ujung dari sisi yang sama.

!".


12/33

(?, ') disebut graf hingga jika ....

A. ? dan ' merupakan himpunan hingga

(?, ') disebut graf tak hingga jika ....

A. ? dan ' merupakan himpunan hingga


13/33

A. seri

cukup

J %4I > kurang

Apabila mencapai tingkat penguasaan 4I atau lebih, Anda dapat

meneruskan dengan egiatan


14/33

Kegiatan Belajar #Graf sebagai Mode" Mateatika

dan )p"ikasinya

A. GRAF SEBAGAI $ODEL $ATE$ATIKA

onstruksi model matematika dapat dibuat dalam berbagai cara dengan

permasalahan matematika yang berbeda-beda. Salah satu model matematika

yang sudah cukup dikenal dan bisa mencakup berbagai permasalahan adalah

teori graf. 1ada bagian ini akan disajikan contoh permasalahan yang dapatdibuat model matematikanya dalam bentuk graf.

%ontoh &

Seorang guru bermaksud membuat suatu diagram tentang hubungan

antar sis2a dari kelas yang diajarnya. 5iagram tersebut harus berisikan

informasi apakah antara satu sis2a dengan sis2a lainnya berteman atau tidak

berteman. 8al semacam itu dapat dinyatakan dalam bentuk diagram yang

disebut graf. 5alam graf tersebut, seorang sis2a dinyatakan sebagai sebuahtitik dan hubungan berteman antara dua sis2a, dinyatakan dengan sebuah sisi

yang menghubungkan titik-titik yang me2akili dua sis2a tersebut.

%ontoh '

5alam suatu persiapan untuk menghadapi perang, beberapa peleton

tentara ditempatkan di beberapa lokasi yang berbeda. omunikasi antara

peleton dilakukan dengan menggunakan radio telepon yang kemampuannya

terbatas pada jarak tertentu.Cika jarak antara dua peleton masih terjangkau, maka komunikasi dapat

dilakukan. eadaan seperti ini dapat dinyatakan dalam suatu model

matematika berbentuk graf. 5alam graf tersebut, titik menyatakan peleton

dan sisi antara dua titik menyatakan komunikasi antara dua peleton yang

di2akili oleh dua titik tersebut.

%ontoh (

Misalkan kita ingin menempuh perjalanan dari Cakarta menuju Surabaya.

Mungkin kita ingin mengetahui rute terpendek yang dapat dipilih. 5alam permasalahan ini kota direpresentasikan sebagai titik, sedangkan rute atau

jalan direpresentasikan sebagai segmen garis atau kur7a.


15/33

%ontoh )

Misalnya terdapat satuan tugas dalam kepolisian yang bertugasmengungkap jaringan pengedar obat terlarang. 8al tersebut dapat kita

gambarkan ke dalam sebuah graf. 5alam graf tersebut, tiap-tiap anggota

komisi dinyatakan dengan sebuah titik, dan hubungan di antara anggota

dinyatakan dengan sisi atau kur7a. 5alam permasalahan ini kita mungkin

ingin tahu seberapa rapuhkah jaringan komunikasi ini, dan seberapa

mudahkah kita bisa menghancurkan jaringan tersebut. 5engan menggunakan

teori graf desain jaringan komunikasi yang handal dapat diciptakan.

%ontoh *$eori graf juga biasanya digunakan dalam bidang elektronika, misalnya

untuk mendesain sirkuit cetakan.


16/33

Gabar !.*.

Misalkan 5! adalah sebuah graf berarah dengan ? > @7

!, 7

", 7

#, 7

* dan '

> @(7!, 7

"), (7

", 7

#), (7

#, 7

"). +raf berarah 5

!, dapat dibuat seperti gambar di

ba2ah ini (+ambar !./)

Gabar !.+.

Mungkin juga terjadi bah2a relasi yang mendefinisikan sebuah graf

berarah 5 merupakan sebuah relasi simetris. +raf semacam ini disebut Graf

berarah simetris. +ambar di ba2ah ini adalah contoh sebuah graf simetris.

Gabar !.!.

%ontoh +


17/33

5iketahui sebuah graf berarah 5 dengan himpunan ? > @7!, 7

", 7

#, 7

*, 7

0,

7& dan himpunan arah ' > @(7

!, 7

#), (7

", 7

#), (7

#, 7

*), (7

*, 7

!), (7

*, 7

#), (7

0,

7&) . +ambarlah diagram dari graf 5.

Penyelesaian

+ambar di ba2ah ini merupakan diagram dari graf 5.

Gabar !.!!.

C. JARINGAN KERJA SEBAGAI $ODEL $ATE$ATIKA

Sebuah jaringan kerja adalah sebuah graf berarah dengan suatu fungsi

yang memetakan himpunan sisi ke himpunan bilangan real. Caringan kerja

yang merupakan sebuah graf disebut jaringan kerja tidak berarah sedangkan

jaringan kerja yang merupakan graf berarah disebut jaringan kerja berarah.

+ambar di ba2ah ini merupakan contoh diagram dari dua jenis jaringan kerja

tersebut.

Gabar !.!#.

Graf bertanda S adalah suatu jaringan kerja tidak berarah yang nilai

fungsinya D! atau -!. arena tanda positif atau negatif dipasangkan pada tiap


18/33

sisi dari S, maka dapat dipahami bila tiap sisi dari S disebut sisi positif atau

sisi negatif. Sebagai contoh, jika

? > @ 7!, 7

", 7

#

' > @ 7!7

", 7

!7

#, 7

"7

#

dan

f > @ (7!7

", D!), (7

!7

#, -!), (7

"7

#, -!)

maka graf bertanda seperti ini dapat dinyatakan dalam dua cara yaitu seperti

diperlihatkan pada gambar di ba2ah ini.

Gabar !.!$.

%ontoh , 8ubungan bertetangga dapat dinyatakan dalam bentuk graf bertanda.

5ua keluarga yang saling berhubungan dengan baik dapat di2akili oleh sisi

positif, dua keluarga yang berhubungan kurang baik dapat dinyatakan dengan

sisi negatif dan dua keluarga yang tidak saling berhubungan atau tidak saling

kenal dapat dinyatakan dengan tidak ada sisi antar dua titik yang me2akili

dua tetangga tersebut.

Caringan kerja tidak berarah yang nilai fungsinya bulat positif sering kali

digunakan sebagai model matematika. Ada dua cara yang sering digunakanuntuk menyatakan jaringan kerja tidak berarah seperti ini. Sebagai contoh,

jika

? > @ 7!, 7

", 7

#

' > @ 7!7

", 7

!7

#, 7

"7

#

dan

f > @ (7! 7

", "), (7

!7

#, !), (7

"7

#, #)

maka jaringan kerjanya dapat dibuat seperti terlihat pada gambar di ba2ahini.


19/33

Gabar !.!%.

Caringan kerja tak berarah yang dinyatakan seperti +ambar !.!* disebutmultigraf . Misalnya M adalah sebuah multigraf dengan himpunan sisi ' dan

fungsi f. Cika u7 ' dan f(u7) > n (n adalah bilangan bulat positif), maka u

dan 7 dihubungkan oleh n sisi. Sisi-sisi seperti ini disebut sisi multipel .

%ontoh -

Misalkan 7!, 7

", dan 7

# adalah tiga buah kota. $iap dua kota dihubungkan

oleh satu jalan yang jaraknya tidak sama. Cika antara salah satu kota dengan

kota lain ditempuh dengan jalan kaki, maka lama perjalanannya adalahsebagai berikut

antara 7! dan 7

", dua hari;

antara 7! dan 7

#, satu hari;

antara 7" dan 7

#, tiga hari.

Situasi seperti ini dapat dinyatakan dalam bentuk graf seperti pada

+ambar !.!* (a).

%ontoh .Misalkan 7

!, 7

", dan 7

# adalah tiga buah kota. Antara 7

! dan 7

" terdapat

dua jalan, antara 7! dan 7

# terdapat satu jalan, sedangkan antara 7

" dan 7

#

terdapat tiga jalan. Situasi ini dapat dinyatakan dengan graf seperti +ambar

!.!* (b).


20/33

Misalkan

? > @7!, 7

", 7

#, 7

* , dan

' > @ (7!, 7"), (7", 7#), (7#, 7"), (7#, 7#), (7*, 7*) .

arena relasi ' memuat (7#, 7

#) dan (7

*, 7

*), maka graf berarah dengan loop

ini dapat digambar seperti di ba2ah ini.

Gabar !.!&.

D. SILSILAH KELARGA

Silsilah keluarga merupakan contoh masalah sederhana yang bisa

dinyatakan dalam bentuk graf. +raf yang terbentuk dari silsilah keluarga biasanya berupa pohon atau tree. +ambar !.!& di ba2ah ini adalah contoh

silsilah keluarga Andri yang dapat diubah menjadi sebuah pohon.

Gabar !.!'.

E. SISTE$ KO$NIKASI

1erhatikan +ambar !.!% di ba2ah ini. +ambar tersebut merupakan suatu

jaringan komunikasi dengan menggunakan komputer. 1ada gambar tersebut,


21/33

bulatan kecil menyatakan komputer mikro dan bulatan ber2arna hitam kecil

menyatakan komputer mini.

Gabar !.!(.

omputer mini digunakan untuk mengubah signal dari suatu sirkuit ke

sirkuit lainnya serta untuk memproses data. Sedangkan lambang diamond

menyatakan komputer mainframe yang merupakan pusat dari seluruh jaringan. Seseorang yang bermaksud mengakses jaringan tersebut harus

melalui salah satu dari komputer mini yang ada dengan menggunakan

komputer mikro miliknya. Sistem tersebut dapat digunakan untuk mengirim

pesan antarkomputer mikro, atau untuk melakukan proses pengolahan data

dengan menggunakan salah satu komputer yang lebih besar. Melalui diagram

atau graf di atas dapat diajukan berbagai pertanyaan antara lain sebagai

berikut

!. 5apatkah komputer mikro di Seattle mengirimkan pesan melaluikomputer mikro di MiamiH

".


22/33

F. JARINGAN TRANSPORTASI

Masalah transportasi sebenarnya merupakan hal yang sangat klasik dalam teori graf, karena kelahiran teori graf itu dia2ali oleh masalah

transportasi yang terkenal yaitu Cembatan onigsberg. Elustrasi jembatan

tersebut dapat dilihat pada +ambar !.! di ba2ah ini.

Gabar !.!*.

1ada gambar tersebut A,


23/33

G. DESAIN ARSITEKTR

1erhatikan desain sebuah bangunan pada +ambar !."4 di ba2ah ini.1ada gambar tersebut A,


24/33

H. IKATAN KI$IA

5alam bidang kimia pun teori graf mempunyai kegunaan yang amat penting. ita mengenal ikatan-ikatan kimia seperti 8"S=*, 8"=, =", dan

8*. $iap molekul kimia mengandung sejumlah atom yang dikaitkan dengan

ikatan kimia. Sebagai contoh, karbon dioksida mempunyai sebuah atom

karbon yang dikaitkan terhadap " atom oksigen. 5emikian pula dalam

"80=8 (ethanol), sebuah atom karbon dikaitkan pada # atom hidrogen,

sedangkan atom karbon lainnya dikaitkan dengan atom karbon pertama, "

atom hidrogen dan sebuah atom oksigen. Atom oksigennya dikaitkan dengan

sebuah atom hidrogen, selain dengan sebuah atom karbon. 1erhatikan+ambar !."".

Gabar !.##

onstruksi "80=8 seperti pada gambar di atas termasuk ikatan kimia

yang cukup rumit. 5alam teori graf ikatan kimia ini dapat dinyatakan dengan

graf pada +ambar !."#. 5alam graf tersebut banyaknya sisi yang

menghubungkan sebuah titik menyatakan 7alensi dari tiap-tiap atom yang

berkorespondensi.

Gabar !.#$

5iagram pada +ambar !."# pertama kali digunakan tahun !&* untuk

menggambarkan bagaimana susunan atom-atom dalam sebuah molekul. Ede pertama diketengahkan oleh AleLander rum


25/33

isomer-isomer. Esomer menyatakan molekul-molekul yang mempunyai rumus

kimia yang sama tapi mempunyai sifat kimia2i yang berlainan.

5iagram ini menunjukkan bagaimana sebuah atom dihubungkan denganatom lainnya. Enformasi ini sangat diperlukan dalam mempelajari perilaku

kimia2i sebuah molekul. Masalah dokumentasi kimia berhubungan dengan

isomorfisme dan masalah pengkodean. Eni menunjukkan bah2a penyelesaian

bagi masalah isomorfisme graf bagian memberikan penyelesaian bagi

masalah penelitian struktur kimia.

!) Suatu sekolah bermaksud membentuk sepuluh macam kepanitiaan yang

anggota-anggotanya diambil dari !0 orang sis2a terpilih.


26/33

Petunjuk #awaban $atihan

!) Bntuk graf +!, misalkan ? (+

!) menyatakan sis2a terpilih yang

jumlahnya !0 orang. 5ua titik dari +! dihubungkan dengan sebuah sisi,

jika dan hanya jika dua sis2a yang di2akili oleh titik-titik tersebut

menjadi anggota kepanitiaan yang sama. Bntuk graf +", misalkan ?

(+") menyatakan !4 kepanitiaan yang dibentuk. 5ua titik dari +

"

dihubungkan jika dan hanya jika dua kepanitiaan yang di2akili oleh

titik-titik tersebut memuat anggota yang sama.

")

#)

*) $ree atau pohon.

0) Sistem komunikasi, jaringan transportasi, dan desain arsitektur.

!. 5i antara beberapa model matematika yang sudah dikenal, graf

merupakan salah satu contoh model matematika yang banyak

kegunaannya.

". $erdapat beberapa jenis graf yaitu graf tak berarah, graf berarah, dan

jaringan kerja.

RANGKUMAN


27/33

#. Sebuah graf + adalah suatu himpunan hingga ? yang tidak kosong

yang memenuhi sifat tidak refleksif dan simetris dari suatu relasi

pada ?.*. Sebuah graf berarah 5 adalah suatu himpunan ? yang tidak kosong

dengan sebuah relasi pada ? yang tidak refleksif.

0. Caringan kerja adalah sebuah graf atau graf berarah dengan suatu

fungsi yang memetakan himpunan sisi ke himpunan bilangan real.

&. +raf dapat diterapkan dalam beberapa permasalahan antara lain

masalah silsilah keluarga, sistem komunikasi, jaringan transportasi,

dan desain arsitektur.

!)


28/33


29/33

. onigsberg

5. 8amilton

ocokkanlah ja2aban Anda dengan unci Ca2aban $es 3ormatif " yang

terdapat di bagian akhir modul ini. 8itunglah ja2aban yang benar.

emudian, gunakan rumus berikut untuk mengetahui tingkat penguasaan

Anda terhadap materi egiatan


30/33

")


31/33

Daftar Pustaka


32/33

G"osariu

A%a"e&"i

edudukan dua titik (misal P dan Q) yang dihubungkan dengan sebuah

sisi e.

Dera%at Titik

(/ , 6 ) dengan 6 > 4.

Gra' Se)er(a&a

Sebuah graf yang tidak memiliki loop dan sisi paralel.

Gra' Tak Hi&!!a

Sebuah graf G (/ , 6 ) dengan / dan 6 tak hingga.

I&"i)e&"i


33/33

edudukan dua titik (misal P dan Q) yang terletak pada sisi e atau titik

P dan Q merupakan titik ujung sisi e.

Jari&!a& Ker%a

Sebuah graf berarah dengan suatu fungsi yang memetakan himpunan sisi

ke himpunan bilangan real.

Jari&!a& Ker%a Berara(

Caringan kerja yang merupakan graf berarah.

Jari&!a& Ker%a Ti)ak Berara(Caringan kerja yang merupakan sebuah graf.

Loo+

Sisi yang dua titik ujungnya sama.

Seri

5ua sisi yang saling berajasensi atau berbatasan jika titik sekutunya

berderajat satu.

Si"i Para*e*

5ua titik yang berlainan dihubungkan oleh dua sisi atau lebih.

Titik A&ti&!/%u&!

Sebuah titik yang berderajat satu.

Titik Teri"o*a"i

Sebuah titik yang tidak memiliki sisi insiden atau titik yang berderajat

nol.

,a*e&"i

5erajat suatu titik.

modul 1. pengetahuan dasar teori graf (1x pert)

Documents