BAB II TINJAUAN PUSTAKA
Pada bab ini akan diberikan definisi dan teorema yang berhubungan dengan penelitian yang dilakukan. 2.1. Konsep Dasar Graf Graf G didefinisikan sebagai pasangan himpunan terurut (V(G),E(G)) dengan ( )
*
+ menyatakan himpunan titik dengan
( )
( )
*
+ menyatakan himpunan garis yaitu pasangan tak terurut dari
dan
( ) (Deo, 1989). v1 v2
e1 v3
e3
e2 e7
e4
e6 v4
e5
v5
G Gambar 2.1. Contoh graf G dengan 5 titik dan 7 garis Walk adalah barisan berhingga dari titik dan garis, dimulai dan diakhiri dengan titik, sedemikian sehingga setiap garis menempel dengan titik sebelum dan sesudahnya. Tidak ada sisi yang muncul lebih dari sekali dalam satu walk.
Lintasan (path) merupakan walk yang semua titiknya berbeda. Suatu graf G dikatakan terhubung jika terdapat lintasan (path) yang menghubungkan setiap pasangan titik di G. Jika tidak, maka G tidak terhubung (Deo, 1989).
(a)
(b)
Gambar 2.2. Contoh graf tak terhubung (a) dan contoh graf terhubung (b) Suatu garis yang berawal dan berakhir pada titik yang sama disebut sebagai loop, sedangkan dua garis atau lebih yang menghubungkan dua titik yang sama disebut sebagai garis paralel. Sebagai contoh pada Gambar 2.1, garis dan garis
dan
merupakan loop
merupakan garis paralel. Graf sederhana adalah graf yang
tidak mengandung loop atau garis paralel (Deo, 1989).
Gambar 2.3. Contoh graf sederhana Jika suatu garis
berujung di titik
maka
dan
sama lain. Sebagai contoh, pada Gambar 2.1, garis
dikatakan saling incident satu dan
incident dengan titik
. Dua atau lebih garis tidak paralel yang incident dengan titik yang sama disebut sebagai garis yang bertetangga (adjacent). Contohnya, pada Gambar 2.1, garis dan
adalah garis-garis yang bertetangga. Dua titik dikatakan bertetangga jika
titik tersebut menjadi titik-titik ujung dari suatu garis. Pada Gambar 2.1, salah satu contoh titik-titik yang bertetangga adalah titik
dan
. 6
Banyaknya garis yang menempel (incident) dalam satu titik dengan loop dihitung sebagai 2 garis disebut sebagai derajat (degree) dari suatu titik, dinotasikan sebagai
( ). Sebagai contoh dalam Gambar 2.1, ( )
, ( )
( )
, ( )
dan ( )
Suatu graf G dikatakan graf berlabel jika titik atau garisnya di berikan suatu nilai atau data tertentu. Jika tidak maka graf G dikatakan graf tak berlabel. Pelabelan graf dapat berupa pelabelan titik, pelabelan garis, atau pelabelan titik dan garis. Jika pelabelan tersebut merupakan pelabelan titik dan garis, maka pelabelan tersebut disebut dengan pelabelan total (Deo, 1989). 2.2. Teknik Dasar Pencacahan Jika suatu aktivitas dapat dibentuk dalam langkah berurutan dan langkah 1 dapat dilakukan dengan
cara, langkah 2 dapat dilakukan dalam
seterusnya sampai langkah ke
dapat dilakukan dalam
aktivitas berbeda yang mungkin adalah
cara dan
cara, maka banyaknya
(Johnsonbaugh, 1997).
Suatu permutasi dari elemen-elemen yang berbeda adalah penyusunan elemenelemen tersebut kedalam urutan yang dapat dibedakan. Suatu permutasi-r dari unsur yang berbeda unsur dari *
merupakan sebuah pengurutan dari subhimpunan r+. Banyaknya permutasi-r dari sebuah himpunan
yang berbeda dinyatakan dengan himpunan
(
unsur
). Banyaknya permutasi-r dari sebuah
unsur yang berbeda adalah (
)
(
)(
)
(
)
atau (
)
(
) 7
; (
)(
)
Misalkan terdapat sebanyak kali, permutasi
;
(Johnsonbaugh, 1997)
unsur dan ada
unsur yang masing-masing muncul
unsur tersebut adalah:
dengan Contoh: Untuk menentukan banyaknya permutasi yang mungkin dari huruf-huruf yang menyusun kata “MATEMATIKA” dapat menggunakan permutasi dengan beberapa unsur yang sama. Banyaknya huruf dalam “MATEMATIKA” adalah sedangkan ada 2 huruf M, 3 huruf A, 2 huruf T, 1 huruf E, 1 huruf I dan 1 huruf K. Maka banyaknya cara menyusun huruf-huruf tersebut adalah:
Jadi banyaknya cara untuk menyusun huruf-huruf dalam kata “MATEMATIKA” adalah 15120 cara. Diberikan suatu himpunan
*
+ yang mengandung
unsur yang
berbeda: a. Suatu r-kombinasi dari
adalah seleksi tak terurut dari r-unsur
(yakni
subhimpunan r-unsur dari ) b. Banyaknya r-kombinasi dari suatu himpunan dengan n unsur yang berbeda dinotasikan dengan (
) atau ( )
8
Banyaknya r-kombinasi dari sebuah himpunan dengan
unsur yang berbeda
adalah: (
)
(
)
(
(
)(
)
(
)
(
)
)
dengan ; (Johnsonbaugh, 1997). Misalkan terdapat
objek yang akan dibagikan kedalam
tempat yang berbeda.
Maka banyaknya cara untuk menempatkan objek tersebut adalah (
)
(
)
Contoh: Empat bola akan dibagikan seluruhnya ke dalam 3 kotak. Banyaknya cara untuk menyusun bola-bola tersebut dapat ditentukan dengan menggunakan kombinasi dengan perulangan. Misalkan
adalah banyak bola dan
adalah banyak kotak
maka banyaknya cara menyusun bola adalah:
(
)
(
)
( )
Jadi banyaknya cara untuk menyusun 4 bola kedalam 3 kotak adalah 15 cara.
9
2.3. Penghitungan Graf (Graph Counting) Misal
( ).
, dengan
a. Banyaknya
graf sederhana berlabel dengan
titik dinyatakan sebagai
( )
b. Banyaknya sebagai
( ) graf sederhana dengan
( )
titik dan
garis dinyatakan
(( ) ) (Agreusson dan Raymon, 2007).
10
