Tato práce byla sepsána především pro studenty bakalářského studia, kteří se seznamují s teorií grafů. V práci se počítá se znalostí základních pojmů a metod lineární algebry, veškeré použité pojmy z teorie grafů jsou vysvětleny. V práci je představeno několik problémů teorie grafů, jako počítání koster grafu, počítání trojúhelníků, nebo sledů určité délky v grafu a hledání izomorfismu dvou grafů. K řešení těchto problémů jsou využity zejména prostředky lineární algebry.
Anotace v angličtině
This thesis was created primarily for bachelor students who are being introduced to graph theory. The thesis assumes knowledge of the basic concepts and methods of linear algebra, all the concepts used from graph theory are explained. Several problems from graph theory are introduced in the thesis, such as counting spanning trees, counting triangles or sequences of a certain length in a graph and finding isomorphisms of two graphs. These problems are primarily solved using the techniques of linear algebra.
Klíčová slova
počet koster, počet trojúhelníků v grafu, počet sledů, izomorfismus grafů, matice sousednosti
Klíčová slova v angličtině
spanning trees count, number of triangles in graph, number of sequences, graph isomorphism, adjacency matrix
Rozsah průvodní práce
82
Jazyk
CZ
Anotace
Tato práce byla sepsána především pro studenty bakalářského studia, kteří se seznamují s teorií grafů. V práci se počítá se znalostí základních pojmů a metod lineární algebry, veškeré použité pojmy z teorie grafů jsou vysvětleny. V práci je představeno několik problémů teorie grafů, jako počítání koster grafu, počítání trojúhelníků, nebo sledů určité délky v grafu a hledání izomorfismu dvou grafů. K řešení těchto problémů jsou využity zejména prostředky lineární algebry.
Anotace v angličtině
This thesis was created primarily for bachelor students who are being introduced to graph theory. The thesis assumes knowledge of the basic concepts and methods of linear algebra, all the concepts used from graph theory are explained. Several problems from graph theory are introduced in the thesis, such as counting spanning trees, counting triangles or sequences of a certain length in a graph and finding isomorphisms of two graphs. These problems are primarily solved using the techniques of linear algebra.
Klíčová slova
počet koster, počet trojúhelníků v grafu, počet sledů, izomorfismus grafů, matice sousednosti
Klíčová slova v angličtině
spanning trees count, number of triangles in graph, number of sequences, graph isomorphism, adjacency matrix
Zásady pro vypracování
Cílem práce je představit aplikace lineární algebry na řešení vybraných úloh teorie grafů.
Postup práce:
v literatuře vyhledat problémy a úlohy teorie grafů, které lze řešit prostředky lineární algebry
vyložit partie teorie grafů užité při formulaci a řešení vybraných problémů
přehledně zpracovat řešení vybraných problémů s využitím prostředků lineární algebry
Zásady pro vypracování
Cílem práce je představit aplikace lineární algebry na řešení vybraných úloh teorie grafů.
Postup práce:
v literatuře vyhledat problémy a úlohy teorie grafů, které lze řešit prostředky lineární algebry
vyložit partie teorie grafů užité při formulaci a řešení vybraných problémů
přehledně zpracovat řešení vybraných problémů s využitím prostředků lineární algebry
Seznam doporučené literatury
1. GODSIL, C. D., ROYLE, G. F. 2001. Algebraic graph theory. New York: Springer. 2. KUČERA, L., NEŠETŘIL, J. 1989. Algebraické metody diskrétní matematiky. Praha: Státní nakladatelství technické literatury, Teoretická knižnice inženýra.
3. MATOUŠEK, J. 2010. Thirty-three miniatures: mathematical and algorithmic applications of linear algebra. Providence, R.I.: American Mathematical Society.
4. MATOUŠEK, J., NEŠETŘIL, J. 2002. Kapitoly z diskrétní matematiky. 3. vyd. Praha: Karolinum.
Seznam doporučené literatury
1. GODSIL, C. D., ROYLE, G. F. 2001. Algebraic graph theory. New York: Springer. 2. KUČERA, L., NEŠETŘIL, J. 1989. Algebraické metody diskrétní matematiky. Praha: Státní nakladatelství technické literatury, Teoretická knižnice inženýra.
3. MATOUŠEK, J. 2010. Thirty-three miniatures: mathematical and algorithmic applications of linear algebra. Providence, R.I.: American Mathematical Society.
4. MATOUŠEK, J., NEŠETŘIL, J. 2002. Kapitoly z diskrétní matematiky. 3. vyd. Praha: Karolinum.