MFF Notebook > Diskrétní matematika

Diskrétní matematika

Grafy

Problém sedmi mostů města Královce, řešený v roce 1736 L. Eulerem lze považovat za historický začátek teorie grafů.

Obyčejný graf nemá ani rovnoběžné hrany ani smyčky.

Prostý graf nemá rovnoběžné hrany, ale má smyčky.

Multigraf má rovnoběžné hrany i smyčky.

Neorientovaný

h A B

Hrana h inciduje s uzly A a B.

Faktor podgraf, který má pořá stejné uzly, jen může mít méně hran. Lze také říci, že je to graf indukovaný podmnožinou jeho hran.

Sled je posloupnost uzlů a hran. Posloupnost začíná i končí uzlem. Každá hrana inciduje s uzly, které jsou v posleupnosti před ní a po ní.

Tah je sled, ve kterém se neopakuje stejná hrana. Pokud množina tahů obsahuje všechny hrany grafu, jedná se o pokrytí.

Cesta je tah, ve kterém se neopakuje stejný uzel. Cesta však může začínat a končit ve stejném uzlu. Pokud se tak děje, je uzavřená, jinak je otevřená.

Kružnice je uzavřená cesta.

Z každého sledu lze vybrat cestu.

Komponenta grafu je maximálí souvislá část grafu. Graf je sjednocením svých komponent. Pro každé dva uzly komponenty platí, že mezi nimi existuje cesta.

Graf je souvislý, pokud má jednu komponentu.

Kostra grafu je jeho faktor, který neobsahuje kružnici. Pro souvislý graf o n hranách existuje nn-2 koster.

Pokud pro každé dva uzly grafu lze najít hranu, která s nimi inciduje, jedná se o úplný graf.

Sousedi jsou uzly, které incidují se stejnou hranou.

Stupeň uzlu je počet hran, které incidují s daným uzlem.

Klika je pojem přenesen z aplikace teorie grafů ve společenských vědách: Jestliže uzly grafu představují osoby a hrany např. vyjadřují shodu politických názorů příslušných osob, pak klikou bude skupina osob se shodnými politickými názory.

Nezávislá podmnožina uzlů grafu G je taková, ve které žádné dva z jejích uzlů neincidují se stejnou hranou grafu G.

Dominující podmnožina uzlů grafu G je taková, která svou množinou sousedů pokrývá všechny zbývající uzly grafu G.

Střed grafu je každý uzel s excentricitou rovnou poloměru.

Minimální pokrytí vyjadřuje minimální počet tahů, které jsou potřeba k propojení všech uzlů grafu těmito tahy. Takže například jeden uzvařený tah, jeden otevřený tah, dva otevřené tahy, atd.

Orientovaný

h A B

Uzel A je předchůdce uzlu B. Uzel B je následník uzlu A. Tyto pojmy nejsou tranzitivní. Tento graf má orientovanou cestu [A,h,B].

Graf je silně souvislý, pokud pro každé dva uzly existuje orientovaná cesta, která tyto uzly spojuje.

Spojení je orientovaná cesta.

Cyklus je uzavřená orientovaná cesta.

Kondenzace je náhrada cyklu za jeden uzel.

Vstupní stupeň je počet předchůdců daného uzlu.

Výstupní stupeň je počet následníků daného uzlu.

Kořen je uzel se vstupním stupněm rovným nule.

List je uzel s výstupním stupněm rovným nule.

Izomorfismus

Pokud si vezmu doplněk grafu, počet jeho izomorfismů se tím nezmění.

Počet automorfismů kružnice s n uzly je 2n.

Počet automorfismů hvězdice s n uzly je (n-1)!.

Počet automorfismů jedná-li se o úplný graf Kn je n!.

Počet automorfismů jedná-li se o úplný bipartitní graf Km,n je m!n!.

Počet automorfismů jedná-li se o úplný bipartitní graf Kn,n je 2n!n!.

Charakteristická čísla

Klikovost je mohutnost uzlů největší kliky.

Chromatické číslo vyjadřuje minimální počet barev nutný k obarvení grafu.

Dominance je mohutnost minimální dominující podmnožiny.

Excentricita uzlu je nejdelší vzdálenost do jiného uzlu grafu.

Poloměr grafu je minimální excentricita.

Průměr grafu je maximální excentricita.

Cyklomatické číslo grafu je minimální počet hran, po jejichž odebrání nebude v grafu žádná kružnice.

Hodnost grafu vyjadřuje počet hran v kostře grafu.

Nezávislot grafu je mohutnost prvků jeho maximální nezávislé nožiny.

Rovnice

χ(G) ≤ δmax + 1
χ je počet barev grafu a δmax je maximální stupeň uzlu.

μ(G) = |E| − |U| + p
E je množina všech hran, U je množina všech uzlů a p je počet komponent grafu.

Značení

α(G) – nezávislost grafu.

β(G) – dominance grafu.

δ(U) – stupeň uzlu

h(G) – stupeň grafu.

χ(G) – chromatické číslo grafu.

Synonyma

uzel = vrchol

rovnoběžná hrana = dvojnásobná hrana

obyčejný graf = 〈H, U〉

Creative Commons License