|
Lecturer(s)
|
-
Rak Josef, RNDr. Ph.D.
-
Pozdílková Alena, Mgr. Ph.D.
|
|
Course content
|
Lecture topics by week of the semester: 1. Basics of graph theory (undirected and directed graph, subgraph, supergraph, graph complement, special, historical notes, knowledge and tasks leading to the use the graph theory, types of graphs) 2. Matrix representation of graphs (data structures for storing graphs, adjacency, incidence and direct distance matrices) 3. Connected graphs (connected graph, component of connection, bridge, articulation, number of vertex and edge connection) 4. Isomorphism (isomorphism of graphs, autocomplementary graphs) 5. Labyrinth search (labyrinth search algorithm) 6. Shortest path (Dijsktr and Floyd's algorithm for determining the shortest path in a graph and a distance matrix) 7. Path with maximum capacity (section set, section, path with maximum capacity) 8. Maximal path (algorithm for determining the maximal path of a graph) 9. Critical path method (representation of the project by an oriented graph, critical path method, critical path) 10. Flows on networks (flows on a planar graphs, highest path, Ford-Fulkerson algorithm for general networks, algorithm for assigning workers to machines) 11. Trees and spanning tree (tree, forest, isolated vertex, vertex eccentricity, vertex strength, tree radius, tree diameter, tree center and centroid, spanning tree, algorithm for determining the minimal spanning tree) 12. Eulerian trail (Eulerian trail, closed trail of minimal length, Fleury and Edmonds algorithm) 13. Graph coloring (planar graph, conditions of planar graphs, graph coloring) The content of the exercises corresponds to the topics of the lectures.
|
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing), Methods of individual activities, Demonstration, Skills training
- Contact teaching
- 52 hours per semester
- Home preparation for classes
- 38 hours per semester
- Preparation for a credit (assessment)
- 30 hours per semester
- Preparation for an exam
- 30 hours per semester
|
|
Learning outcomes
|
The aim of the course is to introduce with the mathematical apparatus, approaches and methods of graph theory to students. Graph theory is one of the basic theoretical tools of operations research.
After completing the course, the student understands the basic definitions, methods and algorithms of graph theory. He is able to formulate selected tasks of transport practice, make a graphic model, calculate a solution and then interpret it for practical use.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Written examination, Didactic test
Attendance at lectures, active participation in seminars. Passing the credit and exam test at the limit of at least 50 percent.
|
|
Recommended literature
|
-
BALAKRISHNAN, V. K. Schaum's Outline of Theory and Problems of Graph Theory. Schaum's Outline Series. New York: McGraw-Hill, 1997. ISBN 0-07-005489-4.
-
DEMEL, Jiří. Grafy a jejich aplikace. Praha: Academia, 2002. ISBN 80-200-0990-6.
-
NEČAS, Jiří. Grafy a jejich použití. Polytechnická knižnice. Řada 2. Příručky, sv. 90. Praha: Státní nakladatelství technické literatury, 1978.
-
NEŠETŘIL, Jaroslav. Teorie grafů. Praha: Státní nakladatelství technické literatury, 1979.
-
VOLEK, Josef. Operační výzkum I. Vyd. 2., nezm. Pardubice: Univerzita Pardubice, 2008. ISBN 978-80-7395-073-6.
|