Muhammad, Suef (2018) Modifikasi Dekomposisi Dulmage-Mendelsohn Pada Matriks Persegi Reguler Tereduksi Atas Aljabar Max-Plus. Masters thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
06111650010018-Master_Thesis.pdf - Accepted Version Download (697kB) | Preview |
Abstract
Matriks blok segitiga atas merupakan suatu bentuk dari matriks persegi yang diperoleh dengan melakukan permutasi pada baris dan kolomnya, hal ini dapat dijelaskan secara umum menggunakan dekomposisi Dulmage-Mendelsohn. Dalam penelitian tesis ini, dilakukan modifikasi pada algoritma
dekomposisi Dulmage-Mendelsohn sehingga diperoleh bentuk matriks blok segitiga atas yang semua blok diagonalnya merupakan matriks persegi. Kemudian untuk mencari matching maksimum pada graf bipartisi digunakan algoritma matching maksimum yang memperhatikan banyaknya garis penghubung disetiap titiknya. Algoritma ini memiliki waktu komputasi lebih cepat dibanding dengan algoritma matching maksimum yang memperhatikan eksistensi augmenting path pada graf bipartisi. Matriks A dengan kardinalitas matching maksimumnya sama dengan banyak elemen diagonalnya yang taknol memiliki bentuk matriks blok segitiga atas hasil dekomposisi Dulmage-Mendelsohn termodifikasi yaitu Ā = PAP^T. Matriks blok segitiga atas Ā ini digunakan untuk menganalisis terkait vektor waktu-sikel dari matriks persegi reguler tereduksi A atas aljabar max-plus, dimana vektor waktu-sikel ini sangat erat kaitannya dengan nilai eigen dan eigenmode dari matriks A.=====================================================================================The upper block-triangular matrix is a square matrix which is obtained by
permutation process on its rows and columns, it could be explained generally by using Dulmage-Mendelsohn decomposition. In this research, modification was done on Dulmage-Mendelsohn decomposition algorithm so that the form of the upper block-triangular matrix was obtained which all diagonal blocks were square matrices. Then to find the maximum matching on the bipartite graph we use the algorithm that respect to the number of connecting edge at each vertices. This algorithm has a faster computation time than the algorithm that respect to the existence of augmenting path in the bipartite graph. The matrix A with cardinality maximum matching is the same as the number of diagonal elements whose nonzero has a upper block-triangular matrix form of the modified Dulmage-Mendelsohn decomposition result was Ā = PAP^T. Thisupper block-triangular matrix Ā was used to analyze the cycle-time vector ofthe reducible regular square matrix A over max-plus algebra, where this cycle-time vector was closely related to eigenvalues and eigenmode from the matrix
A.
| Item Type: | Thesis (Masters) |
|---|---|
| Additional Information: | RTMa 516.35 Sue m |
| Uncontrolled Keywords: | dekomposisi Dulmage-Mendelsohn, aljabar max-plus, vektor waktu-sikel, eigenmode |
| Subjects: | Q Science > QA Mathematics > QA159 Algebra |
| Divisions: | Faculty of Mathematics, Computation, and Data Science > Mathematics > 44101-(S2) Master Thesis |
| Depositing User: | Muhamad Suef |
| Date Deposited: | 27 Jan 2021 03:10 |
| Last Modified: | 27 Jan 2021 03:10 |
| URI: | http://repository.its.ac.id/id/eprint/58863 |
Actions (login required)
 |
View Item |