pojmy

Question 1

Neorientovaný graf

Answer 1

Hrany neorientovaného grafu nemají danou orientaci. Tudíž výrazy (x, y) a (y, x) označují stejnou hranu.

Question 2

Stupeň vrcholu

Answer 2

označuje počet hran, které do daného vrcholu zasahují. Stupeň vrcholu u se značí deg(u)

Question 3

Skóre grafu

Answer 3

Označuje libovolně uspořádaná posloupnost stupňů jeho vrcholů.

Question 4

podgraf

Answer 4

Jinými slovy, podgraf vznikne vymazáním některých vrcholů původního grafu, všech hran do těchto vrcholů zasahujících a případně některých dalších hran.

Question 5

Izomorfizmus grafov

Answer 5

Ak majú byť grafy G a G’ izomorfné, musia mať všetky grafové charakteristiky rovnaké (počet vrcholov, počet hrán, valenčné postupnosti, počet komponentov atď.).

Question 6

Sled

Answer 6

Sled v grafu je posloupnost vrcholů taková, že mezi každými dvěma po sobě jdoucími je hrana.

Question 7

ťah

Answer 7

Tah v grafu je takový sled, ve kterém se neopakují hrany.

Question 8

Cesta

Answer 8

Sled ale Žádné dva vrcholy (a tedy ani hrany) se přitom neopakují.

Question 9

Souvislý graf

Answer 9

Souvislý graf je takový (neorientovaný) graf, v němž platí, že pro každé dva vrcholy x, y existuje sled z x do y.

Question 10

úplný graf

Answer 10

Úplný graf alebo kompletný graf je graf v ktorom je každý vrchol grafu spojený s každým iným vrcholom grafu.
označuje sa Kn

Question 11

Diskrétny graf

Answer 11

žádné dva vrcholy nejsou spojené hranou.

Question 12

Bipartitní graf

Answer 12

Pojmem bipartitní graf nebo sudý graf[1] se v teorii grafů označuje takový graf, jehož množinu vrcholů je možné rozdělit na dvě disjunktní množiny tak, že žádné dva vrcholy ze stejné množiny nejsou spojeny hranou.

Question 13

úplný bipartitní graf

Answer 13

Rozumí se jím takový bipartitní graf, do kterého již nelze přidat žádnou hranu. Jeho vrcholy lze tedy rozdělit na dvě disjunktní množiny a každý vrchol z první množiny je spojen hranou s každým vrcholem z druhé množiny. Tyto grafy jsou až na isomorfismus určeny jednoznačně počtem vrcholů obou množin a značí se
Kn,m

Question 14

orientovaný graf

Answer 14

takový graf, jehož hrany jsou uspořádané dvojice.

Tudíž výrazy (x, y) a (y, x) označují různé hrany. Hrana (x, x) se nazývá smyčka.

Question 15

prostý graf

Answer 15

neobsahuje žádnou rovnoběžnou hranu. Avšak může obsahovat smyčky.

Question 16

regulární graf

Answer 16

všechny vrcholy mají stejný stupeň

Question 17

Faktor grafu

Answer 17

Faktor grafu G alebo faktorový podgraf je taký podgraf grafu G, ktorý obsahuje všetky vrcholy grafu G.

Question 18

Komponenta souvislosti

Answer 18

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.

(jeden súvislý graf)

Question 19

korektnost algoritmu

Answer 19

?????

Question 20

eulerovsky graf

Answer 20

souvislý neorientovaný graf, který má všechny uzly sudého stupně / existuje uzavřený tah obsahující všechny jeho hrany

Question 21

eulerovský ťah

Answer 21

tah, který obsahuje každou hranu grafu právě jednou

Question 22

strom

Answer 22

graf, který je souvislý a neobsahuje žádnou kružnici.

Question 23

barvení grafu

Answer 23

přiřazováním barev různým objektům v grafu – vrcholům, hranám, stěnám atd. Nejčastěji jde o barvení vrcholů.

Question 24

kostra grafu

Answer 24

faktor grafu G taký, že medzi každými dvoma vrcholmi existuje práve jedna cesta.