Course detail

Theory of Graphs

FAST-HA53Acad. year: 2013/2014

Various types of graphs and their applications. Basic structures defined for graphs used for their classification. Tractable and intractable combinatorial problems as modelled by graphs. Essential algorithms used to solve graph problems. Theory of NP-completeness.

Language of instruction

Czech

Number of ECTS credits

2

Mode of study

Not applicable.

Guarantor

RNDr. Karel Mikulášek, Ph.D.

Department

Institute of Mathematics and Descriptive Geometry (MAT)

Learning outcomes of the course unit

After completing the course, students will be acquainted with the basics of the theory of graphs. They will also be able to use the knowledge acquired to find solutions to problems they may come across as engineers or businessmen.

Prerequisites

Basics of combinatorics as taught at secondary schools. Symbol processing.

Co-requisites

Not applicable.

Planned learning activities and teaching methods

The course is taught through practical classes and self-study assignments. Attendance at practical classes is compulsory.

Assesment methods and criteria linked to learning outcomes

To obtain credit for the course, student swill have to submit solutions to three problems in the graph theory assigned to them. If they achieve at least 50 points out of a maximum of 100 and have no unexcused absences, they will be credited for the course.

Course curriculum

1. Definition of graphs, digraphs, multigraphs. Examples.
2. Path in a graph, contiguous graphs, component of a graph. Trees.
3. Homomorfism and isomorfism of graphs. Eulerian and Hamiltonian graphs, applications.
4. Colourability of graphs, independence of graphs. Planar graphs, the Kuratowski theorem. Problem of four colours.
5. Essential combinatorial problems. A good characteristic of a problem.
6. Tractable problems on graphs I.
7. Tractable problems on graphs II.
8. Travelling salesman problem, branch and bound method, heuristic methods.
9. NP-complete problems.
10. Revision.

Work placements

Not applicable.

Aims

After the course, students should be acquainted with the basics of the theory of graphs. They should also be able to apply the knowledge acquired when dealing with problems they may come across as engineers or businessmen.

Specification of controlled education, way of implementation and compensation for absences

Extent and forms are specified by guarantor’s regulation updated for every academic year.

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Nešetřil, J.: Teorie grafů. SNTL, 1978.
Gross, Y; Yellen, J: Graph Theory. CRC Press, 1999.

Recommended reading

Not applicable.

Classification of course in study plans

  • Programme N-P-C-GK Master's

    branch G , 1. year of study, summer semester, elective

Type of course unit

 

Exercise

26 hours, compulsory

Teacher / Lecturer

RNDr. Karel Mikulášek, Ph.D.

Syllabus

1. Definition of directed and undirected graphs.
2. Special undirected graphs, subgraphs, graph connectivity.
3. Trees.
4. Homomorphisms and isomorphisms of graphs.
5. Digraphs, tournaments.
6. Eulerian graphs, Hamiltonian graphs.
7. Chromatic number of a graph, planar graphs, plane graphs.
8. Spanning tree of a graph, minimum spanning tree problem, Kruskal's algorithm.
9. Dijkstra and Warshall-Floyd algorithms for finding shortest paths in graphs.
10. Flow in a network. Ford Fulkerson algorithm for finding maximum flow.
11. Problems solvable in polynomial time and NP complete problems.
12. Heuristic algorithms, travelling salesman problem.
13. Revision, reserve.