|
Lecturer(s)
|
-
Rak Josef, RNDr. Ph.D.
-
Marek Jaroslav, Mgr. Ph.D.
-
Hořeňovská Veronika, Ing.
|
|
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
|
he 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
Given assignment confirms that a student has attended lessons to the extent required and fulfilled qualified requirements. Conditions for credit are: active work at exercises, min. 75% presence, 2 examination papers, student passes if he/she obtains 50 points of 100 possible. Form, contents and length of the exam is determined in accordance with Study and Examining Rules of University of Pardubice. The exam consists of two parts, a written test and a theoretical exam. Student passes successfully the written test as well as the theoretical part of the exam if he/she obtains at minimum 50% of possible points in each part.
|
|
Recommended literature
|
-
Demel, J. Grafy a jejich aplikace. Academia, 2002. ISBN 80-200-0990-6.
-
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.
-
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.
|