User Tools
Site Tools
teorie_grafu
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
teorie_grafu [2017/01/12 21:36] efox [úlohy] |
teorie_grafu [2017/09/21 16:31] (current) efox |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | <WRAP center round tip 60%> | ||
| + | základní pojmy, klasifikace, | ||
| + | </ | ||
| + | |||
| ====== graf ====== | ====== graf ====== | ||
| * http:// | * http:// | ||
| * = grafické vyjádření vztahů mezi objekty | * = grafické vyjádření vztahů mezi objekty | ||
| + | * = dvojice disjunktních množin uzlů (vrcholů, vertex-vertices) a hran (edge-edges), | ||
| * {{:: | * {{:: | ||
| * **incidence** = místu vstupu nebo výstupu hrany, vztah hrany s uzlem | * **incidence** = místu vstupu nebo výstupu hrany, vztah hrany s uzlem | ||
| Line 13: | Line 18: | ||
| * pro orientovaný graf | * pro orientovaný graf | ||
| * H -> U × U (kartézský součin - množina všech uspořádaných dvojic prvků z množiny U) | * H -> U × U (kartézský součin - množina všech uspořádaných dvojic prvků z množiny U) | ||
| + | |||
| + | {{ :: | ||
| * **kostra grafu** | * **kostra grafu** | ||
| * libovolný podgraf spojující hranami všechny vrcholy původního grafu | * libovolný podgraf spojující hranami všechny vrcholy původního grafu | ||
| Line 72: | Line 79: | ||
| ===== tah ===== | ===== tah ===== | ||
| * sled, kde není žádná hrana víc než jedenkrát | * sled, kde není žádná hrana víc než jedenkrát | ||
| + | * sled, kde se neopakují hrany | ||
| ===== uzavřený tah ===== | ===== uzavřený tah ===== | ||
| * končí tam kde začal. tak jak my. | * končí tam kde začal. tak jak my. | ||
| ===== cesta ===== | ===== cesta ===== | ||
| - | * je sled, ve kterém se neopakují vrcholy, tedy každý vrchol se v cestě objevuje nejvýše jednou. Existuje-li mezi dvěma vrcholy sled v grafu, existuje mezi nimi i cesta | + | * je sled, ve kterém se neopakují vrcholy |
| + | * tedy každý vrchol se v cestě objevuje nejvýše jednou. Existuje-li mezi dvěma vrcholy sled v grafu, existuje mezi nimi i cesta | ||
| ===== kružnice ===== | ===== kružnice ===== | ||
| * každá uzavřená cesta | * každá uzavřená cesta | ||
| Line 92: | Line 101: | ||
| * počet hran mezi dvěma sousedními uzly | * počet hran mezi dvěma sousedními uzly | ||
| * vím | * vím | ||
| + | * {{:: | ||
| ===== datovými strukturami ===== | ===== datovými strukturami ===== | ||
| ===== matematicky ===== | ===== matematicky ===== | ||
| Line 99: | Line 109: | ||
| * matice sousednosti má UZLY a UZLY v X i Y | * matice sousednosti má UZLY a UZLY v X i Y | ||
| * tohle to má nahoře HRANY a vlevo UZLY | * tohle to má nahoře HRANY a vlevo UZLY | ||
| + | * {{:: | ||
| * **matice dosažitelnosti** | * **matice dosažitelnosti** | ||
| * je jenom dole pod diagonálou | * je jenom dole pod diagonálou | ||
Permalink teorie_grafu.1484253388.txt.gz · Last modified: 2017/01/12 21:36 by efox
oeffentlich
