KELOMPOK 1

RINU SETYAWATI

SITI KHOTIMATUL HUSNA

ABDUL MALIK

SYAIFUL LUTFI

AHMAD ZAKARIA

HARIS MAULIDI

NURUL HUSNA

Laili suaidah

TEORI DASAR GRAFTEORI DASAR GRAF

1.1 GRAF DAN DERAJAT TITIK

CONTOH:

APEL PISANG CERY KURMA

ERICA FRANK GREG HANK

San Francisco

Oakland

Half Moon Bay

Airport

Bay Bridge

80

PETA SAN JOSE – SAN FRANCISCO

Palo Alto

San Jose

Santa Cruz

Half Moon Bay 101

208

17

880

AIR (H2O)

H

O

H

CYCLOHEXENA (C6H12)

H H

H

HH

H

CC

CC

C

H

H

HH

H

H CC

C

C C

CCC

C

CC

C

C

C

C

C

C

C

C

C

CC

CO

VITAMIN A (C20H30O)

C CCC

CONTOH PADA PETA DARI JALAN JEND. SUDIRMANMENUJU VETERAN UNIVERSITY

Dalam mata kuliah latis dan aljabar Boolean, grafik-grafik

dapat membentuk sketsa dari sebuah bangunan.

Mereka yang telah mempelajari teori himpunan akan

mengenali diagram dari gambar 1.1.10 dan 1.1.11

sebagai pola-pola geometris dari himpunan bagian.

Untuk memudahkan, kita menggunakan notasi yang

lebih singkat untuk himpunan; contohnya, kita menulis

ABC untuk himpunan {A, B, C}.

ABC

AB AC BC

Gambar 1.10

B CA

Pola geometris dari himpunan bagian ABC

Diagram dari gambar 1.10 dan 1.11 menunjukkan

semua himpunan bagian dari himpunan diatasnya. Jika

satu himpunan diperoleh dari himpunan yang berbedasatu himpunan diperoleh dari himpunan yang berbeda

dengan menghapus satu elemen, maka dua himpunan

tersebut dihubungkan dengan garis dalam diagram.

60

3.20 5.12 6.104.152.30

Faktor yang berbeda dari bilangan bulat 60 ditunjukkandalam diagram gambar 1.1.12.

3.20 5.12 6.104.152.30

2.2.3.5

2.2.15 2.310 2.5.6 3.4.5

Gambar 1.12

Beberapa contoh graf yang lain adalah sebagai berikut:

●

●

●

●

●

●

●

●

●

●

●

●

●

●Gambar 1.13

●●

●

●

●

●

Gambar 1.15

Gambar 1.13Gambar 1.14

●

●

●

●

●

●

●

● ● ● ●

Gambar 1.16

●

●

●

●

● ●

●

●

●

Gambar 1.17

Definisi Sebuah Graph : Graph G

Graph adalah sebuah himpunan (V,E), dimana V adalah

tak kosong atau bisa diartikan elemen-elemen yang

dinamakan verteks atau titik sedangkan E adalah

pasangan terurut dari verteks-verteks yang berbeda

dinamakan edgE (sisi). Sebagai contohnya seperti pada

permulaan tadi dimana verteks (titik) adalah buah dan

anak-anak pada contoh pertama sedangkan garis-garis

yang menghubungkan antara buah dan anak-anak

dinamakan edeg(sisi).

CERYAPEL PISANG KURMA

Vertex atau titik

Edge/sisi

ERICA FRANK GREG HANK

Perhatikan gambar 1.17 adalah gambar yang tidak utuh, yaitu takterhubung. Kemudian kita beri definisi yang tepat dari sebuahgrafik terhubung

●

●

●

●

● ●

●

●

●

● ● ● ● ●

Gambar 1.17

●

●

●

● Gambar 1.18

Dalam grafik tidak diperbolehkan 2 titikyang bergabung dengan lebih dari 1 sisi.Jika kita membiarkan hal tersebut maka,disebut multigraf. Seperti pada gambar1.18

●

●

●

●

Gambar 1.19

Dalam gambar 1.19 memiliki apayang disebut putaran (LOOP), yangmerupakan relasi yang hanyadengan 1 titik. Struktur ini disebutPseudograph.

●

● ● ●

●

Gambar 1.20

A CB

EDGambar 1.20

●

●

●

●

● ●

●

●

●

Gambar 1.17

Pada gambar 1.17 mempunyai 2 titik berderajat 0 yang kitasebut dengan titik yang terisolasi (isolated verteks). Dansebuah titik berderajat 1 yang disebut end verteks.

●

●

Gambar 1.16

●

●

●

●

●

sebuah titik berderajat 1 yang disebut end verteks.

Mari kita jumlahkan derajat-derajat dari titik-titik pada grafyang ditunjukkan pada gambar 1.16

5+4+3+3+2+2+1=20

Jumlah dari sisinya adalah q = 10.

Jadi pada sebuah graf khusus ketika kita menjumlahkansemua derajat dari titik-titik, kita peroleh 2 kali jumlahsisinya.

Teorema 1.1 misal v1,v2,……,vp adalah titik-titik dari graf G,dan d1,d2,………..dp adalah derajat dari titik. Misal q adalahjumlah sisi dari graf G

d1 + d2 +……………..+dp=2q

Teorema 1.1 dapat dimulai sebagai berikut:

