BAB PENDAHULUAN
1.1 Latar Belakang Penelitian Penelitian
mengenai eksponen digraf dwiwarna telah banyak dilakukan. Shader dan Suwilo
(2003) adalah yang pertama sekali melakukan penelitian tersebut. Pada tahun 2002
, Wielandt ( Schneizer,H ) melakukan penelitian mengenai eksponen matrik tak negatif.
Andaikan A adalah sebuah matriks tak negatif berordo n × n. Matriks tak negatif
A dikatakan primitif jika dan hanya jika terdapat bilangan bulat positif k sehingga
A k bernilai positif dan bilangan bulat terkecil k disebut sebagai eksponen dari
A.
Selanjutnya Digraf D(A) adalah
sejumlah titik yang terhubung dengan garis berarah (arc) pada setiap pasang
titik (v i , vj ) di D(A) jika dan hanya jika entri dari matriks tak negatif A,
yaitu a i,j > 0, untuk i, j = 1, 2, · · · , n. Digraf D(A) dikatakan terhubung
kuat jika untuk setiap pasang titik (v i , vj ) di D(A) terdapat walk dari v i ke
v j dan dari v j ke v i dengan i, j = 1, 2, · · · , n. Suatu digraf D(A)
dikatakan primitif jika dan hanya jika terdapat bilangan bulat positif l
sehingga untuk setiap pasangan titik (v i , vj ) terdapat walk dengan panjang l
, maka bilangan bulat terkecil l disebut sebagai eksponen dari digraf D(A) yang
dinotasikan sebagai exp(D) (Brualdi dan Ryser,1991). Eksponen titik dari
digraph D(A) adalah jumlah walk dengan panjang minimum l yang menghubungkan titik v k , k = 1, 2, · ·
· , n ke setiap titik di D(A), dinotasikan dengan expD(v k ).
Pada tahun 1997, Fornasini dan
Valcher mendefinisikan digraf dwiwarna sebagai berikut. Digraf dwiwarna D (2) merupakan
suatu digraf yang setiap arcnya diberi warna merah atau biru. Digraf dwiwarna D
(2) terhubung kuat dikatakan primitif jika
terdapat suatu bilangan bulat tak negatif m dan n dengan m + n > 0 sehingga untuk
setiap pasang titik (v i , vj ) di D (2) terdapat (m, n)-walk dari v i ke v j dan
walk dari v j ke v i , dengan m dan n masing-masing merupakan jumlah arc merah
dan arc biru, kemudian bilangan bulat positif terkecil dari m + n disebut
sebagai eksponen digraf dwiwarna D (2) yang dinotasikan dengan exp D (2)
(Shader dan Suwilo,2003).
Eksponen titik dari digraph
dwiwarna D (2) adalah jumlah walk dengan panjang minimum m + n yang
menghubungkan titik v k , k = 1, 2, · · · , n ke setiap titik di D (2) , untuk
m dan n
masing-masing adalah jumlah arc merah dan arc biru, dinotasikan dengan
exp D (2) (v k ).
Pada tahun 2009 Gao dan Shao
mulai memperkenalkan konsep eksponen lokal. Andaikan D (2) adalah sebuah digraf
dwiwarna primitif. Eksponen titik keluar dari digraf dwiwarna adalah bilangan
bulat positif terkecil g + h sehingga terdapat (g, h)-walk untuk setiap pasang
titik v k , k = 1, 2, · · · , n ke setiap titik di D (2) , dinotasikan dengan
expout D (2) (v k ) . Sedangkan eksponen titik masuk dari digraf dwiwarna adalah
bilangan bulat positif terkecil g + h sehingga terdapat (g , h )-walk
untuk setiap titik di D (2) ke titik v k di D (2) , dinotasikan dengan expin D (2)
(v k ) .
Bai dan Shao (2007) melakukan
penelitian menentukan eksponen dari kelas digraf dwiwarna dengan n-titik ganjil
dengan batasan eksponen serta karakteristik ekstermal dari digraf dwiwarna D (2)
yang primitif atas n-titik ganjil yang memiliki dua cycle yakni n-cycle dan (n + 1)-cycle. Sedangkan penelitian kali ini
meneruskan penelitian yang dilakukan oleh Bai dan Shao untuk menentukan
eksponen titik keluar dari digraf dwiwarna D (2) .
1.2 Perumusan Masalah Andaikan D (2)
adalah digraf dwiwarna yang primitif atas n-titik ganjil. Kemudian, mencari
bagaimana pola dari eksponen titik keluar untuk setiap titik v k pada ekstermal
digraf dwiwarna D (2) .
1.3 Tinjauan Pustaka Pada digraf dwiwarna, komponen terpenting dari
sebuah walk ditentukan oleh jumlah br merah dan br biru. Sebuah (h, k)-walk
adalah sebuah walk yang terdiri dari h buah br berwarna merah dan k buah br
berwarna biru. Andaikan w adalah sebuah walk dari digraf dwiwarna, dengan r(w)
adalah banyaknya br berwarna merah dari w dan b(w) adalah banyaknya br berwarna
biru. Sehingga vektor r(w)
b(w) disebut
sebagai komposisi dari w.
Andaikan D (2) adalah sebuah
digraf dwiwarna terhubung kuat dan C = {c
, c , ...., c t } adalah himpunan
semua cycle di D (2) . Sebuah matriks cycle dari D (2) adalah sebuah matriks 2
× t dalam bentuk S = r(c ) r(c )
... r(c t ) b(c ) b(c ) ... b(c t ) setiap kolom ke-i dengan i = 1, 2, ..., t dari matriks
tersebut adalah komposisi dari cycle c t. Fornansi Valcher (1997) memberikan
karakteristik secara aljabar bagi primitifitas digraf dwiwarna. Sebuah digraf
dwiwarna terhubung kuat adalah primitif jika dan hanya jika pembagi persekutuan
terbesar dari determinan submatriks 2 × 2 dari S adalah 1.
Penelitian mengenai eksponen
digraf dwiwarna dimulai oleh Shader dan Suwilo (2003). Pada penelitian tersebut
Shader dan Suwilo (2003) memperlihatkan bahwa
bila D (2) adalah digraf dwiwarna yang primitif atas n-titik, maka
eksponen terbesar D (2) terletak pada interval [ (n −
5n ),
(3n − 2n − 2n)].
Bai dan Shao (2007) melakukan
penelitian menentukan eksponen dari kelas digraf dwiwarna dengan n-titik ganjil
dengan batasan eksponen serta karakteristik ekstermal dari digraf dwiwarna D (2)
yang primitif atas n-titik ganjil yang memiliki cycle yakni n-cycle dan (n + 1)-cycle.
Gao dan Shao (2009) melakukan
penelitian menentukan eksponen lokal keluar dari titik-titik pada digraf
dwiwarna tipe Wiedlant. Gao dan Shao mendefinisikan eksponen lokal sebagai walk
dengan komposisi sama yang berasal dari satu titik tertentu dan menuju kesemua
titik lainnya. Suwilo (2011) menentukan eksponen lokal keluar dari titik-titik
pada digraf ministrong ekstermal dwiwarna, sedangkan Syahmarani dan Suwilo
(2012) menentukan eksponen lokal keluar dari digraf Hamilton dwiwarna dengan
eksponen terbesar dan dengan eksponen terkecil.
Penelitian kali ini bertujuan
untuk menentukan bentuk umum eksponen titik keluar dari ekstermal digraf
dwiwarna yang primitif atas n-titik ganjil dari tipe kedua dengan dua arc biru
berturut-turut pada penelitian yang dilakukan oleh Bai dan Shao.
Dalam hal ini terdapat dua
karakter posisi arc biru berturut-turut yaitu : 1. arc biru tepat berada pada
posisi arc v 2 → v dan arc v 1 → v n Gambar 1.1 : Karakter Pertama D (2) 2. arc
biru tepat berada pada posisi arc v (n+1)
→ v (n−1) dan arc v (n+3) → v (n+1) Gambar 1.2 : Karakter Kedua D (2) 1.4
Tujuan Penelitian Tujuan dari penelitian ini adalah menentukan bentuk umum
eksponen titik keluar dari digraf dwiwarna yang primitif dengan n-titik ganjil
dan dua arc biru berturutturut berdasarkan warna arc.
1.5 Manfaat Penelitian Penelitian ini dilakukan untuk memperkaya
literature dan menambah pengetahuan mengenai eksponen digraf dwiwarna dengan
n-titik ganjil yang primitif.
Skripsi Matematika:Eksponen Titik Keluar Dari Sebuah Kelas Digraf Dwiwarna Primitif Atas n-Titik
Download lengkap Versi PDF
 | ||
| ||
| ||
| ||
|