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ů

## Reprezentace grafu

Definice (Nakreslení)

Graf lze reprezentovat např. jeho nakreslením - lze si pod tím představit i grafické znázornění na papír. Formální definici nakreslení provedeme v sekci o rovinných grafech.

Definice (Matice sousednosti)

Mějme graf s vrcholy Matice sousednosti grafu je čtvercová matice řádu definovaná předpisem

(Po umocnění matice sousednosti představuje číslo počet sledů délky z vrcholu do vrcholu v grafu )

Definice (Matice vzdáleností)

Pro grafy s ohodnocenými hranami lze zkonstruovat matici vzdáleností -- je to matice sousednosti, do které se v případě, že hrana existuje, ukládá místo jedničky její ohodnocení.

Definice (Laplaceova matice)

(Na hlavní diagonále je stupeň vrcholu, kde vede hrana, tam je -1, jinde 0. )

Poznámka

Laplaceovu matici lze použít mj. k výpočtu počtu koster grafu, jak uvidíme v následující sekci.

Definice (Matice incidence)

Řádky matice odpovídají vrcholům, sloupce odpovídají hranám. Prvek matice se rovná , pokud v tomto vrcholu začíná daná hrana, pokud tam tato hrana končí, 0 jinak. Neorientované grafy mají u obou vrcholů hrany hodnotu .

Definice (Seznam sousedů)

Pomocí dvou polí; v jednom čísla všech následníků, v druhém poli indexy určující, kde začíná sekvence sousedů daného vrcholu.

Definice (Seznam hran)

Pole s prvky o dvou složkách, zaznamenávají se do něj hrany ve formě obou jejich vrcholů; pro orientované grafy lze stanovit, že první složka bude reprezentovat počáteční a druhá koncový vrchol hrany.