Sistem Linear Tipe Titik-Tetap di Dalam Dioid Topologis dan Aplikasinya untuk Menyelesaikan Masalah Lintasan Terpendek

NUR CHOLIS, Ari Suparwanto, M.Si., Dr.

2015 | Skripsi | S1 MATEMATIKA

Suatu semiring (E, oplus, otimes) disebut dioid apabila E terurut secara kanonik terhadap operasi oplus, yaitu E adalah suatu himpunan terurut dengan relasi urutan kanonik lebih-kecil-sama-dengan yang dibangun oleh operasi oplus. Himpunan E dapat dilengkapi dengan Sup-topologi. Jika setiap barisan non-decreasing yang terbatas ke atas di dalam E konvergen ke batas atas terkecilnya dan pengambilan limitnya kompatibel terhadap operasi oplus dan otimes, maka (E, oplus, otimes) disebut dioid topologis. Didefinisikan sistem linear tipe titik-tetap di dalam dioid topologis dengan bentuk Y = Y otimes A oplus B di mana A anggota Mn(E) dan B anggota Emxn (m bilangan bulat 1 lebih-kecil-sama-dengan m lebih-kecil-sama-dengan n). Misalkan A star adalah limit dari A(k) = I oplus A oplus A2 oplus ... oplus Ak untuk k menuju tak hingga. A star disebut quasi-inverse dari matriks A. Jika A star ada dan memenuhi A star = I oplus A otimes A star = I oplus A star otimes A, maka Y = B otimes A star adalah solusi minimal dari sistem linear dengan bentuk Y = Y otimes A oplus B. Di sisi lain, suatu graf G(A) dapat berasosiasi dengan suatu matriks A anggota Mn(E). Sebaliknya, matriks A dapat dipandang sebagai (generalisasi) matriks ikatan dari suatu graf bernilai G(A). Akan ditunjukkan bahwa sistem linear tipe titik-tetap di dalam dioid topologis dapat digunakan untuk menyelesaikan beberapa permasalahan di dalam teori graf, khususnya masalah lintasan terpendek.

A semiring (E, oplus, otimes) is called dioid if E is canonically ordered with respect to oplus, i.e. E is an ordered set by the canonical order relation less-than-equal induced by oplus. We can endow E with the Sup-topology. If every non-decreasing sequence bounded from above in E is convergent to its least upper bound and taking the limit is compatible with the two laws oplus and otimes of the dioid, then (E, oplus, otimes) is called topological dioid. A linear system of the fixed-point type in topological dioids is given by the form Y = Y otimes A oplus B where A in Mn(E) and B in Emxn (m integer 1 less-than-equal m less-than-equal n). Let A star is the limit of A(k) = I oplus A oplus A2 oplus ... oplus Ak for k towards infinity. A star is called the quasi-inverse of matrix A. If A star exists and satisfies A star = I oplus A otimes A star = I oplus A star otimes A, then Y = B otimes A star is the minimal solution for the linear system of the form Y = Y otimes A oplus B. In other hand, a graph G(A) can be associated with a matrix A in Mn(E). Conversely, a matrix A can be considered as a (generalized) adjacency matrix of the valued graph G(A). We will show that the linear system of the fixed-point type in topological dioids can be used to solve some problems in graph theory, especially to solve the shortest path problems.

Kata Kunci : Dioid Topologis, Sistem Linear, Titik-Tetap, Quasi-Inverse