09 - Obyčejné grafy
pátek 13. května 2016
9:55
Obyčejné grafy (stupně uzlů, cesty a kružnice, souvislost grafu, stromy, kostry, Kruskalův a Primův algoritmus pro hledání minimální kostry ohodnoceného grafu, eulerovské a hamiltonovské grafy, obarvitelnost a planarita).
[link]
Grafy
Obyčejný neorientovaný graf
V teorii grafů se termínem obyčejný graf označuje takový graf, jenž neobsahuje smyčky ani rovnoběžné hrany.
Definice
Graf je dvojice 𝐺 = (𝑈, 𝐻), kde:
U je konečná množina uzlů (vrcholů)
H je konečná množina hran (dvouprvkových množin), 𝑯 ⊆ 𝒖, 𝒗  𝒖, 𝒗 ∈ 𝑼 ∧𝒖 ≠ 𝒗
U orientovaného grafu to není množina 𝑢, 𝑣, ale dvojice (𝒖,𝒗)
Obecný graf (multigraf)
Může mít více hran mezi stejnými uzly.
Je to trojice 𝐺=(𝑈,𝐻,𝜖), kde
𝑈 je konečná množina uzlů (vrcholů)
𝐻 je konečná množina hran
Pojmy
Počet hran
Označme si písmenem 𝑢 počet uzlů v grafu. Obyčejný neorientovaný graf může obsahovat maximálně 𝒖∗(𝒖−𝟏)𝟐 hran. Orientovaná verze obyčejného grafu může obsahovat maximálně 𝒖∗(𝒖−𝟏) hran.
Ohodnocený graf
Graf ve kterém je každé hraně přiřazena její cena (číslo)
Stupně uzlů
Stupeň uzlu je počet hran které z něj vycházejí.
Suma stupňů všech uzlů je 𝟐|𝑯|, protože každá hrana má 2 konce.
Graf, v němž každé dva vrcholy 𝑢,𝑣∈𝑈, 𝑢≠𝑣 jsou spojeny hranou.
Počet hran v tomto grafu je počet 2 členných kombinací 𝑛 prvků, kde 𝑛 je počet uzlů grafu. Tento počet lze vyjádřit kombinačním číslem 𝑛2.
Stupně vrcholů n−1
Komponenta grafu
je maximální souvislý podgraf, t.j. v tomto podgrafu najdeme cestu z vrcholu  do vrcholu  pro jakékoliv vrcholy v podgrafu. Souvislý graf má právě jednu komponentu.
Sledy v grafu
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, tedy každý vrchol se v cestě objevuje nejvýše jednou. Existuje-li mezi dvěma vrcholy sled v grafu, existuje mezi nimi i cesta (protože každý úsek mezi dvěma výskyty stejného vrcholu se dá „vystřihnout“).
Na všechny tyto pojmy se dá také nahlížet jako na podgraf.
Kružnice
V teorii grafů se termínem kružnice (též cyklus) označuje takový graf, který se skládá z jediného cyklu – tedy uzavřenéposloupnosti propojených vrcholů. Kružnice může být orientovaná i neorientovaná.
Graf, který jako podgraf obsahuje kružnici, se nazývá cyklický. V opačném případě se nazývá acyklický (viz strom).
sled, ve které jsou první a poslední uzly totožné
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.
Souvislý neorientovaný graf, který má všechny uzly sudého stupně.
Stromy
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
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
(kostra je červeně, graf černě)
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 ("hladový") algoritmus
Kruskalův algoritmus nejprve setřídí hrany dle jejich váhy (od nejmenší) a následně přidává hrany do grafu takovým způsobem, aby nevznikl žádný cyklus (tj. procedura terminuje po přidání 𝑈−1 hran).
[link]
Seřadíme hrany podle ceny od nejmenší po největší
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.
Přidané hrany pak tvoří min. kostru grafu.
Složitost
𝑂𝐻∗log𝐻 //rychlost algoritmu je limitovaná seřazením hran
Primův (Jarníkův) algoritmus
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.
[link]
Vyjdeme z libovolného uzlu
Dokud nemáme v kostře všechny uzly:
Najdeme všechny hrany vycházející z uzlů, které jsou již součástí kostry
Vybereme z nich hranu s nejmenší cenou, která po přidání nevytvoří kružnici
Tuto hranu přidáme do kostry
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í.
Složitost
𝑂𝐻∗log𝑈 //složitost záloží na použitých datových strukturách
Obarvitelnost a planarita
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 𝑘 barvami, nazývá se k-obarvitelným.
Nejmenší možná hodnota 𝒌, pro kterou je graf G k-obarvitelným, se nazývá chromatické číslo grafu G, formálně X(G).
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.
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
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.
Notes
2. Otazka (predmet) (okruh):14. Obyčejné grafy
Kdo me primarne zkousel: Smrž Pavel, doc. RNDr., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Ptal se na rozdíl mezi obyčejnými a orientovanými grafy. Pak na kostru a kolik má kostra grafu hran (prvně jsem řekl špatně n+1, ale hned jsem se opravil). Pak se ptal na úplný graf a opět kolik má hran (to jsem musel spočítat). Nakonec se zeptal, jak určujeme nejkratší cestu, řekl jsem že Kruskalův a Primův algoritmus. Tak mi řekl, ať si jeden vyberu a ukážu ho. Taky za A.
From <[link]> 
2. Otazka (predmet) (okruh): 9. Obyčejné grafy
Kdo me primarne zkousel: Steingartner (externista)
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Na papírku bylo: 9. Obyčejné grafy: definice, cesta, kružnice, kostra, Cayleyho formule (WTF???), strom, les
Napsal jsem definici na tabuli, popsal jsem cestu (to jsem spletl, že obsahuje všechny uzly právě jednou), tak se doptal, jestli musí obsahovat všechny uzly - tak potom, že je to obecně cesta mezi dvěma uzly. I když jsem měl na papírku ty pojmy, tak už to pak probíhalo jen otázka(pojem)/odpověď. V čem je specifická kružnice. Co je kostra. Potom se ptal na Cayleyho formuli, zda jsem slyšel někdy, to jsem mu řekl, že v životě fakt ne (jinými slovy). Pak se ptal Meduny, jestli nekecám, tak mu řekl, že to možná známe pod jiným pojmem. Pak se ptal na Hamiltonovskou kružnici, k ní se ještě doptal na nějakou podrobnost, kterou jsem asi nezmínil předtím. Byl spokojen, na stromy a lesy nedošlo. Pak se ještě Meduna doptal na tu definici grafu (měl jsem H = {{u, v} | u, v € U}), jaký je rozdíl pro orientovaný graf. Tak že tam místo {,} bude (,) a v pohodě. Tohle taky za B.
From <[link]> 
1. Otazka (predmet) (okruh): 9. Obyčejné grafy.- MAT
Kdo me primarne zkousel: Holík
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
9ka otázka, ale chcel orientované grafy, takže prakticky 9+10 
. Začal som orientovanými grafmi - defíníciou - je to trojica G = (H, U, epsilon), kde ma Holik prerusil, ze nech poviem co je co. 
To som zvladol, potom sa pytal priamo na algoritmy: Povedal som Dijkstrov, pytal sa ma este na Floyd-Warshalov-vravim, ze vobec neviem. Holik skusal, ze ci aspon nieco, vravim, ze vobec 
Dalej na algoritmy pre hladanie minimalnej kostry grafu - Popisal som Kruskalov, ale pri odpovedi som ho uviedol ako Primov. 
Vysledna D. 
From <[link]> 
1. Otazka (predmet) (okruh): Obyčejné grafy (MAT)
Kdo me primarne zkousel: Smrž Pavel, doc. RNDr., Ph.D. UPGM FIT VUT, Brno
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
V duchu jsem si rikal - pohoda, to umim. Zacal jsem suverene definici grafu, jenze pak to zacalo - nadefinoval jsem hrany jako mnozinu dvojic a ne mnozinu mnozin. Tak me upozornili, ze tohle je definice orientovaneho grafu. Absolutne mi to nedoslo, mezitim se ptali co to je graf a jak vypada. Jak vypada orientovany - chteli me k tomu nejak navest. Ja jsem jim jeste rekl neco o multigrafu. Uz zazvonil budik - ja uz to videl na opravny termin. Nakonec jsme se k tomu nejak dopracovali. Co me zachranilo, ze se ptali dal - co je to kostra grafu, to jsem jim rekl. Kolik ma kostra hran - (uzly - 1). Na zaver Kruskaluv algoritmus - samosreme, ze jsem jim ukazoval Primuv. Dokoncil jsem jej tedy a pote ukazal i Kruskaluv. Na zaver jsem rekl slozitosti ac se na ne neptali.
(na papirku - obyc. grafy, kostra, kruskaluv alg.)
From <[link]> 
1. Otazka (predmet) (okruh): MAT - Obyčejné grafy
Kdo me primarne zkousel: Rogalewicz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: 
Měl jsem začít definicí stromu, pak co je to kostra a kostra s minimální cenou. Pak chtěl ať nakreslím nějáký jednoduchý graf a vyznačím tam tu kostru a pak ať demonstruji jak bych hledal minimální kostru - ukázal jsem Kruskalův algoritmus. Pak se ještě ptal jak funguje Primův. Poslední otázka byla jestliže může mít graf více koster s minimální cenou. Výsledné hodnocení - A
From <[link]> 
1. Otazka (předmět) (okruh): 9. Obyčejné grafy (MAT)
Kdo me primarne zkousel: Jen Herout
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Ptal se na obecnou definici, pak na kostru, cestu a souvislý graf. Všechno jsem řekl, ale poměrně často mě musel opravit nebo požádat o doplnění (třeba když jsem řekl množina místo uspořádaná dvojice nebo "Co je to strom?" "Graf, jehož žádný podgraf není kružnicí" "To není všechno!" Já po chvíli ticha: "Jo, ještě musí být souvislý".
Cca po dvou-třech minutách řekl, že mu to stačí. Nicméně celou dobu držel poker face a to nebylo dvakrát příjemné. Ale byl jsem si jistý, že to mám, jen jsem nevěděl, na jakou známku. Nakonec A
From <[link]> 
1. Otázka (předmět) (okruh): MAT - Obyčejné grafy (stupně uzlů, cesty a kružnice, souvislost grafu, stromy, kostry, Kruskalův a Primův algoritmus pro hledání minimální kostry ohodnoceného grafu, obarvitelnost a planarita)
Kdo mě primárně zkoušel: myslím, že hlavně Holík a Švéda, ale přesně si to nevybavuji
Co jsem k tomu řekl(a)/na co se ptali/co mně vytkli: Přestože jsem myslel, že u grafů mě nic nepřekvapí, trochu jsem se zamotal hned u formální definice a pak už se mě spíš ptali, takže jsem odpovídal na otázky a lezlo to ze mě strašně pomalu, zadrhával jsem se a asi jsme ani vše nestihli. Každopádně i tak jsem měl celkem dobrý pocit a výsledek byl C.
From <[link]> 
1. Otazka (předmět) (okruh): Obyčejné grafy
Kdo me primarne zkousel: Křivka Zbyněk, Ing., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Definice grafu, formalne na tabuli. Pak se ptal co to je kostra grafu, souvisly graf atp. Nakonec chtěl slovy popsat Kruskalův algoritmus a jak by se dal optimalizovat (pocet hran kostry je pocet uzlu+1) a bylo. B.
From <[link]> 
1. Otazka (předmět) (okruh):Obyčejné grafy
Kdo me primarne zkousel:Hladká Eva, doc. RNDr., Ph.D. FI MUNI, Brno
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Luxusní otázka nechala mě mluvit graf, multigraf, komponenty co je to spojity graf atd kdyz jsem chtel projit kruskaluv algoritmus rekla at ji definuji jeste stream. Naprosto v pohode otazka a zkouseni
From <[link]> 
1. Otazka (předmět) (okruh): Obyčejné grafy (MAT)
Kdo me primarne zkousel: prof. Šlapal
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
MATu jsem se bál jako čert kříže. V jediné naší komisi byl prof. Šlapal, takže to byl respekt největší. Ikdyž jsme MAT docela poctivě drtili, věděl bych tak k polovině otázek a u zbytku by to bylo na úklon.
Naštěstí padly grafy, což byla moje spása. Úvodní definice ho nezajímaly ("to přece všichni známe") a zaměřil se na stupně uzlů (něco v tom smyslu bylo i na papírku - stupně uzlů, cesty, stromy,...) ze všech různých úhlů pohledu. Já jsem v tu chvíli nebyl schopný vymyslet ani základní vztah pro stupně uzlů ve vztahu k hranám. Tak jsem mu to slovně popsal s tím, že vzorec prostě nevypotím, byl jsem úplně mimo. V tu chvíli bych nedal ani vztah pro kvadratickou rovnici, prostě nic.
Prof. Šlapal byl ale super, dost mě naváděl a viděl že tomu docela rozumím, jen se nemůžu vymáčknout. Rozhodně musím říct, že ho jeho pověst předchází, ale až tak strašně zlý určitě není. Klidně mi mohl dát mnohem horší otázku, ale dal grafy a dost pomáhal. Žádný vzorec ve výsledku ani nechtěl, na tabuli jsem taky nekreslil. Rozhodně nevypadal, tak jak někdo strašil loni, že by zkoušel stylem "pokud mi neřeknete tuhle definici, tak se nehneme dál". Nemluvil za mě, musel jsem všechno vymýšlet sám, ale rozhodně nedrtil a zkoušel třeba navést k odpovědi z jiné strany.
From <[link]> 
1. otazka (okruh): Obycejne grafy (9)
- Kdo me primarne zkousel: Strnadel
- Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Chtel co je to graf, podgraf, faktor grafu, nakreslit graf, ukazat podgrafy, faktor grafu a definici kruznice. To je vsechno!
From <[link]> 
1. Otazka (předmět) (okruh): 9. Obyčejné grafy
Kdo me primarne zkousel: Hladká Eva, doc. RNDr., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Tak som si hovoril, akou lahodnou otázkou sa na úvod zahrejem. Docentka Hladká to však zobrala z úplne iného konca, tak aby som sa pri tom poriadne zapotil. Na začiatku som hneď pokazil multigraf. Potom vraj, akými štruktúrami reprezentujeme grafy v algoritmoch. Vtedy zapol môj mozog na maximum a snažil sa spomenúť na znalosti z Grafových algoritmov spred dvoch rokov 
 Nakoniec ma to viazané pole aj matica susednosti uzlov napadli. Potom som mal nakresliť maticu a ukázať jej to na príklade. Potom ešte nejaké otázky o cestách, kružniciach, minimálnych kostrách a algoritmoch. To už bolo relatívne v pohode, sem tam som ešte nejakú drobnosť nevedel. Tiež sa ma pýtala, kde používame minimálne kostry v sieťach. Napadli ma smerovacie protokoly, ale vraj aj nižšie v L2 vrstve.
From <[link]> 
1. Otazka (předmět) (okruh): Obyčejné grafy
Kdo me primarne zkousel: Rychlý
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Zeptal se na definici obecného grafu, cesty, kružnice, minimální kostry a Primova algoritmu. Pak ještě Primův algoritmus prakticky. Asi dvakrát jsem mu řekl něco, co se mu nezdálo, tak mě upozornil, ať popřemýšlím a řekl jsem mu, co chtěl slyšet. Splet jsem si Primův a Krusalův algoritmus a u definice obecného grafu jsem zapomněl na to, že u != v. Nevěděl jsem jedinou věc, a to, že u Primova algoritmu po nenalezení vhodné hrany se algoritmus nevrací o jeden uzel na zpět, ale prohledává všechny s minimálním ohodnocením. Celkově - A
From <[link]> 
1. Otazka (předmět) (okruh): 9. Obyčejné grafy (MAT) - stromy
Kdo me primarne zkousel: Češka Milan, prof. RNDr., CSc.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Zameranie otázky na stromy som mal kvôli DP. Začal som trochu kostrbato koktavo definíciou grafu, hrán, uzlov a obecného grafu. Potom ma hneď prerušil a chcel odomňa všetko zapísať formálne, z čoho som bol v strese tak ma trochu potrápil. Potom sa ma pýtal na vzťah hrán a uzlov... nevedel som čo myslí tak som začal vymenovávať čo mi napadlo po vyše minúte hádania som mu povedal, že je hrán o 1 menej ako uzlov a to on chcel akože počuť, ešte mi to dal zapísať formálne zasa... (nepochopil som tieto maniere, že načo mi dával takéto veci zapisovať ale vyzeral že má toho z tých štátnic už dosť). Potom konečne definícia súvislého grafu a stromu. Zazvonil budík, spýtal sa ešte na kostru, minimálnu kostru. Potom mal ešte Zemčík doplňujúcu otázku kde ma chcel nachytať, že akú kostru má konkrétny graf aký zadal, ten bol ale nesúvislý a došlo mi to hneď takže pohoda.
From <[link]> 
1. Otazka (okruh):
Obyčejné grafy, kostra, algoritmy pro minimální kostru
Kdo me primarne zkousel:
Křivka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Chtěl formální definici grafu. Pak co je to kostra a nakonec dva algoritmy pro hledání nejmenší kostry (Kruskalův a Primův). Úplná pohodička, když bylo něco špatně, tak jenom jemně naznačil a nechal mě to opravit.
From <[link]> 
1. Otazka (předmět) (okruh): Neorientovane grafy (9)
Kdo me primarne zkousel: Rychly + Ceska se dost ptal
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Chteli definici, cestu, strom, kostru, algoritmy, vsechno jsem rekl. Chtel formalni zapis ohodnoceni hrany, to jsem nejak zaimprovizoval, ale finalne pro me prekvapive D
From <[link]> 
1. Otazka (MAT) (Obyčejné grafy):
Kdo me primarne zkousel: Češka, Lucká
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Chtěli to slyšet v podstatě celé od začátku. Češka si mě trošku podal u definic (chtěl to naprosto přesně a nechtěl srovnání s orientovanými grafy). Takže sled, tah, cesta, kružnice. Dále podgraf, souvislý, les, strom, kostra. A pak prý rozdíl mezi lesem a stromem není to, že strom je souvislý, ale že strom je souvislý a les není 
. Kruskalův a Primův algoritmus včetně složitosti. Tvrdě jsem přetáhli čas, už mě zastavovali, klidně bych ještě valil dál. Jo a pak otázka, na problém 4 barev, jestli jsem o něm něco slyšel a jak to souvisí s planaritou grafu. Celkově za B.
From <[link]> 
2. Otazka (předmět) (okruh): MAT - Obyčejný graf
Kdo me primarne zkousel: Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Byl jsem tak mimo že i u takto lehké otázky jsem se zamotal. Na otázky jsem odpovídal jak jen to bylo možné. Pan Češka je naporostej proík a když viděl že to vím a nemužu si vzpomenotu tak mě navedl k odpovědi, i když mi to někdy krapet trvalo. Nicméně to bylo lepší jak první otázka. Myslím že za tuto jsem dostal D, ale nejsem si jiostej.
From <[link]> 