SISTEM LINEAR TIPE TITIK-TETAP DI DALAM DIOID TOPOLOGIS DAN APLIKASINYA UNTUK MENYELESAIKAN MASALAH LINTASAN TERPENDEK; THE LINEAR SYSTEM OF THE FIXED-POINT TYPE IN TOPOLOGICAL DIOIDS AND ITS APPLICATION TO SOLVE THE SHORTEST PATH PROBLEMS

NUR CHOLIS, Ari Suparwanto

2015 | Skripsi | PROGRAM STUDI S1 MATEMATIKA

Suatu semiring (E, ?, ?) disebut dioid apabila E terurut secara kanonik terhadap operasi ?, yaitu E adalah suatu himpunan terurut dengan relasi urutan kanonik ? yang dibangun oleh operasi ?. 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 ? dan ?, maka (E, ?, ?) disebut dioid topologis. Didefinisikan sistem linear tipe titik-tetap di dalam dioid topologis dengan bentuk Y = Y ? A ? B di mana A ? Mn(E) dan B ? Em×n (m bilangan bulat 1 ? m ? n). Misalkan A? adalah limit dari A(k) = I ? A ? A2 ? ... ? Ak untuk k ? ?. A? disebut quasi- inverse dari matriks A. Jika A? ada dan memenuhi A? = I ? A ? A? = I ? A? ? A, maka Y = B ? A? adalah solusi minimal dari sistem linear dengan bentuk Y = Y ? A ? B. Di sisi lain, suatu graf G(A) dapat berasosiasi dengan suatu matriks A ? 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.

Kata Kunci : SISTEM LINEAR TIPE TITIK-TETAP,DIOID TOPOLOGIS