|
Lecturer(s)
|
|
|
|
Course content
|
Motivation, Operational Research - Definition, Basic Mathematical Apparatus, Historical Remarks, Classification of Disciplines, the Role of the Theory of Graphs, Key Problems and Authors. Basic Definitions, Classification of Graphs, Operations with Graphs, Graphs and their Mathematical Representation. Undirected and Directed Graphs. Common and Different Features. Connected Graphs, Chains, Routes and Paths. Labyrinth, Theseus, Ariadne and Minotaurus Story. Important Paths in Graphs, the Shortest Path Problem. Maximum Capacity Path, Maximum Reliability Path. Maximum path, Networks Analysis. Critical Path Method (CPM). Programme Evaluation Research Task (PERT). Graphs and Flows, the Max-Flow Problem, Ford-Fulkerson Theorem, Transportation Problem. Location Analysis, Continuous and Discrete Location, Location in Transportation Networks. Euler and Hamiltonian Cycles. Fleury's and Edmond's algorithms. Travel Salesman's Problem, Little Algorithm. Planar Graphs, Kuratowski Theorem, Colouring Graphs. Trees, Skeleton of Graph.
|
|
Learning activities and teaching methods
|
|
Monologic (reading, lecture, briefing), Demonstration, Projection, Skills training
|
|
Learning outcomes
|
The main goal of discipline is to familiarise students with the basic mathematical apparatus and terminology of Theory of Graphs as one of the basic disciplines of operational research, acquaint with approaches and clarify methods and their applications in transportation, communication and information systems.
Successful pasing of the subject means that student mastered fundamental definitions, methods and algorithmus of Graphs Theory.
|
|
Prerequisites
|
The basics of finite mathematics, set theory and mathematic programming are presumed.
|
|
Assessment methods and criteria
|
Oral examination, Written examination
The condition for granting the credit is active participation in the exercises and passing the credit test. The course ends with an exam. Active participation can be replaced by elaboration of individual work. Credit test can be done electronically.
|
|
Recommended literature
|
-
Demel, Jiří. Grafy a jejich aplikace. Praha: Academia, 2002. ISBN 80-200-0990-6.
-
Nečas, Jiří. Grafy a jejich použití. Praha: Státní nakladatelství technické literatury, 1978.
-
Nešetřil, Jaroslav. Teorie grafů. Praha: Státní nakladatelství technické literatury, 1979.
-
Sedláček, Jiří. Kombinatorika v teorii a praxi : úvod do teorie grafů. Praha: Československá akademie věd, 1964.
-
V. Balakrishnan. Schaum's Outline of Graph Theory: Including Hundreds of Solved Problems.
-
Volek, Josef. Operační výzkum I. Pardubice: Univerzita Pardubice, 2002. ISBN 80-7194-410-6.
|