Předmět Graph Theory (KMF / ZTEGR)

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 KMF / ZTEGR - Graph Theory, Fakulta elektrotechniky a informatiky, Univerzita Pardubice (UPa).

Materiál	Typ	Datum	Počet stažení

Obsah

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.

Získané způsobilosti

Successful pasing of the subject means that student mastered fundamental definitions, methods and algorithmus of Graphs Theory.

Literatura

Volek, J. Operační výzkum I. Pardubice, 2002. ISBN 80-7194-410-6.Demel, J. Grafy a jejich aplikace. Academia, 2002. Nečas, J. Grafy a jejich použití. Polytechnická knižnice, SNTL, 1978. Sedláček, J. Kombinatorika v teorii a praxi. Nakladatelství ČSAV, 1964. Nešetřil, J. Teorie grafů. SNTL, 1979.

Požadavky

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.

Garant

RNDr. Josef Rak, Ph.D.

Vyučující

RNDr. Josef Rak, Ph.D.RNDr. Josef Rak, Ph.D.