|
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 the 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 them with approaches and clarify methods and their applications in transportation, communication and information systems.
After passing the course the students will have mastered the basic definitions, methods and algorithms of Graph Theory, they will be able to define selected problems of transportation practice as Theory of Graphs tasks, design graphic model, calculate the solution and interpret the issues of the solution.
|
|
Prerequisites
|
Knowledge of basic knowledge of finite math, theory of set and mathematical programming.
|
|
Assessment methods and criteria
|
Oral examination, Written examination
By awarding course credit it is confirmed that the students have fulfiled the required attendance as well as other qualifying requirements. Conditions for awarding the course credit are: active work at seminars, min. 75% presence, 2 examination papers. Student passes the exam if he/she obtains 50 of 100 possible points. Form, contents and length of the exam are determined in accordance with the Study and Examination Regulations of University of Pardubice. The exam consists of two parts, a written test and a theoretical oral exam. Student passes the exam if he/she obtains at the minimum 50% of possible number of points in each part.
|
|
Recommended literature
|
-
Bertsekas, Dimitri P. Network optimization : continuos and discrete models. Belmont: Athena Scientific, 1998. ISBN 1-886529-02-7.
-
Demel, J. Grafy a jejich aplikace. Academia, 2002. ISBN 80-200-0990-6.
-
Christofides, N.:. Graph Theory - an Algorithmic Approach.. New York: Academic Press, 1975. ISBN 0-12-174350-0.
-
Nečas, J. Grafy a jejich použití. Polytechnická knižnice, SNTL, 1978.
-
Nešetřil, J. Teorie grafů. SNTL, 1979.
-
Sedláček, J. Kombinatorika v teorii a praxi. Nakladatelství ČSAV, 1964.
-
Tutte, W. T. Graph Theory. Addison-Wesley Publishing Company, 1984. ISBN 0-521-30241-2.
-
Volek, Josef. Operační výzkum I. Pardubice: Univerzita Pardubice, 2002. ISBN 80-7194-410-6.
|