|
|
Hlavní nabídka Prohlížení IS/STAG
Nalezené předměty, počet: 1
Stránkování výsledků vyhledávání
Nalezeno 1 záznamů
Export do Xls
Informace o předmětu
KMF / BTEGR
:
Popis předmětu
Pracoviště / Zkratka
|
KMF
/
BTEGR
|
Akademický rok
|
2023/2024
|
Akademický rok
|
2023/2024
|
Název
|
Teorie grafů
|
Způsob zakončení
|
Zkouška
|
Způsob zakončení
|
Zkouška
|
Akreditováno / Kredity
|
Ano,
5
Kred.
|
Forma zakončení
|
Kombinovaná
|
Forma zakončení
|
Kombinovaná
|
Rozsah hodin
|
Přednáška
2
[HOD/TYD]
Cvičení
2
[HOD/TYD]
|
Zápočet před zkouškou
|
Ano
|
Zápočet před zkouškou
|
Ano
|
Automatické uznávání zápočtu před zkouškou
|
Ne
|
Počítán do průměru
|
ANO
|
Vyučovací jazyk
|
Čeština
|
Obs/max
|
|
|
|
Automatické uznávání zápočtu před zkouškou
|
Ne
|
Letní semestr
|
53 / -
|
0 / 0
|
0 / 0
|
Počítán do průměru
|
ANO
|
Zimní semestr
|
0 / -
|
0 / -
|
0 / -
|
Opakovaný zápis
|
NE
|
Opakovaný zápis
|
NE
|
Rozvrh
|
Ano
|
Vyučovaný semestr
|
Letní semestr
|
Vyučovaný semestr
|
Letní semestr
|
Minimum (B + C) studentů
|
nestanoveno
|
Volně zapisovatelný předmět |
Ano
|
Volně zapisovatelný předmět
|
Ano
|
Vyučovací jazyk
|
Čeština
|
Počet dnů praxe
|
0
|
Počet hodin kontaktní výuky |
0
|
Hodnotící stupnice |
A|B|C|D|E|F |
Periodicita |
každý rok
|
Hodnotící stupnice pro zp. před zk. |
S|N |
Periodicita upřesnění |
|
Základní teoretický předmět |
Ano
|
Profilující předmět |
Ne
|
Základní teoretický předmět |
Ano
|
Hodnotící stupnice |
A|B|C|D|E|F |
Hodnotící stupnice pro zp. před zk. |
S|N |
Nahrazovaný předmět
|
KMF/ITEGR
|
Vyloučené předměty
|
Nejsou definovány
|
Podmiňující předměty
|
Nejsou definovány
|
Předměty informativně doporučené
|
Nejsou definovány
|
Předměty,které předmět podmiňuje
|
Nejsou definovány
|
Graf četnosti udělených hodnocení studentům napříč roky:
Obrázek PNG
,
XLS
|
Cíle předmětu (anotace):
|
Cílem předmětu je seznámit studenty s matematickým aparátem, přístupy a metodami teorie grafů jako jednoho ze základních teoretických nástrojů operačního výzkumu.
|
Požadavky na studenta
|
Účast na přednáškách, aktivní účast na cvičeních. Zvládnutí zápočtového a zkouškového testu na hranici minimálně 50 procent.
|
Obsah
|
1. Základní pojmy (základní pojmy z teorie grafů - neorientovaný a orientovaný graf, podgraf, nadgraf, doplněk grafu, speciální, historické poznámky, poznatky a úlohy vedoucí ke vzniku teorie grafů, typy grafů )
2. Maticová reprezentace grafů (datové struktury pro uložení grafů, matice přilehlosti, incidence a matice přímých vzdáleností)
3. Souvislost grafů (souvislost grafů, komponenta souvislosti, most, artikulace, číslo vrcholové a hranové souvislosti)
4. Izomorfismus (izomorfismus grafů, autokomplementární grafy)
5. Prohledávání labyrintu (algoritmus prohledávání labyrintu)
6. Nejkratší cesta (Dijsktrův a Floydův algoritmus pro určení nekratší cesty v grafu a distanční matice)
7. Cesta s maximální kapacitou (řezová množina, řez, cesta s maximální kapacitou )
8. Maximální dráha (algoritmus na určení maximální dráhy grafu)
9. Metoda kritické cesty (znázornění projektu orientovaným grafem, metoda kritické cesty, kritická cesta)
10. Toky na sítích (toky na rovinné stíti, nejvýše položená dráha, Fordův-Fulkersonův algoritmus pro obecné sítě, algoritmus na přiřazení pracovníků ke strojům )
11. Stromy a kostra grafu (strom, les, izolovaný vrchol, excentricita vrcholu, síla vrcholu, poloměr stromu, průměr stromu, centrum a centroid stromu, kostra grafu, algoritmus na určení minimální kostry grafu)
12. Eulerovský tah (Eulerovský tah, uzavřený tah minimální délky, Fleuryho a Edmondsův algoritmus)
13. Barvení grafu (rovinný graf, podmínky rovinnosti grafu, barvení grafu )
|
Aktivity
|
|
Studijní opory
|
|
Garanti a vyučující
|
|
Literatura
|
-
Základní:
Volek, Josef. Operační výzkum I. Pardubice: Univerzita Pardubice, 2002. ISBN 80-7194-410-6.
-
Doporučená:
Demel, J. Grafy a jejich aplikace. Academia, 2002. ISBN 80-200-0990-6.
-
Doporučená:
Nečas, Jiří. Grafy a jejich použití. Praha: Státní nakladatelství technické literatury, 1978.
-
Doporučená:
Balakrishnan, V. K.. Schaum's outline of theory and problems of graph theory. New York: McGraw-Hill, 1997. ISBN 0-07-005489-4.
-
Doporučená:
Nešetřil, J. Teorie grafů. SNTL, 1979.
|
Předpoklady - další informace k podmíněnosti studia předmětu |
Získání zápočtu z předmětu je podmíněno úspěšným absolvováním testu, elektronickým testem v systému Learn a aktivní účastí na cvičeních. Předmět je zakončen písemnou zkouškou. K absolvování je zapotřebí alespoň 50% úspěšnosti. |
Získané způsobilosti |
Student po absolvování předmětu ovládá základní definice, metody a algoritmy teorie grafů. Je schopen formulovat vybrané úlohy dopravní praxe, sestavit grafický model, vypočíst řešení a toto potom interpretovat pro praktické využití. |
Vyučovací metody |
- Monologická (výklad, přednáška, instruktáž)
- Metody samostatných akcí
- Demonstrace
- Nácvik dovedností
|
Hodnotící metody |
- Písemná zkouška
- Didaktický test
|
|
|
|