bab iv konteks graph

8/19/2019 Bab IV Konteks Graph

http://slidepdf.com/reader/full/bab-iv-konteks-graph 1/4



Graph eularian

• Adalah graph yang dapat dilalui seluruh ruas dan simpulnya dengan sekali jalan. ( simpul

P

Q R

o e er a – a , ruas anya sekali )

• Dari graph dikanan S T

Z G2

• Ada yang bilang syarat eularian adalah :

B C

P

Q R

‐ semua ra a s mpu arus genap, dengan perkecualian 2 simpul berderajat 3.

‐

D E S T

G1 G3

graph dikanan ini.

‐ bagaimana pendapatmu.

Graph lingkaran dan graph teratur

• Graph lingkaran adalah graph

=2

• rap era ur a a a grap

yang drajat seluruh simpulnya

a a a sama

A V

B C W U

• Adalah graph yang sebangun sebagaimana

halnya dengan graph ABC dan UVW.

• Coba perhatikan isomoprhic pasangan graph

dua – dua diatas.

Graph bidang

Graph bidang, kedua

ra h sama ident ik

Bukan graph bidang karena tidak

dapat direpresentasikan kedalam

• Graph bidang adalah graph yang dapat digambarkan

bidang tanpa ruas berpotongan

buktikan

.

• Perhatikan juga 3 graph pertama diatas, apakah isomorphic ?

• Check kebenaran bahwa ketiga graph itu adalah graph

bidang. •

graph bidang.

.

• Daerah dalam graph adalah

bidang yang dikukung oleh

beberapa ruas dengan siklus tertutup.

• Daerah graph baru dapat D1

ditentukan daerahnya sesudah

dijadikan graph bidang. D2

D4 D3

• Apakah mungkin suatu daerah

ra h dibatasi oleh lebih dari ti aD5

ruas?

Jika titik bertetanga harus diberi warna

.

diperlukan oleh tiap graph

• Ingat yang disebut simpul bertetangga jika ada satu

w: n= 1 2 3 3 3 4

.

pada graph 1 tidak ada simpul ber‐tetangga

•

tidak ada simpul bertetangga berwarna sama.



Aturan untuk mewarnakan dengan jumlah

B E HTata cara pengerjaan

1.Urutkan berdasarkan dera at sim ul

A B C D E F G H I

C F I

mulai dari yang besar sampai yg kecil

2.Warnai warna pertama sampai terakhir

untuk simpul yang tidak bertetangga .

3 3 2 3 5 4 2 4 23.Lakukan untuk warna yang kedua dst.

4.Maka

jumlah

warna

yang

diperlukan…..

Merah , Biru dan HijauE H F A B D C G I

5 4 4 3 3 3 2 2 2

E H F A B D C G I

5 4 4 3 3 3 2 2 2

M B H B H B M M M

• Tentukan warna minimum yang diperlukan

A

B C

D

Tentukan warna pada

peta dibawah ini supaya

EH

berwarna sama dengan bidang disebelahnya.

G FDapatkah soal ini dirubah

ke simpul?

d1

d2d4

d5

d6

Tentukanlah pengaturan lampu hijau, merah dan kuning untuk tiap arah.

B Lintas keterangan

AB 1 Langsung 2 AC

A C

ampu

AD 3 Lampu

BA 4 Lampu

3 AD

7 C

D BD 6 Lampu

CA 7 Lampu

CD 8 langsung Pengaturan : CB tak

4 BA

6 BD

CB 9 Lampu

berkait dengan CA (

bebas) → no

conection, tapi

ruas 3 3 4 3 2

ttk 4 2 3 6 9 7

Maka tentukan

warna titik titik

ruas 4 3 3 3 3 2

H K K H M M .

BB

A B C D E

F G H

A

CJ

I K L

D

Latihan lagi – latihan lagi

•Ada 7 orang bermain, akan

dikelompokan. Jumlah anggota

er kelom ok minimal 2 Ada •

•

E.

beberapa orang yang tidak cocok

dalam satu kelompok. Dari datadata dibawah ini; tentukanlah

G• F

•

jumlah kelompok minimal supaya

permainan dapat berjalan

dengan baik.

A• D

•D hanya cocok dengan A dan F

•G tidak bagus jika bertemu

dengan A,E

B•

•

C• ecua engan an ma a

dapat bertemu dengan siapa

saja.

•

Minimum

perlu

…………kel,

sekelompok



8 titik kota

A,B,C,D,E,F,G dan HA B C D E F G H

erara sau sama a n

seperti table disamping

ini (km). Yang diminta,

B

1000 1200

C

900 1400

terpendek yang harus

ditempuh supaya

semua kota terkunun i

D 1000

E

1700

F

800 1000

dan kembali ketempatasal.

G 300

Maka an an alan

A

B

F

minimum yang

dijalani adalah :

………… Km

.

yang paling pendek (

salah satu )

2. Lompati jika titik sudah

G H

Eepert pat

disampingada garisnya

3. Nanti akan terlihat mana

jalurnya.

A B C D E a a a pos s s rup pa a se ua

mesin. Robot bertugas memasang skrup

tersebut. Tentukan path yang harus

.

A 0 5 9 3 3

B 0 7 5 5

dipasang supaya gerakan robot itu

efisien. Waktu yang dibutuhkan untuk

ber erak dari titik ke titik diberikan

C 0 8 8

D 0 10

dengan table di kanan ini. Berapakah

detik yang dibutuhkan j untuk

Satuan dalam detik

.

memutar tiap skrup = 3 detik

• .

ternyata palsu. Coin yang palsu mungkin lebih

.

Misalkan tersedia sebuah timbangan neraca

,

untuk mencari uang palsu tersebut dengan

.

•

dan segelas air .

sedemikian hingga terjadi panggung pisau.

• Panggung p sau arus cu up uat untu

menampung gelas berisi air diatasnya.

• Rencanakan.!!

•

pisau, kerjakan dengan pertanyaan yang sama.

2 botol dengan 4 pisau?

•

berjabatan tangan. Berapa jabatan terjadi .(

bab iv konteks graph

Documents