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ů

## Stromy a jejich základní vlastnosti

Definice (Strom, list)

Strom je souvislý graf neobsahující kružnici. List (koncový vrchol) je vrchol stupně 1.

Věta

Počet stromů na -vrcholové množině je

Věta (Charakterizace stromů)

Pro graf jsou následující podmínky ekvivalentní:

1. je strom.
2. Pro každé dva vrcholy existuje právě jedna cesta z do (jednoznačnost cesty)
3. Graf je souvislý a vynecháním libovolné hrany vznikne nesouvislý graf. (minimální souvislost)
4. Graf neobsahuje kružnici a každý graf vzniklý z přidáním hrany již kružnici obsahuje. (maximální graf bez kružnic)
5. je souvislý a
6. je acyklický a

Definice (Kostra grafu)

Kostra grafu je strom, který je podgrafem a obsahuje všechny vrcholy grafu .

Věta (Počet koster)

Počet koster grafu je kde je matice, která vznikne odstraněním -tého řádku a -tého sloupce z Laplaceovy matice charakterizující graf.

??? Dukaz