Teorie grafů - OKB2310255

• Anglický název: Graph Theory
• Zajišťuje: Katedra matematiky a didaktiky matematiky (41-KMDM)
• Fakulta: Pedagogická fakulta
• Platnost: od 2011 do 2018
• Semestr: zimní
• E-Kredity: 2
• Způsob provedení zkoušky: zimní s.:
• Rozsah, examinace: zimní s.:0/0, Z [HS]
• Rozsah za akademický rok: 4 [hodiny]
• Počet míst: neurčen / neurčen (50)
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: kombinovaný
• Způsob výuky: kombinovaný
• Poznámka: předmět je možno zapsat mimo plán; povolen pro zápis po webu; při zápisu přednost, je-li ve stud. plánu
• Garant: prof. RNDr. Ladislav Kvasz, DSc., Dr.
• Vyučující: doc. RNDr. Jaroslav Zhouf, Ph.D.
• Třída: Matematika 1. cyklus - povinné
• Kategorizace předmětu: Matematika > Matematika, Algebra, Diferenciální rovnice, teorie potenciálu, Didaktika matematiky, Diskrétní matematika, Matematická ekonomie a ekonometrie, Předměty širšího základu, Finanční a pojistná matematika, Funkční analýza, Geometrie, Předměty obecného základu, , Reálná a komplexní analýza, Matematika, Matematické modelování ve fyzice, Numerická analýza, Optimalizace, Pravděpodobnost a statistika, Topologie a kategorie
• Je korekvizitou pro: OKB1310004

Anotace

čeština

Cílem semináře seznámit studenty se základyními pojmy a metodami teorie grafů. Základními probíranými pojmy budou pojem grafu, isomorfismus grafů, různé způsoby zadávání grafů, stromy, úplné grafy, kostra grafu, rovinné grafy, pojem cesty, Eulerovské grafy, pojem kružnice, Hamiltonovské grafy, barvení grafů, algoritmy na grafech. Doporučená literatura je: Bosák: Grafy a ich aplikácie (Alfa, Bratislava 1980), Sedláček: Úvod do teorie grafů (Academia, Praha 1981), Fuchs: Diskrétní matematika pro učitele (MU Brno, 2001) a Matoušek a Nešetřil: Kapitoly z diskrétní matematiky (UK Praha, 2003).

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)

angličtina

The aim of the seminar is to make students acquainted with the basic notions and methods of graph theory, such as isomorphism of graphs, different ways of introducing a graph, trees, complete graphs, skeleton, planar graphs, paths in a graph, Euler graphs, hamiltonian graphs, graph coloring, graph algorithms. Recommended literature: Bosák: Grafy a ich aplikácie (Alfa, Bratislava 1980), Sedláček: Úvod do teorie grafů (Academia, Praha 1981), Fuchs: Diskrétní matematika pro učitele (MU Brno, 2001) a Matoušek a Nešetřil: Kapitoly z diskrétní matematiky (UK Praha, 2003).

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)

slovenština

Cieľom seminára je oboznámiť študentov so základnými pojmami a metódami teórie grafov. Základnými preberanými pojmami budú pojem grafu, izomorfizmus grafov, rôzne spôsoby zadávania grafov, stromy, úplné grafy, kostra grafu, rovinné grafy, pojem cesty, Eulerovské grafy, pojem kružnice, Hamiltonovské grafy, farbenie grafov, algoritmy na grafoch. Doporučená literatúra je: Bosák: Grafy a ich aplikácie (Alfa, Bratislava 1980), Sedláček: Úvod do teorie grafů (Academia, Praha 1981), Fuchs: Diskrétní matematika pro učitele (MU Brno, 2001) a Matoušek a Nešetřil: Kapitoly z diskrétní matematiky (UK Praha, 2003).

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)

Cíl předmětu

čeština

Cílem předmětu je seznámit studenty učitelství matematiky se základy teorie grafů, na několika vybraných tématech ukázat specifické způsoby myšlení v tomto oboru. Bude zdůrazněna motivace praktickými problémy a účinnost jejich řešení.

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)

angličtina

The aim of the seminar is to make students of mathematics education acquainted with the basic notions and techniques of graph theory. On some selected themes the specific methods of argumentation and proofs in graph theory will be illustrated. The motivation by practical problems will be put into the foreground and the effectiveness of graph-theoretical methods will be shown.

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)

Literatura

čeština

§ Vrba: Grafy - učebnice pro gymnázia se zaměřením na matematiku, SPN 1989

§ Nešetřil: Teorie grafů, SNTL, Praha 1979

§ Matoušek, Nešetřil: Kapitoly z Diskrétní Matematiky, Matfyzpress, Praha, 2000

§ Sedláček: Úvod do teorie grafů Academia, Praha 1981,

§ Fuchs: Diskrétní matematika pro učitele MU Brno, 2001

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)

Metody výuky

angličtina

At the seminar we will present standard problems and on the solution of these problems we will illustrate the fundamental notions and methods of graph theory. Thus a rather concrete approach, close to problem solving will be used.

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)

slovenština

Na seminári sa budú riešiť štandardné problémy a na ich riešení sa budú ilustrovať jednotlivé pojmy a vety teórie grafov.

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)

Požadavky ke zkoušce

Účast ve výuce, závěrečný test.

Poslední úprava: ZHOUF/PEDF.CUNI.CZ (09.11.2011)

Sylabus

čeština

Hlavní témata:

§ Definice základních pojmů (obecné grafy a speciální případy: úplný graf, kružnice, cesta, strom, bipartitní graf). Skóre grafu.

§ Souvislost grafu, vzdálenost v grafu, uzavřené tahy, Hamiltonova kružnice, Eulerovy grafy.

§ Reprezentace grafu: matice sousednosti, matice incidence.

§ Nezávislost grafu, teorie kódování.

§ Kreslení grafů, rovinné grafy a mapy, barvení grafu.

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)

angličtina

Main topics:

§ Definition of the basic concepts (graph, complete graph, circle, path, tree). The score of a graph.

§ Connected graphs, distance in graphs, closed paths, Hamiltonian circle, Eulerian graphs.

§ Representations of a graph: matrix of neighbourhood, matrix of incidence.

§ Independence of a graph, the theory of coding.

§ Planar graphs, maps, graph colouring, the four colour problem.

Poslední úprava: JANCARIK/PEDF.CUNI.CZ (04.06.2010)