SPECIÁLNÍ TYPY GRAFŮ

Question 1

Bipartitní graf

Answer 1

je graf, jehož množinu vrcholů můžeme rozdělit do dvou množin V1 a V2 tak, že
V1 průnik V2 = prázdná množina a V1 sjednoceno V2 = V a každá hrana grafu má jeden koncový vrchol v množině V1 a druhý v množině V2.

tj. graf jehož množinu vrcholů lze rozdělit na dvě části tak, že z každého vrcholu první části jde hrana pouze do vrcholu druhé části a naopak

VĚTA: Pro každý graf G = (V, E) platí:
Graf G je BIPARTITNÍ právě tehdy, když graf G neobsahuje kružnice LICHÉ DÉLKY

Question 2

Úplný bipartitní graf K m,n

Answer 2

je bipartitní graf, kde |V1| = m, |V2| = n, a ve kterém je hranou spojen
každý z m vrcholů množiny V1 s každým z n vrcholů množiny V2 .

tj. pokud jde z každého vrcholu první části hrana do každého vrcholu druhé části.

Graf K m,n má m*n hran

Question 3

HAMILTONOVSKÁ KRUŽNICE

Answer 3

V grafu G je kružnice, která obsahuje všechny vrcholy grafu G

Question 4

HAMILTONOVSKÝ GRAF

Answer 4

graf ve kterém existuje Hamiltonovská kružnice

- pokud je graf hamiltonovský, neexistuje v něm most

Question 5

EULEROVSKÝ TAH

EULEROVSKÝ GRAF

Answer 5

V G je uzavřený/otevřený TAH (můžou se opakovat vrcholy ale hrany ne), který obsahuje všechny hrany grafu G.

Eulerovský graf= souvislý graf ve kterém existuje eulerovský tah

Question 6

EULEROVSKÝ GRAF VĚTA

Answer 6

Graf G je Eulerovský <==> G je souvislý a má buď všechny vrcholy sudého stupně, nebo právě dva vrcholy lichého stupně

Question 7

Rovinný graf

Answer 7

graf ve kterém ex. ROVINNÁ REPREZENTACE
můžeme jej nakreslit do roviny tak, aby se žádné dvě hrany nekřížily

Pro každý graf G s alespoň 3 vrcholy platí:
Jestliže G je rovinný graf pak |E| ≤ 3*|V|-6

Question 8

DĚLENÍ GRAFU

Answer 8

nazýváme každý graf, který vznikne z grafu G postupným půlením hran.

Question 9

OBARVENÍ GRAFU

obarvení vrcholů grafu

Answer 9

je ohodnocení vrcholů grafu hodnotami z množiny B (tzv. barvami) a to tak, že žádné dva sousední vrcholy nejsou ohodnoceny stejnou barvou.

Question 10

r-BAREVNÝ GRAF

Answer 10

jestliže existuje jeho obarvení r barvami

Question 11

BAREVNOST GRAFU / Vrcholová barevnost/ Chromatické číslo

Answer 11

je nejmenší počet barev potřebný k obarvení grafu

Question 12

PROBLÉM 4 BAREV

Answer 12

Pro každý graf G = (V, E) platí:

Jestliže G je rovinný, pak barevnost grafu G je menší/rovná 4