Hledej
Zobraz:
Univerzity
Kategorie
Rozšířené vyhledávání
12 659 projektů
0 nových
Podgrafy a jejich konstrukce
«»
| Přípona .doc |
Typ poznámky |
Stažené 0 x |
| Velikost 1,1 MB |
Jazyk český |
ID projektu 6921 |
| Poslední úprava 09.11.2015 |
Zobrazeno 1 269 x |
Autor: blackmagic |
Sdílej na Facebooku |
||
| Detaily projektu | ||
- Cena:
2 Kreditů - kvalita:
83,3% -
Stáhni
- Přidej na srovnání
- Univerzita:České vysoké učení technické v Praze
- Fakulta:Fakulta dopravní
- Kategorie:Technika » Doprava a spoje
- Předmět:Teorie grafů a její aplikace v dopravě
- Studijní obor:-
- Ročník:3. ročník
- Formát:MS Office Word (.doc)
- Rozsah A4:9 stran
1.1 Kostra grafu
Kostra grafu G = (V, X) je graf T = (W, Y) | W = V, Y c X, který je stromem. V každém souvislém neorientovaném grafu existuje alespoň jedna kostra. V grafu s n vrcholy má každá kostra právě n-1 hran.
V hranově ohodnocených grafech definujeme minimální a maximální kostru grafu. Minimální kostrou souvislého hranově ohodnoceného grafu je kostra, pro kterou je součet ohodnocení hran minimální. Analogicky maximální kostrou grafu je kostra s maximálním součtem ohodnocení hran.
Kostra grafu G = (V, X) je graf T = (W, Y) | W = V, Y c X, který je stromem. V každém souvislém neorientovaném grafu existuje alespoň jedna kostra. V grafu s n vrcholy má každá kostra právě n-1 hran.
V hranově ohodnocených grafech definujeme minimální a maximální kostru grafu. Minimální kostrou souvislého hranově ohodnoceného grafu je kostra, pro kterou je součet ohodnocení hran minimální. Analogicky maximální kostrou grafu je kostra s maximálním součtem ohodnocení hran.
Klíčová slova:
konstrukce
eulerovské tahy
podgrafy
konstrukce. algoritmus
Obsah:
- 1 PODGRAFY A JEJICH KONSTRUKCE
1.1 Kostra grafu
1.2 Sestrojení kostry grafu
1.2.1 Sestrojení minimální/maximální kostry grafu postupným výběrem hran (princip J.B.Kruskala)
1.2.2 Sestrojení minimální/maximální kostry grafu pomocí množin sousedů (Jarníkův-Primův princip)
1.3 Eulerovské tahy
1.3.1 Problém 7 mostů města Královce
1.3.2 Fleuryho algoritmus
1.4 Edmondsův algoritmus
1.5 Hamiltonovské kružnice
1.5.1 Heuristický algoritmus určení hamiltonovské kružnice v kompletním grafu