Poznámky: Podgrafy a jejich konstrukce
Skrýt detaily | Oblíbený- Kvalita:83,3 %
- Typ:Poznámky
- Univerzita:České vysoké učení technické v Praze
- Fakulta:Fakulta dopravní
- Kategorie:Technika
- Podkategorie:Doprava a spoje
- Předmět:Teorie grafů a její aplikace v dopravě
- Autor:blackmagic
- Ročník:3. ročník
- Rozsah A4:9 strán
- Zobrazeno:1 268 x
- Stažené:0 x
- Velikost:1,1 MB
- Formát a přípona:MS Office Word (.doc)
- Jazyk:český
- ID projektu:6921
- Poslední úprava:09.11.2015
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.