ZÁKLADNÍ POJMY

Question 1

Obyčejný graf

Answer 1

uspořádaná dvojice (V,E) kde V je neprázdná množina vrcholů a E je množina hran, přičemž hrana e z E je dvojprvková podmnožina množiny V.

Question 2

Obyčejný konečný graf

Answer 2

Množiny V a E jsou konečné, počet prvků V zn. |V| a počet prvků E zn. |E|

Question 3

Koncové vrcholy v, w hrany v e / vrcholy incidentu s hranou e

Answer 3

e = {v,w}, vrchol v nazýváme SOUSEDNÍM vrcholem vrcholu w a naopak

Question 4

Stupeň vrcholu v

Answer 4

číslo rovnající se počtu hran incidentních s vrcholem v
deg g (v)

Question 5

Počet vrcholů lichého stupně

Answer 5

vždy sudý

Question 6

PRINCIP SUDOSTI

Answer 6

Pro každý graf G=(V, E) platí vztah Σ v∈V deg g (v)= 2*|E|

D: Stupeň vrcholu v udává počet hran grafu G obsahujících vrchol v. Každá hrana obsahuje 2 vrcholy. Sečteme li všechny stupně dostaneme dvojnásobný počet hran.

Důsledek: Počet vrcholů lichého stupně je vždy sudý.

Question 7

SKÓRE GRAFU

Answer 7

Nechť G=(V, E) je graf s n vrcholy v1, v2,…,vn

Skóre grafu je posloupnost (dg(v1), dg(v2), …., dg(vn))

Question 8

VĚTA O SKÓRE GRAFU

Answer 8

Nechť D =(d1, d2,… , dn) je posloupnost ℕ čísel.
Předpokládejme, že d1 ≤ d2≤ … ≤ dn a označme D’posloupnost (d1’, d2’, … ,dn-1’)
kde di’= di pro i

Question 9

Úplný graf

Answer 9

Na množině v vrcholů je graf s vrcholy n≥1 ve kterém je každý vrchol spojen se všemi ostatními vrcholy grafu hranou
zn: Kn
Graf Kn má n(n-1)/2 hran

Question 10

Doplněk -G = (V, -E)

Answer 10

grafu G=(V, E) je graf, jehož množina hran -E je množina všech těch hran úplného grafu na mn. vrcholů V, které neleží v E

Question 11

MOST

Answer 11

hrana e je most grafu G, jestliže G-e má více komponent, než G
Hrana grafu je buď most, nebo leží na kružnici

Question 12

ARTIKULACE

Answer 12

vrchol v je artikulace G, jestliže G-v má více komponent než graf G
Vrchol stupně 1 nikdy není artikulací
Pokud vrcholy mezi kterými je most mají více než 1 stupeň, jsou ARTIKULACE

Question 13

2-souvislý graf

Answer 13

Souvislý graf, který neobsahuje artikulaci

- každý úplný graf je 2-souvislý, odebráním libovolného vrcholu neporušíme souvislost

Question 14

BLOK GRAFU (2-souvislá komponenta)

Answer 14

je každý jeho 2-souvislý podgraf

tj. 2-souvislý podgraf, který není podrazem žádného jiného 2-souvislého podgrafu

Question 15

KOMPONENTA

Answer 15

Komponenta grafu je maximální souvislý podgraf, t.j. v tomto podgrafu najdeme cestu z vrcholu a do vrcholu b pro jakékoliv vrcholy a, b v podgrafu.

Question 16

IZOMORFISMUS

Answer 16

Graf G = (V, E) je izomorfní s grafem G’ = (V’, E’), jestliže existuje vzájemně jednoznačné
zobrazení f: V –> V’ takové, že platí {v, w} ∈ E <==> { f {v}, f {w}} ∈ E’.

tj: dva izomorfní grafy jsou stejné, až na pojmenování vrcholů.

MAJÍ STEJNÉ:
1, počet vrcholů, hran
2, skóre
3, kružnici dané délky
4, doplněk
5, pod grafy indukované množinou vrcholů stejného stupně

Question 17

NESOUVISLÝ GRAF

Answer 17

mezi každými 2 vrcholy není cesta

Question 18

Komponenta grafu

Answer 18

KAŽDÝ jeho maximální souvislý podgraf, tj. souvislý podgraf, který není podgrafem žádného jiného souvislého podgrafu

Question 19

SLED DÉLKY k

Answer 19

Sled v grafu je posloupnost vrcholů taková, že mezi každými dvěma po sobě jdoucími je hrana.
Posloupnost hran, které na sebe navazují, se nazývá sled.

Question 20

TAH DÉLKY k

Answer 20

Sled, ve kterém se neopakuje žádná hrana se nazývá tah.

Question 21

CESTA DÉLKY k

Answer 21

Tah, ve kterém se naopakuje žádný vrchol se nazývá cesta.

V grafu G existuje cesta z vrcholu v do w <==> v G existuje sled z vrcholu v do w

Question 22

Kružnice délky k

Answer 22

tedy uzavřené posloupnosti propojených vrcholů. Kružnice může být orientovaná i neorientovaná.