Předmět Graph algorithms (KMA / WGRAA)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMA / WGRAA - Graph algorithms, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
Programme of the course1.BASIC TERMINOLOGY: graphs and their properties, setting graphs, important types of subgraphs ? path, sequence, component, factor, spanning tree of a graph, regular graphs.2.BASIC GRAPH ALGORITHMS: terminology of graph algorithms. Marking algorithms, Backtracking, searching for the shortest path.3.BASIC GRAPH ALGORITHMS: shortest path search in a weighted graph, searching for the maximum spanning tree of a graph, determining the number of spanning trees, using a matrix of sequence.4.MATCHING: Matching in general graphs.5.MATCHING: Matching in bipartite graphs.6.EULERIAN GRAPHS: Eulerian graphs, the role of the Chinese postman.7.HAMILTONIAN GRAPHS: Hamiltonian paths and circles (in general).8.HAMILTONIAN GRAPHS: Finding the shortest undirected Hamiltonian path and circle.9.HROMATICITY INDEPENDENCE, CLIQUES: Basic terminology for determining the chromaticity of a graph.10.CHROMATICITY INDEPENDENCE, CLIQUES: Combinatorial terminology and relationships. Finding maximal independent sets.11.NETWORKS AND NETWORK FLOWS: basic terminology, marking procedure.12.NETWORKS AND NETWORK FLOWS: algorithm for maximum flow, algorithm for permissible circulation.13.Possibility to take the credit test at this earlier date or re-sit the test attempted during the semester.
Literatura
Gross, J.; Yellen, J. Graph theory and its applications. London, New York: CRC Press, 1998.
Požadavky
The examination consists of several pieces of written homework and a final test in the examination period. The evaluation of the course including the classification is carried out in accordance with the Study and Examination Regulations OU.
Garant
RNDr. Petra Konečná, Ph.D.
Vyučující
RNDr. Petra Konečná, Ph.D.RNDr. Petra Konečná, Ph.D.