Makalah Graph “Derajat Titik”

MAKALAH

 

MATEMATIKA DISKRIT

 

 

 

DERAJAT TITIK

Oleh

NOFYTA ARLIANTI

(51536)

DOSEN PEMBIMBING

Prof. Dr. Ahmad Fauzan, M.Sc

 

KONSENTRASI PENDIDIKAN MATEMATIKA

PROGRAM STUDI TEKNOLOGI PENDIDIKAN

PROGRAM PASCASARJANA

UNIVERSITAS NEGRI PADANG

2010

DERAJAT TITIK

Misalkan G sebuah graph dan v sebuh titik G. Derajat titik v, dilambangkan dengan dG(v) atau d(v), adalah banyak sisi G yang terkait dengan titik v (dengan catatan setiap gulungan/loop di hitung dua kali), atau dengan kata lain derajat titik yaitu banyaknya sisi bertemu pada suatu titik. Misalkan peta pada jalan raya, dengan persimpangan yang merupaka pertemuan tiga jalan atau lebih. Situasi ini diilustrasikan sebagai berikut:

Pertigaan/simpang tiga

Perempatan/simpang empat

Peta pada jalan raya

Derajat minimum G, dilambangkan dengan , didefinisikan sebagai berikut:

= minimum {d(v) / v  V(G)}

Sedangakan derajat maksimum G, dilambangkan dengan , didefenisiskan sebagai berikut

= maksimum {d(v) / v  V(G)}

V4

V1

= 2

= 3

= 4

= 1

Contoh 1 : Derajat titik graph G dibawah ini adalah?

= 1

= 4

V2

V3

G

Walaupun derajat suatu titik telah didefenisikan hanya untuk graph tanpa loop, defenisi ini dapat dengan mudah di perluas untuk graf yang memiliki loop. Hal ini dilakukan dengan mengingat bahwa setiap loop menyumbang 2 pada derajat titiknya.

V1

Contoh 2: Derajat titik graph H dibawah ini adalah?

= 2

= 5

= 4

= 5

H

V2

V1

V4

= 2

= 5

Suatu graph G dikatakan beraturan jika semua titiknya memiliki derajat yang sama, maka = . Jika derajat titik adalah r, maka G dikatakan beraturan dengan derajat r. Dalam diagram berikut ini diilustrasikan beberapa contoh graph beraturan dengan derajat r, untuk berbagai nilai r.

V1

V5

=  =  =  =  = 0

=  = r = 0

Contoh 3:

V2

●              ●

V3

V4

●              ●

G

=  =  =  = 1

=  = r = 1

c

a

b

d

●                ●

H

=  =  =  =  = 4

=  = r = 4

G

v1

v5

V3

V2

V4

b

v

=  =  =  =   = 2

=  = r = 2

z

w

H

y

x

Bila diamati bahwa graph terakhir di atas merupakan graph beraturan dengan derajat 4 dan memiliki 5 titik, sehingga jumlah derajat titiknya 20. Juga diamati bahwa graph ini memiliki 10 sisi (5 di luar heptagon dan 5 didalamnya). Dengan kata lain, jumlah derajat titik itu tepat dua kali banyak sisinya. Hasil yang sesuai berlaku untuk semua graph, dan disebut lema jabat tangan.

LEMA JABAT TANGAN Dalam setiapp graph, jumlah semua derajat titiknya sama dengan dua kali banyak sisinya.

Pembuktian

Karena setiap sisi memiliki dua ujung, maka kedua ujung itu menyumbang 2 derajat. Sehingga jumlah derajat titiknya dua kali banyak sisinya.

Catat bahwa pembuktian ini valid (absah) walupun graphnya memiliki loop, karena setiap loop menyumbang 2 juga pada derajat titik itu.

Nama lema jabat tangan timbul dari kenyataan bahwa graph dapat digunakan untuk menyajikan sekelompok orang yang berjabat tangan pada suatu pesta. Dalam graph itu, orang-orang disajikan sebagai titik, dan sisinya menunjukan jabatan tangan antara orang-orang tersebut. Dengan interprestasi ini, banyaknya sisi menunjukkan banyak total jabat tangan yang terjadi. Sehingga lema jabat tangan itu menyatakan bahwa banyak orang yang berjabat tangan sama dengan dua kali jabat tangan yang terjadi. Penalarannya, dalam setiap jabat tangan ada dua tangan yang berjabatan.

Terdapat beberapa akibat (konsekuensi) penting dari lema jabat tangan ini:

  1. Dalam setiap graph, jumlah semua derajat titiknya merupakan bilangan genap.
  2. Dalam setiap graph, banyak titik yang derajatnya merupakan bilangan gasal tentulah genap.
  3. Jika G merupakan graph yang memiliki n titik dan beraturan dengan derajat r, maka G memiliki tepat  sisi.

Jika diberikan sebuah graph, dengan mudah kita bisa menentukan barisan derajatnya. Yang menjadi pertanyaan adalah apakah syarat dari sebuah barisan agar barisan tersebut merupakan barisan derajat sebuah graph? Jawaban atas pertanyaan tersebut disajikan dalam teorema berikut.

Teorema 1: Barisan bilangan bulat non negatif (d1, d2, …, dn) adalah barisan derajat sebuh graph jika dan hanya jika   genap.

Untuk menentukan apakah barisan bilangan bulat non negatif murupakan suatu graphic atau bukan, dapat digunakan teorema berikut.

Teorema 2: Misalkan  = (d1, d2, …, dn) barisan bulat non negatif monoton turun. Barisan  graphic jika dan hanya jika barisan ( ) graphic.

Contoh: Misalkan ada sebuah graph bipartisi komplit K3,2.

V1

V3

Barisan derajat K3,2 adalah  = (3,3,2,2,2). Karena K3,2 graph sederhana maka  adalah graphic.

V2

●          ●          ●

V5

V4

●          ●

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s