Sidang Tugas Akhir

Lukman Hakim Podungge
G05400039

Penentuan Ketaktereduksian Matriks Taknegatif dan Keprimitifan Matriks Taktereduksi dengan Menggunakan Digraf

Penetuan ketaktereduksian matriks tak negatif dan keprimitifan matriks taktereduksi dapat ditentukan dengan menggunakan digraf (directed graf/graf berarah) yang berpadan. Suatu matriks segi tak negatif dikatakan berpadanan dengan suatu digraf atau sebaliknya, jika matriks adjacency dari digraf memiliki pola nol yang sama dengan matriks taknegatif tersebut. Langkah pertama yang harus dilakukan ketika ingin menetukan ketaktereduksian suatu matriks taknegatif dengan menggunakan digraf adalah denganmembuat suatu digraf yang bepadanan. Kemudian digraf tersebut dipeiksa apakah conected atau tidak conected. Matriks taknegatif adlah taktereduksi jika dan hanya jika digraf yang berpadanan adalah conected. Apabila suatu matriks taknegatif adalah matriks taktereduksi, selanjutnya akan ditentukan keprimitifan dari matriks taktereduksi tersebut. Keprimitifan suatu matriks taktereduksi bergantung pada indeks ketakprimitifannya. Jika indeks ketakprimitifannya sama dengan satu, maka matriks taktereduksi adalah primitif. Jika indeks ketakprimitifannya lebih besar atau sama dengan satu, maka matriks taktereduksi adalah matriks takprimitif. Indeks ketakprimitifan pada matriks taktereduksi adalah sama dengan indeks ketakprimitifan dari digraf yang berpadanan. Indeks ketakprimitifan pada suatu digraf didefinisikan sebagai pembagi bersama terbesar (greatest common divisor/gcd) dari panjang semua cycle yang melalui salah satu simpul pada digraf tersebut. Jika gcd dari panjang semua cycle yang melalui salah satu simpul pada digraf yang berpadanan adalah satu, maka matriks taktereduksi yang berpadanan adalah matriks primitif. Tetapi, jika gcd dari panjang semua cycle yang melalui salah satu simpul pada digraf yang berpadanan adalah lebih besar dari satu, maka matriks taktereduksi yang berpadanan adalah matriks takprimitif.