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)
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é
- nesouvislé
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
tah
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
Permalink teorie_grafu.1484148463.txt.gz · Last modified: by efox
oeffentlich
