Párování v bipartitních grafech a LU faktorizace
| Thesis title in Czech: | Párování v bipartitních grafech a LU faktorizace |
|---|---|
| Thesis title in English: | Bipartite graph matching and LU factorization |
| Key words: | párování|bipartitní graf|LU faktorizace|řídká matice |
| English key words: | matching|bipartite graph|LU factorization|sparse matrix |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Numerical Mathematics (32-KNM) |
| Supervisor: | prof. Ing. Miroslav Tůma, CSc. |
| Author: | Bc. Eliška Kurečková - assigned and confirmed by the Study Dept. |
| Date of registration: | 14.10.2024 |
| Date of assignment: | 16.10.2024 |
| Confirmed by Study dept. on: | 26.10.2024 |
| Date and time of defence: | 27.06.2025 08:30 |
| Date of electronic submission: | 07.05.2025 |
| Date of submission of printed version: | 07.05.2025 |
| Date of proceeded defence: | 27.06.2025 |
| Opponents: | doc. RNDr. Iveta Hnětynková, Ph.D. |
| Guidelines |
| Souvislost grafů a matic, obecněji grafů a lineární algebry je jedním z hlavních strůjců velkého pokroku
v řešení soustav rovnic, které vznikají v mnoha inženýrských i přírodovědných aplikacích. Tato souvislost umožňuje dobře zachytit maticovou strukturu, použít v řešení klasické grafové algoritmy i nalézat nové postupy v řešení. Jednou z užitečných souvislostí je vztah mezi párováním v grafech na jedné straně a LU rozkladem, který se používá k řešení soustav lineárních rovnic s obecně nesymetrickou maticí. Práce bude zaměřena na základní orientaci v této souvislosti a jejím použitím v LU faktorizaci či i jejím dalším zobecněním. |
| References |
|
R. Brualdi, H. Ryser: Combinatorial matrix theory, Cambridge University Press, 1991 M. Fiedler: Speciální matice v numerické matematice, SNTL, 1981 J. Kepner, J. Gilbert (eds): Graph algorithms in the language of linear algebra, SIAM, Philadelphia, 2011 J. Scott, M. Tůma: Algorithms for sparse linear systems, Birkhauser, 2023 |
| Preliminary scope of work |
| Práce k bližšímu pochopení souvislostí mezi grafy a maticemi s případnou algoritmickou aplikací. |
| Preliminary scope of work in English |
| Thesis towards better understanding of relations between graphs and matrices, possibly with an algorithmic application. |