9 - Obyčejné grafy Flashcards
Definice grafu, obyčejného grafu, orientovaného a obecného grafu
obyčejný graf
V teorii grafů se termínem obyčejný graf označuje takový graf, jenž neobsahuje smyčky ani rovnoběžné hrany
Graf je dvojice G = (U, H), kde:
• U je konečná množina uzlů (vrcholů)
• H je konečná množina hran (dvouprvkových množin), H ⊆ {{u, v} │ u, v ∈ U ∧u ≠ v}
○ U orientovaného grafu to není množina {u, v}, ale dvojice (u,v)
Obecný graf (multigraf)
Může mít více hran mezi stejnými uzly.
Je to trojice G=(U,H,ϵ), kde
• U je konečná množina uzlů (vrcholů)
• H je konečná množina hran
• ϵ:H→{{u,v}|u,v∈U∧u≠v} je zobrazení přiřazující každé hraně dvojici uzlů (U={1,2,3,4}, H={a,b,c,d}, ε(a)={1,3}, ε(b)={1,3}, ...)
Počet hran grafu, ohodnocený graf, stupně uzlů a úplný graf
Počet hran
Označme si písmenem u počet uzlů v grafu. Obyčejný neorientovaný graf může obsahovat maximálně (u∗(u−1))/2 hran. Orientovaná verze obyčejného grafu může obsahovat maximálně u∗(u−1) hran.
Ohodnocený graf
Graf ve kterém je každé hraně přiřazena její cena (číslo)
Stupně uzlů (vrcholů)
Stupeň uzlu je počet hran incidentních s daným uzlem.
• Suma stupňů všech uzlů je 2|H|, protože každá hrana má 2 konce.
Úplný graf
Graf, v němž každé dva vrcholy u,v∈U, u≠v jsou spojeny hranou.
Počet hran v tomto grafu je počet 2 členných kombinací n prvků, kde n je počet uzlů grafu. Tento počet lze vyjádřit kombinačním číslem (n¦2)*(n!/(n−k)!)
Podgrafy - Sled, tah, cesta, kružnice, souvislý graf
Sled
• Sled v grafu je posloupnost vrcholů taková, že mezi každými dvěma po sobě jdoucími je hrana.
Mohou se opakovat uzly i hrany
Tah
Tah v grafu je sled, ve kterém se neopakují hrany.
Cesta
Cesta je sled, ve kterém se neopakují vrcholy (aneb obsahuje všechny uzly a hrany maximálně jednou)
Kružnice (cyklus) - kružnice obsahují každou hranu maximálně jednou a všechny uzlu až na první a poslední jsou různé; uzavřené posloupnosti propojených vrcholů. (sled, ve které jsou první a poslední uzly totožné)
- Graf, který jako podgraf obsahuje kružnici, se nazývá cyklický. V opačném případě se nazývá acyklický (viz strom) ze dvou kružnic se společnou hranou lze udělat velkou kružnici bez této společné hrany
Souvislý graf - obsahuje pro libovolnou dvojici uzlů nějaký sled
Kružnice, hamiltonovská kružnice, Eulerovský graf
Kružnice (cyklus) - kružnice obsahují každou hranu maximálně jednou a všechny uzlu až na první a poslední jsou různé; uzavřené posloupnosti propojených vrcholů. (sled, ve které jsou první a poslední uzly totožné)
- Graf, který jako podgraf obsahuje kružnici, se nazývá cyklický. V opačném případě se nazývá acyklický (viz strom) ze dvou kružnic se společnou hranou lze udělat velkou kružnici bez této společné hrany
Hamiltonovká cesta (kružnice)
• Je taková kružnice, která obsahuje všechny uzly grafu.
• Hamiltonovský graf - v grafu existuje hamiltonovská kružnice
Eulerovský graf
• Existuje uzavřený tah, který obsahuje všechny hrany. (domeček)
• Souvislý neorientovaný graf, který má všechny uzly sudého stupně.
Strom a les
Les
Les je neorientovaný graf, ve kterém jsou libovolné dva vrcholy spojeny nejvýše jednou cestou. Ekvivalentní definice zní, že les je množina navzájem nepropojených stromů (odtud tedy jméno).
• Tedy graf bez kružnic se nazývá les.
Strom
V teorii grafů se jako strom označuje neorientovaný graf, který je souvislý a neobsahuje žádnou kružnici.
• Tedy souvislý les se pak nazývá strom..
Strom je tedy minimální souvislý graf bez kružnic.
• Odebráním libovolné hrany se stane nesouvislým
• Přidáním libovolné hrany vznikne kružnice!
Kostra grafu, minimální kostra
V teorii grafů je kostra souvislého grafu G takový podgraf souvislého grafu G na množině všech jeho vrcholů, který je stromem.
Graf je souvislý právě tehdy pokud má kostru
Minimální kostra
Pokud má graf ohodnocené hrany, tak má smysl hledat minimální kostru (tj. kostru, kde je součet ohodnocení hran nejmenší).
• Pokud mají všechny hrany různé hodnoty existuje právě jedna minimální kostra.
• Minimální kostru dokáží najít Kruskalův a Primův algoritmus.
Kruskalův a Primův
- algoritmy hledání minimální kostry
Kruskalův “hladový” algoritmus - nejprve seřídíme hrany dle jejich váhy od nejmenší a přidáváme vždy nejmenší hranu do grafu tak, aby nevznikl cyklus (tj. procedura terminuje po přidání |U|−1 hran).
1. Seřadíme hrany podle ceny od nejmenší po největší
2. Postupně zkoušíme přidávat hrany do kostry v tomto pořadí
○ Pokud by vznikla kružnice hranu přeskočíme.
○ Pokud přidáním hrany kružnice nevzniká přidáme ji do kostry.
3. Přidané hrany pak tvoří min. kostru grafu.
Primův (Jarníkův) algoritmus - vyjdeme z libovolného uzlu a vždy přidáme hranu s nejmenší cenou vedoucí z již objevených uzlů, která nevytvoří kružnici
Algoritmus vychází z libovolného uzlu a udržuje si seznam již objevených uzlů a jejich vzdáleností od propojené části grafu. V každém svém kroku připojí ten z uzlů, mezi nímž a projenou částí grafu je hrana nejnižší délky a označí sousedy nově připojeného uzlu za objevené, případně zkrátí vzdálenosti od již známých uzlů, pokud byla nalezena výhodnější hrana. V okamžiku, kdy jsou propojeny všechny uzly, algoritmus terminuje.
1. Vyjdeme z libovolného uzlu 2. Dokud nemáme v kostře všechny uzly: a. Najdeme všechny hrany vycházející z uzlů, které jsou již součástí kostry b. Vybereme z nich hranu s nejmenší cenou, která po přidání nevytvoří kružnici c. Tuto hranu přidáme do kostry 3. Přidané hrany pak tvoří min. kostru grafu Oproti Kruskalovu algoritmu má tu výhodu , že se nemusejí předem seřazovat podle vzrůstající ceny všechny hrany. • Při Kruskalově algoritmu se totiž většinou hrany s vysokými cenami vůbec nevyužijí.
Obarvitelnost, planarita a problém čtyř barev
Obarvitelnost (obyčejné grafy bez smyček)
• Graf je obarvený, když se každému uzlu přiřadí barva tak, že dvěma uzlům spojeným hranou jsou přiřazeny různé barvy.
• Pokud je možno graf obarvit k barvami, nazývá se k-obarvitelným.
• Nejmenší možná hodnota k, pro kterou je graf G k-obarvitelným, se nazývá chromatické číslo grafu G, formálně X(G).
Planarita = hrany se nekříží! (Má-li souvislý graf n uzlů a m hran a tvoří p buněk, platí n − m + p = 2.)
Planárnost (připouštějí i vícenásobné hrany)
• Graf G se nazývá planární (tež rovinný graf), když je možno jej nakreslit v rovině tak, aby se jeho hrany protínaly pouze v jeho uzlech. (žádné hrany se nekříží)
• Dvourozměrná oblast ohraničená hranami rovinného grafu se nazývá buňka.
Má-li souvislý graf n uzlů a m hran a tvoří p buněk, platí n − m + p = 2.
Problém čtyř barev - obarvený vrcholů planárního grafu vždy stačí max 4 barvy
Problém čtyř barev či také věta o čtyřech barvách je (již kladně vyřešený) problém z teorie grafů, který zní: „Stačí čtyři barvy na obarvení libovolné politické mapy tak, aby žádné dva sousedící státy nebyly obarveny stejnou barvou?“ (Za sousední státy jsou považovány takové, že mají společnou hraniční čáru tj. nesousedí spolu jen v jednom bodě.)
Formulace v teorii grafů
Formálně se tento problém v teorii grafů podává tak, že cílem je obarvení vrcholů planárního grafu tak, aby žádné dva vrcholy spojené hranou neměly stejnou barvu. Formulace s mapou se na tuto verzi převede tak, že každému státu se přiřadí jeden vrchol (např. hlavní město) a hranou se spojí ty vrcholy, jejichž státy mají společnou hranici.
