Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Graf

Definice

Graf je dvojice , kde je množina bodů (vrcholů) a množina jejich dvojic (hran). Je-li množinou neuspořadaných dvojic, jde o neorientovaný graf. Jsou-li dvojice uspořádané, jedná se o orientovaný graf. Velikost množiny se značí , velikost je - , .

Graf je možné strojově reprezentovat např. pomocí matice sousednosti - matice, kde je na souřadnicích hodnota , pokud z do je hrana a 0 jinak. Pro neorientované grafy je souměrná podle hlavní osy. Matice zabírá místa v paměti. Další možností jsou seznamy sousedů - dvě pole, jedno příslušné vrcholům, druhé hranám. V prvním jsou uložené indexy do druhého pole, určující kde začínají seznamy hran vedoucích z vrcholu (příslušejícímu k indexu v prvním poli). Paměťová náročnost je .