Párování v bipartitních grafech a LU faktorizace

• Název práce v češtině: Párování v bipartitních grafech a LU faktorizace
• Název v anglickém jazyce: Bipartite graph matching and LU factorization
• Klíčová slova: matice|graf|rozložitelnost|řídká matice
• Klíčová slova anglicky: matrix|graph|reducibility|sparse matrix
• Akademický rok vypsání: 2024/2025
• Typ práce: bakalářská práce
• Ústav: Katedra numerické matematiky (32-KNM)
• Vedoucí / školitel: prof. Ing. Miroslav Tůma, CSc.
• Řešitel: Eliška Kurečková - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 14.10.2024
• Datum zadání: 16.10.2024
• Datum potvrzení stud. oddělením: 26.10.2024

Zásady pro vypracování

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.

Seznam odborné literatury

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

Předběžná náplň práce

Práce k bližšímu pochopení souvislostí mezi grafy a maticemi s případnou algoritmickou aplikací.

Předběžná náplň práce v anglickém jazyce

Thesis towards better understanding of relations between graphs and matrices, possibly with an algorithmic application.