Contoh :Apakah ada sebuah graf dengan 7 buah titik, masing-masing titik berderajat 5?

Jawab:Jika ada sebuah graf yang jumlah seluruh derajatnya ituadalah 7 X 5=35. menurut teorema 1.1 angka ini (35) harusmerupakan bilangan genap, sehingga titik ada graf yangmerupakan bilangan genap, sehingga titik ada graf yangdimaksud.

Kembali ke gambar 1.16

●

●

●

●

●

●

Kita daftar semua derajat titiknyasebagai berikut:

5,4,3,3,2,2,1

Dari rangkaian berikut manakah yang merupakan sebuah graf:i) 5,4,3,2,2,1ii) 5,5,4,4,0ii) 5,5,4,4,0iii) 6,5,5,4,3,3,2,2,2iv) 6,6,6,6,4,3,3,0

Untuk i) kita lihat dengan segera bahwa jumlah derajatnyaadalah bilangan ganjil, sehingga rangkaian i) bukanlahmerupakan graf.

Untuk rangkaian ii) derajatnya berjumlah genap. Perhatikanbahwa bilangan pertama adalah 5. hal ini berarti bahwa, jikaada sebuah graf dengan rangkaian seperti ini. Graf inimempunyai sebuah titik yang berkorelasi dengan 5 titik yanglainnya, tetapi kemudian graf harus mempunyai sekurang-kurangnya 6 titik, dan hanya ada 5 bilangan pada rangkaiantersebut. Sehingga rangkaian ii) bukanlah graf.

Pada kasus rangkaian iii) kita peroleh rangkaian berikut:Pada kasus rangkaian iii) kita peroleh rangkaian berikut:1) 6 5 5 4 3 3 2 2 22) 4 4 3 2 2 1 2 23) 4 4 3 2 2 2 2 14) 3 2 1 1 2 2 15) 3 2 2 2 1 1 16) 1 1 1 1 1 1Rangkaian 6) adalah sebuah grafik.

Teorema 1.2 (Havel, Hakimi) mempertimbangkan 2 rangkaianberikut dan mengasumsikan rangkaian (1) adalah secaramenurun.1) s , t1, t2, . . . , ts, d1, . . . , dn

2) t1 – 1, t2 – 1, . . . , ts – 1, d1, . . . , dn

Kemudian rangkaian (1) adalah graf jika dan hanya jikarangkaian (2) adalah graf.

Bukti:Bukti:Anggap rangkaian 2) adalah graf, kemudian ada graf G2 denganrangkaian derajat sama dengan rangkaian derajat (2), kitabangun G1 dari G2, dengan menambahkan suatu titik danmenghubungkannya kepada titik yang derajatnya adalah t1 – 1,t2 – 1, . . . , ts – 1.

Kemudian G1 adalah suatu grafik dengan rangkaian derajatsama dengan rangkaian (1), maka rangkaian (1) adalah grafis.

Kita anggap bahwa rangkaian 1) adalah graf. Kemudian ada

sebuah graf H dengan derajat sama dengan rangkaian 1).

Misal titik S mempunyai derajat s, Ti mempunyai derajat ti,

Dj berderajat dj. Jika S berkorelasi dengan T1,T2,…..,Ts

kemudian secara sederhana kita hilangkan titik ini dan garis

yang berhubungan dengannya sehingga memperolehyang berhubungan dengannya sehingga memperoleh

sebuah graf dengan derajat yang sama pada rangkaian 2).

●● ●S Ti Dj

●● ●S TiDj

T●●●●

●●●●

S

S

Dj

Dj

Ti

Ti w

w

Sekarang kita gunakan prosedur untuk menentukan apakah

rangkaian iv merupakan graph.

iv 66664330

5553220

442110

3100031000

Ketika tidak ada graf dengan satu titik berderajat 3, satu titik

berderajat 1 dan tiga buah garis berderajat 0, kita melihat

bahwa rangkaian terakhir bukan merupakan graf, begitu juga

rangkaian iv.

1. tujuh siswa pergi berlibur. Mereka memutuskan bahwamasing masing akan mengirim 3 kartu post kepada 3 siswayang lain. Apakah mungkin bahwa setiap siswa menerimakartu poat dari tiga siswa yang dia kirimi kartu post secaratepat?

2. a. Buktikan bahwa untuk setiap bilangan genap adasebuah graf dengan n titik yang kesemuanya berderajat 3,sebuah graf dengan n titik yang kesemuanya berderajat 3,tanpa menggunakan teorema 1.1.2

b. buktikan bahwa setiap bilangan ganjil ada sebuah grafdengan n+1 titik seperti yang secara tepat n titik berderajat 3.

3. Buktikan bahwa setiap bilangan ada sebuah graf dengan ntitik yang kesemuanya berderajat 4

4. Yang manakah dari rangkaian berikut ini yangmerupakan graf?a) 55443221b) 65432222c) 444433d) 76544321

5. Gambarlah graf dengan rangkaian derajata) (4, 3, 2, 2, 1)b) (4, 3, 3, 3, 1)

6. Gambar 1.1.12 menunjukkan diagram perkalianuntuk bilangan 60. Konsesikan diagram perkalianuntuk bilangan 48.

SEKIANDAN

TERIMAKASIHTERIMAKASIH

WASSALAMU’ALAIAKUM