II. TINJAUAN PUSTAKA
Pada bab ini akan diberikan beberapa konsep dasar dalam teori graf dan teknik pencacahan dalam bentuk definisi dan teorema yang berhubungan dengan penelitian yang akan dilakukan.
2.1 Konsep Dasar Teori Graf
2.1.1 Graf
Graf G didefinisikan sebagai pasangan himpunan (V(G),E(G)) dengan V(G) = {v1, v2, v3, ..., vn} menyatakan himpunan titik, dengan V(G) ≠ Ø, sedangkan E(G) = {e1, e2, ..., en} menyatakan himpunan garis yakni pasangan tak terurut dari V(G) (Deo, 1989).
V1
V2
V4
V3
Gambar 2. Contoh graf dengan 4 titik dan 6 garis
6
2.1.2 Adjacent (Bertetangga) dan Incident (Menempel)
Dua titik dikatakan adjacent (bertetangga) jika ada garis yang menghubungkan keduanya. Suatu garis dikatakan incident (menempel) dengan suatu titik jika titik tersebut merupakan salah satu ujung dari garis tersebut (Deo, 1989).
V1 e1
V2
e2
V3
Gambar 3. Contoh graf dengan 3 titik dan 2 garis Pada Gambar 3, titik v2 bertetangga dengan titik v1 dan titik v1 bertetangga dengan titik v3. Tetapi, titik v2 tidak bertetangga dengan v3 karena tidak ada garis yang menghubungkan kedua titik tersebut. Garis e1 menempel pada titik v1 dan v2, sedangkan garis e2 menempel pada titik v1 dan v3.
2.1.3 Derajat Suatu Titik dan Titik Pendant (Daun)
Misalkan v adalah titik dalam suatu graf G. Derajat titik v pada graf G adalah banyaknya garis yang menempel pada titik v. Derajat suatu titik v dinotasikan dengan d(v). Pada Gambar 3, d(v1) = 2, d(v2) = 1 dan d(v3) = 2. Sedangkan, titik pendant (daun) adalah titik yang berderajat satu (Siang, 2006).
7
2.1.4 Loop, Garis Paralel dan Graf sederhana
Loop adalah garis yang titik awal dan ujungnya sama. Sedangkan, garis paralel adalah dua garis atau lebih yang memiliki titik ujung yang sama. Graf sederhana adalah suatu graf tanpa loop atau garis paralel (Deo, 1989).
a
b
c
Gambar 4. Contoh graf sederhana dan graf bukan graf sederhana Perhatikan bahwa Gambar a adalah contoh dari graf sederhana. Sedangkan Gambar b dan Gambar c adalah graf yang bukan graf sederhana.
2.1.5 Walk, Path dan Cycle Walk adalah barisan berhingga dari titik dan garis yang dimulai dan diakhiri dengan titik sedemikian sehingga setiap garis menempel pada titik sebelum dan sesudahnya. Walk yang berawal dan berakhir pada titik yang sama disebut closed walk. Sedangkan path adalah walk yang memiliki atau melewati titik yang berbeda-beda. Path yang berawal dan berakhir pada titik yang sama disebut cycle (Deo, 1989).
8
V5
e4
V4
e5
e3 e7
V6
e8
e9
V3
e2
e6
e1
V1
V2
Gambar 5. Contoh graf dengan 6 titik dan 9 garis Berdasarkan
Gambar
5,
salah
satu
contoh
dari
walk
yaitu
v6e5v5e4v4e9v2e1v1e6v6e7v1e1v2e2v3. Pada walk, garis dan titik boleh dilewati lebih dari satu kali. Sedangkan pada path, titik maupun garis tidak boleh dilewati lebih dari satu kali. Salah satu contoh path berdasarkan Gambar 5 adalah v1e1v2e2v3e3v4e4v5e5v6.
2.1.6 Graf Terhubung dan Graf Tidak Terhubung Suatu graf dikatakan graf terhubung jika untuk setiap dua titik yang berbeda pada graf tersebut terdapat path yang menghubungkannya. Jika tidak ada path yang menghubungkan, maka G dikatakan graf tak terhubung (Deo,1989).
Graf terhubung
Graf tak terhubung
Gambar 6. Contoh graf terhubung dan graf tak terhubung
9
2.1.7 Graf berlabel Graf berlabel adalah graf yang setiap titiknya diberi sebuah nilai atau label. Label pada tiap titik dapat berbeda–beda bergantung pada masalah yang dimodelkan dengan graf ( Munir, 2005).
2.2 Barisan Aritmatika Orde Tinggi
Definisi 1: Diberikan barisan bilangan {an} sebagai berikut: a0, a1, a2, a3, ..., am .................................................................................................................................. (2.2.1) Beda pertama dari barisan (2.2.1) yaitu: ,
,
, ..., dengan
= am+1 – am Secara rekurensi, definisikan beda orde ke k dari barisan (2.2.1) dengan orde k-1 sebagai beda sebelumnya yaitu: ,
,
, ...,
dengan =
-
.................................................................................... (2.2.2)
Perhatikan bahwa (2.2.2) valid untuk k = 1 jika ditulis am = (Alonso, 2000).
10
Proposisi 1 : Diberikan barisan (2.2.1). Jika terdapat polinomial p(x) berderajat k dengan koefisien A sehingga am = p(m) untuk m=1,2,3, ... maka barisan (2.2.1) adalah barisan aritmatika orde k dengan beda adalah k!c (Alonso,2000). Bukti: Misalkan p(x)=Axk+Bxk-1+Cxk-2+... maka am=Amk+Bmk-1+Ck-2+... Sehingga, = am+1 – am = A[(m+1)k – mk] + B[(m+1)k-1 – mk-1] + ... = Akmk-1+ ... Maka untuk beda pertama dapat dibentuk p1(x)= Akxk-1+ ... yang berderajat k-1 dengan koefisien pertama Ak sehingga
= p1(x).
Dengan melakukan perulangan proses yang sama sebanyak k kali dapat disimpulkan bahwa: = pk(m) untuk suatu polinomial pk(m) berderajat nol dengan koefisien pertama Ak. Sehingga
= k!c untuk n=0,1,2,3, ...
■
Berdasarkan Proposisi 1, dari barisan (2.2.1), terdapat polinomial p(x) dengan derajat k, p(x)=Axk+Bxk-1+Cxk-2+... dengan am = p(m) untuk m=1,2,3, ... maka barisan (2.2.1) yaitu am=Amk+Bmk-1+Ck-2+... adalah barisan aritmatika orde k dengan beda pada orde k adalah sama.
11
2.3 Konsep Dasar Teknik Pencacahan 2.3.1 Faktorial Misalkan n adalah bilangan bulat positif. Besaran n! (dibaca “n faktorial”) didefinisikan sebagai hasil kali semua bilangan bulat antara n hingga 1. n! =n(n-1)(n-2)(n-3) ... 1
(Ayres dan Schmidt, 2004).
2.3.2 Permutasi Permutasi adalah sebarang pengaturan dari sekumpulan objek dalam suatu urutan tertentu. Banyak permutasi dari n objek dengan menggunakan r objek dalam tiaptiap pengaturan dinotasikan
dengan r ≤ n. Secara umum, permutasi r objek
dari n buah objek dapat dihitung dengan persamaan:
=(
!
)!
Dalam permutasi, perulangan tidak diperbolehkan. Artinya, objek yang sudah dipilih tidak bisa dipilih kembali (Ayres dan Schmidt, 2004).
12
2.3.3 Kombinasi Kombinasi dari n objek dengan pengambilan sebanyak r objek dalam tiap-tiap pengambilan terdiri dari semua kumpulan r objek yang mungkin, tanpa memandang urutan pengaturannya. Banyaknya kombinasi n objek dengan pengambilan sebanyak r objek dinyatakan dengan
dengan r ≤ n. Banyaknya
kombinasi dari n objek berbeda yang diambil sebanyak r objek adalah
=(
! )! !
(Ayres dan Schmidt, 2004).
