User Tools
Site Tools
Sidebar
teorie_grafu
This is an old revision of the document!
Table of Contents
graf
- = grafické vyjádření vztahů mezi objekty
- incidence = místu vstupu nebo výstupu hrany, vztah hrany s uzlem
- definice grafu
- graf je trojice G={H, U, ρ), kde:
- H je množina hran H={h1, h2, …, hn}
- U je množina uzlů U={u1, u2, …, um}
- ρ je indicenční funkce, která je dána předpisem:
- pro neorientovaný graf
- H → U ⊗ U (množina všech neuspořádaných dvojic prvků z množiny U)
- pro orientovaný graf
- H → U × U (kartézský součin - množina všech uspořádaných dvojic prvků z množiny U)
- kostra grafu
- libovolný podgraf spojující hranami všechny vrcholy původního grafu
- sám neobsahuje žádnou kružnici
- izomorfní graf
- něco s bijekcí (najdu si to!!!!)
- mají stejný počet vrcholů i hran
- hrany
- orientovaná, neorientovaná, násobné hrany, rovnoběžné hrany (jaký je rozdíl mezi násobnou a rovnoběžnou???, smyčka
- ohodnocená, neohodnocená
- vzdálenost, průchodnost, kapacita hrany pro přenos (informace, komodity)
typy grafů
podle smyček a rovnoběžných hran
- jednoduchý graf (obyčejný graf)
- nemá ani smyčky ani násobné hrany
- multigraf
- obsahuje násobné hrany (tzn. když jsou dva uzly spojeny více hranami) i smyčky
- pseudograf (prostý graf)
- obsahuje smyčky
podle orientace
- orientovaný
- všechny hrany jsou orientované
- vyjadřuje jednostranné (nesymetrické) vztahy mezi uzly
- neorientovaný
- všechny hrany jsou neorientované
- vyjadřuje oboustranné vztahy
- např. sourozenci
- smíšený
- obsahuje orientované i neorientované hrany
- v praxi se nepoužívá (spíš se nahradí orientovanými hranami - opačné směry)
podle souvislosti
- souvislé
- musí ∃ cesta mezi každou dvojicí vrcholů
- nesouvislé
podle ∃ kružnice v grafu
- cyklické
- acyklické
nakreslím ho do roviny bez křížení hran?
- rovinné
- nerovinné
souvislost grafu
- kružnice je uzavřená cesta
- z každého sledu lze vybrat cestu
- v souvislém grafu existuje cesta mezi každou dvojicí jeho uzlů
sled
- taková posloupnost vrcholů, že mezi každými po sobě dvěma jdoucími je hrana
- prostě to musí být spojení
tah
- sled, kde není žádná hrana víc než jedenkrát
uzavřený tah
- končí tam kde začal. tak jak my.
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
- každá uzavřená cesta
cyklus
- uzavřená orientovaná cesta
reprezentace grafů
diagramem
definicí
maticí
- v hlavní diagonále jsou nuly (uvažujeme obyčejný graf bez smyček)
- u neorientovaného grafu je symetrická podle hlavní diagonály
datovými strukturami
strom
- souvislý graf
- neobsahuje kružnici
- mezi každými dvěma vrcholy existuje právě jedna cesta
- je to datová struktura
Permalink teorie_grafu.1484251275.txt.gz · Last modified: by efox
oeffentlich
