Gurantor department | Department of Applied Mathematics | Credits | 6 |

Subject guarantor | doc. Mgr. Petr Kovář, Ph.D. | Subject version guarantor | doc. Mgr. Petr Kovář, Ph.D. |

Study level | undergraduate or graduate | Requirement | Optional |

Year | 1 | Semester | summer |

Study language | Czech | ||

Year of introduction | 2003/2004 | Year of cancellation | 2009/2010 |

Intended for the faculties | FEI | Intended for study types | Follow-up Master, Master |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

KOV16 | doc. Mgr. Petr Kovář, Ph.D. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Credit and Examination | 2+2 |

Combined | Credit and Examination | 10+10 |

Each student is supposed to
- analyze real life problems
- express them as a graph theory problem
- solve the problem using graph theory methods
- give an interpretation of the theoretical results in the terms of the original problems
At the same time he should decide what are the limits of an ideal theoretical solution in contrast to the real situation.

Lectures

Individual consultations

Tutorials

Project work

The course covers both basic and advanced topics of Graph Theory, often overlapping with other branches of mathematics (algebra, combinatorics).
In the course are many real life problems solved by the methods of graph theory.

D. Fronček: Úvod do teorie grafů, Slezská univerzita Opava, (1999).
J. Matoušek, J. Nešetřil, Chapters in Discrete Mathematics, Karolinum Praha (2000).

D. B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001).

During the semester each student prepares one or two projects.
Topic of each project is chosen among topics presented in the lecture.
The sumbission date and all assignments are available in the university electronic information system.
(Each student has to register for a topic.)
For a pass it is necessary to have at least one project graded for at least 10 points.

Subject has no prerequisities.

Subject has no co-requisities.

Lectures:
1) Graphs, simple graphs. Graph isomorphisms. Incidence matrix and adjacency matrix. Subgraphs. Degree of a vertex. Paths and cycles.
2) Trees, bridges and cuts. Connectivity and blocks.
3) Matching and covers in general and bipartite graphs. Perfect matchings.
4) Edge colorings. Chromatic index, Vizing's Theorem.
5) Vertex colorings, Chromatic number, Brook's Theorem.
6) Planar graphs. Dual graphs, Euler's formula for connected planar graphs, Kuratowski's Theorem. Four Folor Theorem.
7) Eulerian and Hamiltonian graphs.
8) Oriented graphs. Oriented paths and cycles.
9) Flows in networks, cuts. Maximal flow and minimal cut Theorem.
Discussions:
1) Graphs, simple graphs. Degree of a vertex. Paths and cycles. Important graph classes.
2) Trees, bridges and cuts. Connectivity, blocks and articulations.
3) Graph connectivity.
4) Matching and covers in general and bipartite graphs. Perfect matchings.
5) Edge colorings. Chromatic index.
6) Vertex colorings, Chromatic number.
7) Planar graphs. Euler's formula for general planar graphs.
8) Eulerian and Hamiltonian graphs.
9) Oriented graphs. Oriented paths and cycles.

Task name | Type of task | Max. number of points
(act. for subtasks) | Min. number of points |
---|---|---|---|

Exercises evaluation and Examination | Credit and Examination | 100 (100) | 51 |

Examination | Examination | 80 | 41 |

Exercises evaluation | Credit | 20 | 10 |

Show history

Academic year | Programme | Field of study | Spec. | Form | Study language | Tut. centre | Year | W | S | Type of duty | |
---|---|---|---|---|---|---|---|---|---|---|---|

2009/2010 | (N2647) Information and Communication Technology | (1103T031) Computational Mathematics | P | Czech | Ostrava | 1 | Optional | study plan | |||

2009/2010 | (N2647) Information and Communication Technology | (1103T031) Computational Mathematics | K | Czech | Ostrava | 1 | Optional | study plan | |||

2008/2009 | (N2647) Information and Communication Technology | (1103T031) Computational Mathematics | P | Czech | Ostrava | 1 | Optional | study plan | |||

2008/2009 | (N2647) Information and Communication Technology | (1103T031) Computational Mathematics | K | Czech | Ostrava | 1 | Optional | study plan | |||

2007/2008 | (N2647) Information and Communication Technology | (1103T031) Computational Mathematics | P | Czech | Ostrava | 1 | Optional | study plan | |||

2007/2008 | (N2647) Information and Communication Technology | (1103T031) Computational Mathematics | K | Czech | Ostrava | 1 | Optional | study plan | |||

2006/2007 | (N2647) Information and Communication Technology | (1103T031) Computational Mathematics | P | Czech | Ostrava | 1 | Optional | study plan | |||

2006/2007 | (N2647) Information and Communication Technology | (1103T031) Computational Mathematics | K | Czech | Ostrava | 1 | Optional | study plan | |||

2005/2006 | (N2646) Information Technology | (1103T021) Computational Mathematics | P | Czech | Ostrava | 2 | Choice-compulsory | study plan | |||

2005/2006 | (N2646) Information Technology | (1103T021) Computational Mathematics | K | Czech | Ostrava | 2 | Choice-compulsory | study plan | |||

2004/2005 | (N2646) Information Technology | (1103T021) Computational Mathematics | P | Czech | Ostrava | 2 | Choice-compulsory | study plan | |||

2004/2005 | (N2646) Information Technology | (1103T021) Computational Mathematics | K | Czech | Ostrava | 2 | Choice-compulsory | study plan |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|