SubjectsSubjects(version: 837)
Course, academic year 2014/2015
  
Graphs in Engineering - N445044
Title in English: Grafy v inženýrství
Guaranteed by: Department of Computing and Control Engineering (445)
Actual: from 2013
Semester: summer
Points: summer s.:3
E-Credits: summer s.:3
Examination process: summer s.:
Hours per week, examination: summer s.:2/1 MC [hours/week]
Capacity: 30 / 30 (unknown)
Min. number of students: unlimited
Language: Czech
Teaching methods: full-time
Level:  
For type:  
Additional information: http://moodle.vscht.cz/course/view.php?id=117
Note: course can be enrolled in outside the study plan
enabled for web enrollment
Guarantor: Cejnar Pavel RNDr.
Annotation -
Last update: Cejnar Pavel RNDr. (30.07.2013)
The course concentrates on important problems from graph theory with emphasis on engineering applications. It deals with basic terms of graph theory, properties of various types of graphs and methods their numerical coding with aims on computational complexity of algorithms. It systematically goes over real-life graphs problems (large-scale sets of equations, numerical applications, engineering problems, tasks of operational research/analysis and decision-making problems) and presents effective algorithms of their solution.
Aim of the course -
Last update: Cejnar Pavel RNDr. (30.07.2013)

Students will be able to:

  • Extract the graph theory problems in industrial tasks.

  • Analyze the graph theory problems and solve them using efficient known graph algorithms.

  • Have an overview of many problems solvable by various graph algorithms.

  • Distinguish computationally intensive tasks among various graph theory problems.

Literature -
Last update: Cejnar Pavel RNDr. (25.04.2018)

A: Thulasiraman K., Swamy M. N. S.: Graphs: Theory and Algorithms. Wiley-Interscience, 1992. ISBN 978-0471513568.

A: West D. B.: Introduction to Graph Theory. Pearson, 2001. ISBN 978-0130144003.

A: Diestel R.: Graph Theory (Graduate Texts in Mathematics). Springer, 2010. ISBN 978-3642142789.

A: Christofides N.: Graph Theory. An Algoritmic Approach. Academic Press Inc, 1975. ISBN 978-0121743505.

Learning resources -
Last update: Cejnar Pavel RNDr. (30.07.2013)
  • electronic materials available at http://moodle.vscht.cz/course/view.php?id=117 (in Czech language)

Teaching methods -
Last update: Cejnar Pavel RNDr. (30.07.2013)

Lectures and courses.

Syllabus -
Last update: Cejnar Pavel RNDr. (30.07.2013)

1. Graphs, their terminology and basic definitions, graph description and coding

2. Time and storage complexity of algorithms, NP-complete problems

3. Directed and undirected acyclic graphs, topological ordering and finding a circle in a graph

4. Depth-first and breadth-first search in graphs, mutual reachability of nodes and its analysis

5. Bipartite graphs, matching in bipartite graphs and output mapping of equation set

6. Strong components, k-edge-connected graphs and irreducible subsystems of equation set

7. Graph condensation, hierarchical structure of a directed graph, computation sequencing

8. Planar graphs, their embedding into a plane, application in design of printed circuits and chips

9. Finding shortest path in graphs

10. Pipeline networks, spanning tree, search for independent circuits, minimization of pipe networks

11. Flow networks, maximum flow and minimum cut, transportation reserves, Eulerian path

12. General matching problems, critical path method

13. Discrete optimization, local and systematic search - principles of methods, constraint programming, branch-and-bound method

14. Examples of application in engineering and technology

Registration requirements -
Last update: Cejnar Pavel RNDr. (30.07.2013)
  • Mathematics I or any equivalent subject

  • one subject in the topic of computer programming (in any computer language)
Teaching methods
Activity Credits Hours
Účast na přednáškách 1 28
Příprava na přednášky, semináře, laboratoře, exkurzi nebo praxi 0,5 14
Práce na individuálním projektu 1 28
Účast na seminářích 0,5 14
3 / 3 84 / 84
Coursework assessment
Form Significance
Aktivní účast na výuce 40
Protokoly z individuálních projektů 60

 
VŠCHT Praha