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: matice|graf|rozložitelnost|řídká matice
• English key words: matrix|graph|reducibility|sparse matrix
• Academic year of topic announcement: 2024/2025
• Thesis type: Bachelor's thesis
• Department: Department of Numerical Mathematics (32-KNM)
• Supervisor: prof. Ing. Miroslav Tůma, CSc.
• Author: 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

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.