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ů

## Základní pojmy teorie grafů, reprezentace grafu

Definice (Graf)

Graf je uspořádaná dvojice , kde je nějaká množina a je množina dvouprvkových podmnožin množiny (takže neuspořádaných dvojic). Prvky množiny se jmenují vrcholy grafu a prvky množiny hrany grafu

Definice (Orientovaný graf)

je dvojice kde je podmnožina kartézského součinu . Prvky (tj. uspořádané dvojice prvků z ) nazýváme orientované hrany grafu.

Definice (Symetrizace grafu)

Orientovanému grafu přiřadíme neorientovaný graf kde Graf se nazývá symetrizace grafu (Z orientovaného grafu se odstraní údaje o směru hran.)

Definice (Důležité typy grafů)

- úplný graf : (Každý vrchol je spojen hranou s každým např. -- pentagram.)
- kružnice : (V kružnici se nesmí opakovat vrcholy.)
- cesta : (Jako kružnice, ale bez poslední hrany.)
- bipartitní graf: , ; v úplném bipartitním grafu je (Každý vrchol z jedné partity je spojen hranou pouze s některými (v úplném z každým) vrcholem druhé partity. Např. , úplný bipartitní graf na 3 a 3 vrcholech.)

Definice (Sled, tah)

Pro graf definujeme sled jako posloupnost kde pro Tah je sled, ve kterém se žádná hrana neopakuje.

Definice (Isomorfismus grafů)

Dva grafy považujeme za isomorfní (značíme ), pokud se liší jen v označení vrcholů a hran, tj. pokud existuje vzájemně jednoznačné zobrazení tak, že platí

Definice (Podgraf, indukovaný podgraf)

Graf je podgrafem grafu jestliže a . Pro indukovaný podgraf grafu platí, že a (Indukovaný podgraf dostaneme vymazáním některých vrcholů původního grafu a všech hran tyto vrcholy obsahujících.)

Definice (Souvislost)

Neorientovaný graf je souvislý, jestliže mezi každými jeho dvěma vrcholy v něm existuje cesta. Pro orientované grafy definujeme slabou souvislost -- po symetrizaci se z něj stane souvislý neorientovaný graf -- a silnou souvislost -- každé dva vrcholy lze spojit orientovanou cestou v obou směrech.

Poznámka

Pro orientované grafy není samotný pojem souvislost definován.

Definice (-souvislost)

Graf je vrcholově -souvislý, pokud má alespoň vrcholů a po odebrání libovolných vrcholů dostaneme vždy souvislý graf. Podobně (přes odebírání hran) definujeme hranovou -souvislost.

Poznámka

Vrcholová -souvislost je silnější podmínka než hranová -souvislost, protože při odebírání vrcholů můžeme (a většinou musíme) odebrat více než hran.

Definice (Komponenta souvislosti)

Komponenta souvislosti grafu je jeho maximální souvislý podgraf. (Sjednocením všech komponent grafu dostaneme původní graf).

Definice (Most)

Most je hrana, která neleží ve 2-souvislém podgrafu (po jejím odstranění se zvětší počet komponent).

Definice (Blok)

Blok je maximální vrcholově 2-souvislý podgraf grafu. Samotný graf o 2 vrcholech spojených jednou hranou je také blok. (2-souvislý podgraf, ke kterému se nedá přidat žádný vrchol, protože by přestal být 2-souvislý.)

Definice (Artikulace)

Artikulace je vrchol souvislého grafu takový, že není souvislý.

Definice (Blokový graf)

je graf incidence (sousednosti) bloků a artikulací -- artikulacím a blokům odpovídají vrcholy, hrany značí incidenci bloků a artikulací.

Věta

Blokový graf souvislého grafu je strom.

Definice (Hranové pokrytí)

Množinu v grafu nazveme hranovým pokrytím, pokud každý vrchol je obsažen alespoň v jedné hraně

Definice (Stupeň vrcholu)

Stupeň vrcholu, je počet hran grafu obsahujících vrchol V případě orientovaného grafu rozlišujeme vstupní stupeň vrcholu, což je počet vstupních hran, podobně výstupní stupeň vrcholu.

Definice (Párování)

Každá množina vzájemně disjunktních hran v grafu se nazývá párování.

Definice (k-faktor grafu)

k-faktor je podgraf grafu takový, že

Poznámka (1-faktor grafu)

1-faktor je vlastně párování na všech vrcholech (úplné párování).

Věta (Princip sudosti)

Definice (Skóre grafu)

Skóre grafu je posloupnost stupňů vrcholů grafu, přičemž nezáleží na pořadí, v jakém jsou uváděny.

Věta (Věta o skóre)

Nechť je posloupnost přirozených čísel. Předpokládejme, že a označme symbolem posloupnost kde

Potom je skóre grafu, právě když je skóre grafu. (Jakoby odebereme poslední vrchol () a myslíme si, že byl propojen s předchozími vrcholy.)

Důkaz

Jedna implikace je triviální, druhá (máme skóre grafu - a tedy k němu nějaký graf a dokazujeme, že je taky skóre grafu ) není o moc těžší - přepojíme hrany tak, aby z vrcholu šly právě do a odebereme.

Definice (Metrika grafu)

Pro souvislý graf definujeme metriku jako funkci kde číslo představuje délku nejkratší cesty z do Funkce má následující vlastnosti (tj. splňuje axiomy metriky, jak ji známe z metrických prostorů):

1. a
2. (symetrie)
3. (trojúhelníková nerovnost)

Definice (Některé grafové operace)

Nechť je graf. Definujeme

- odebrání hrany: kde je hrana grafu G
- přidání nové hrany: kde je dvojice vrcholů, která není hranou v
- odebrání vrcholu: kde (odebereme vrchol a všechny hrany do něj zasahující)
- dělení hrany: kde je hrana a je nový vrchol (na hranu přikreslíme nový vrchol ).

Řekneme, že graf je dělení grafu G, pokud je isomorfní grafu vytvořenému z grafu postupným opakováním operace dělení hrany.