Poznámky k teorii grafů

Nekdy vyzaduje rucni prepnuti kodovani do UTF-8 (Zobrazit-> Kodovani-> UTF-8)

Imagemap
Poznámky k teorii grafůZákladní typy grafůÚplný grafDiskrétní grafCestaKružniceEulerovský grafHamiltonovský grafStromLesSíťBigrafPlanární (plochý) grafV grafu lze najít / určitVrchol či uzelHranaSledCestaKružniceSmyčkaTahKomponentyKostraHvězda vrcholu - SeparaceŘezTětiva kostryFundamentální soustava kružnicFundamentální soustava řezůVzdálenost mezi vrcholyVáha, ohodnoceníZdroj a StokIntenzita uzluPropustnost hranyPolocestaStabilní množinaVlastnosti grafůNeorientovanéOrientovanéMorfizmySouvislý grafNesouvislý grafStupeň grafuFaktor grafuAcyklické orientiované grafyOhodnocenost grafuAlgoritmyDijkstrův algoritmusUrčení počtu koster v orientovaném grafuHladový algoritmusFloydův algoritmusBorůvkův algoritmusFord-FulkersonůvEdmonds–Karpův algoritmusZnačeníG, H - grafV - množina všech vrcholů grafu (vertex)E - množina všech hran grafu (edge)T - tahu, v, w - konkétní vrcholy z množiny Ve - konkrétní hrana grafu(u,v) - hrana začínající v u a končící v ...n - počet vrcholů grafum - počet hran grafuk - délka kružnice
k - u počítání s mati ...Binární stromyd+, d- stupeň vrcholu orientovaného graf ...M(G) - incidenční maticeL - Lapalaceova matice grafu GL' - Lapaceova matice s vypuštěním posle ...R(G) - Matice řezůS(G) - Matice sousednostiD(G) - distanční matice(G,w) - Ohodnocený grafOhodnocení grafu (w...)D^w(G) - w-distanční matice, matice váže ...z Zdroj, s Stokai - ohodnocení uzlu r(i,j) - ohodnocení hranyA - podmnožina množiny všech vrcholů gra ...|x| - velikost toku xTheta - velikost toku polocestyřez (A,Ä)Operace prováděné s grafemOdstranění vrcholuOdstranění hranySymetrizace grafuOrientace grafuTranzitivní uzávěrKondenzace grafuOhodnocení grafuZdvojení uzlůPřidání fiktivního zdroje / stokuZnačkování vrcholůMaticeIncidenční matice M(G) - Matice sousedno ...Redukovaná incidenční matice MR(G)Laplaceova maticeTransponovaná maticeSpeciální maticeMatice řezů R(G)Matice sousednostiDistanční maticeVážená matice sousednostiw-distanční matice, Matice vážených vzdá ...RozložitelnáStrukturální maticeZjištění určité skutečnostiZjištění acykličnosti grafuPočet koster grafu orientovaného grafuPočet koster neorientovaného grafuZjištění počtu komponent orientovaného g ...Zjištění počtu komponent neorientovaného ...Určit faktor grafuZjištění počtu sledů dané délky Určení acykličnosti grafuUrčení vzdálenosti mezi vrcholyZda je graf silně souvislýVyhledání maximálního tokuZjištění rozložitelnosti maticeZda je matice regulárníSložitost řešeníObecněZda je graf či není EulerovskýZda je graf, nebo není HamiltonosvkýDijkstrův algoritmusNalezení distanční maticeZda je graf silně souvislýZjištění acykličnosti grafuVytvoření matice vážených vzdáleností (w ...Hladový algoritmusProblém obchodního cestujícíhoProblém SATk-obarvitelnostExistence kliky velikosti kProblémem INDNalezení nevetšího tokuZdrojeSkripta - Diskrétní matematika
R. Čada,  ...Pracovní texty přednášek
Teorie grafů a  ...Doc.RNDr.Milan BERKA,CSc.
http://home.eu ...
hidePoznámky k teorii grafů
hideZákladní typy grafů
hideÚplný graf
leafKaždý vrchol je s každým propojen hranou
hideDiskrétní graf
leafNemá žádné hrany
hideCesta
leafV grafu jsou dva vrcholy, ktere maji pouze jednu hranu. Z jednoho vrcholu s jednou hranou se lze dostat přes všechny hrany a všechny uzly k druhému bodu s jednou hranou. Graf má dva a více vrcholů.
hideKružnice
leafMá stejný počet hran jako vrcholů. Z každého vrcholu vedou dvě hrany. Graf musí mít 3 a více vrcholů.
hideEulerovský graf
leafSouvislý graf obsahující tah procházející všemi vrcholy a hranami (Eulerovksý tah) (Prochází všemi hranami a vrcholy. Hranami nejvíce jednou vrcholy libovolněkrát.)
leafElerovský tah (Eulerova cesta) v souvislém grafu existuje, právě když tento graf obsahuje maximálně dva vrcholy lichého stupně.Předpokládáme, že graf je konečný.
leafideaJe souvislý a všechny jeho vrcholy mají sudý stupeň
leafstopGraf který obsahuje řez o velikosti 1 nemůže být Eulerovský, ani hamiltonovský
hideHamiltonovský graf
leafObsahuje Hammilnonovskou kružnici. (Kružnici, která spojuje všechny vrcholy grafu, vrcholy a hranami prochází nejvíce jedenkrát.) Nemusí procházet všemi hranami.
hidePostačující podmínky pro existenci Ham. Graf
leafSouvislost grafu ve smyslu: Počet všech vrcholů je alespoň stupně n/2
leafstopGraf který obsahuje řez o velikosti 1 nemůže být Eulerovský, ani hamiltonovský
hideStrom
leafJe souvislý graf, který neobsahuje žádnou kružnici,
hideO stromech
leafList stromu = každý vrchol, který má jen jednu hranu
leafMá-li strom alespon dva vrcholy, pak má alespon dva listy.
leafKaždý vrchol je s každým propojen hranou
leafNemá žádné hrany
leafAby libovolný konečný, souvislý graf byl stromem, je nutné a postačující, aby počet jeho hran byl o jednu menší než počet jeho vrcholů.
leafSouvislý graf obsahující tah procházející všemi vrcholy a hranami (Eulerovksý tah) (Prochází všemi hranami a vrcholy. Hranami nejvíce jednou vrcholy libovolněkrát.)
leafObsahuje Hammilnonovskou kružnici. (Kružnici, která spojuje všechny vrcholy grafu, vrcholy a hranami prochází nejvíce jedenkrát.) Nemusí procházet všemi hranami.
leafGraf G je stromem, právě když pro každé dva vrcholy existuje právě jedna cesta.
leafGraf G je stromem, právě když pro každé dva vrcholy existuje právě jedna cesta.
leafGraf je strom, kprávě když je souvislý a má n-1 hran
leafGraf je strom právě když je souvislý a nemá žádný souvislý vlastní faktor
leafGraf G je strom, právě když je souvislý a nemá žádný souvislý vlastní faktor
hideRozhodovací strom
leafPoužívá se k modelování rozhodovacích procesů
hideBinární stromy
leafKaždý strom, v němž má každý vrchol nejvýše dva potomky.
hideLes
leafGraf vzniklý disjunktním sloučením stromů
hideSíť
leafSíť je orientovaný graf, s ohodnocením hran kladnými reálnými čísly, obsahující dva význačné vrcholy. z - zdroj s - stok Každá hrana má určenu propustnost. Určuje se maximální tok.
hideBigraf
hideCo je bigraf
leafBigraf je orientovaný graf G , jehož množinu uzlů lze rozložit na disjunktní neprázdné podmnožiny U1, U2 2 tak, že pro každou hranu (u, v) u patří do množiny U1 a v patří do množiny U2. Jednoduše řečeno takový graf, který se dá rozdělit na dvě množiny uzlů a který má hrany které vedou pouze mezi těmito skupinami nikoliv mezi uzly jedné skupiny.
leafGraf je bigrafem, právě když je graf acyklický a každý uzel je vstupní nebo výstupní.
leafSymetrizací bigrafu je biparitní neorientovaný graf
leaf
hideÚplný bigraf
leafÚplný bigraf Z každého uzlu první skupiny vede hrana do každého uzlu druhé skupiny. n= počet uzlů Má tedy n * n hran
hideLineární bigraf
leafdef 3.7
hidePlanární (plochý) graf
leafTakový graf, který se dá na ploše zobrazit tak, že se žádné dvě hrany nekříží
hideV grafu lze najít / určit
hideVrchol či uzel
leafZnázorňován často jako bod v rovině. Používán také k označení stavu.
hideStupeň vrcholu
leafPočet všech hran spojených s vrcholem
hideforwardVstupní vrchol
leafVrchol orientovaného grafu, který nemá vstupní hrany
hideforwardVýstupní vrchol
leafVrchol orientovaného grafu, který nemá výstupní hrany
hideHrana
leafSpojnice mezi dvěma vrcholy. Někdy i vrchol sám se sebou. Někdy může být i více hran mezi dvěma vrcholy.
hideNeorientované
leafBez určení odkud kam vedou
hideforwardOrientované
leafMají směr, výchozí a cílový uzel
hideSled
leafLibovolná posloupnost vrcholů mezi vrcholy u a v do kterých se lze dostat po hranách. Hrany i vrcholy lze procházet opakovaně.
leafMinimální sled
hideUzavřený sled
leafZačíná a končí ve stejném vrcholu
leafforwardOrientovaný sled
hideCesta
leafCesta z vrcholu u do v je takový sled, ve kterém se každý vrchol vystytuje pouze jednou.
hideTranzitivita
leafPokud existuje cesta z vrcholu x do v a z v do z, je logické, že bude existovat cesta z x do z
leafMinimální cesta
leafforwardOrientovaná cesta
hideKružnice
leafKružnice grafu G je uzavřený sled, obsahující nejméně 3 vrcholy. Jeden vrchol se v něm objevuje právě dvakrát a ostatní vrcholy nejvýše jednou.
leafI po odstraněním jedné hrany kružnice graf stále zůstává souvislý.
hideHamiltonovská kružnice
leafUzavřený sled, který prochází všemi vrcholy grafu právě jednou
leafforwardCyklus neboli orientovaná kružnice
hideSmyčka
leafHrana začínající i končící v jednom vrcholu
hideTah
leafJe sled, ve kterém se mohou opakovat vrcholy, ale nesmí se opakovat hrany.
hideUzavřený tah
leafZačíná i končí stejným vrcholem
hideEulerovský tah
leafJe nazýván Eulerovským, pokud používá každou hranu grafu právě jednou
hideKomponenty
leafIndukované podgrafy grafu Maximální souvislý podgraf grafu
hideKomponenty orientovaného grafu
leafMaximální slabě souvislé podgrafy. (Maximální podgrafy po převodu grafu na neorientovaný graf.)
hideforwardKvazikomponenty
leafU orientovaného grafu G každý jeho indukovaný podgraf na množině vrcholů, která tvoří některou ze tříd ekvivalence.
leafLaicky: část orientovaného grafu, po které lze libovolně chodit dle orientace a navštěvovat libovolné vrcholy. Může jí být i jediný uzel, když to nejde lépe.
hideKostra
leafKostrou souvislého grafu je je každý jeho souvislý podgraf obsahující všechny vrcholy a neobsahujíví kružnice.
leafideaKaždý souvislý graf má alespoň jednu kostru
hideMinimální kostra
leafObjevuje se v úlohách, kde se hledá optimální propojení objektů.
hideHvězda vrcholu - Separace
leaf10.4 Množina jen těch hran, které začínají nebo končí v jednom konkrétním vrcholu
hideŘez
leafDůkaz 10.4 Řezem v souvislém grafu G je množina hran A s vlastností, že graf G - A (vzniklý oddělením hran A z grafu G) je nesouvislý, ale přitom žádná vlastní podmnožina množiny A tuto vlastnost nemá.
hideTětiva kostry
leafTaková hrana, která spojuje ve stromovém grafu dva vrcholy tak, že vznikne kružnice
hideFundamentální soustava kružnic
leafje vztažena ke konkrétní kostře T a tvoří bázi prostoru kružnic
hideFundamentální soustava řezů
leafSoustava všech možných řezů vzhledem ke kostře T, které rozdělí graf na komponenty
hideVzdálenost mezi vrcholy
leafDélka nejkratší cesty z x do y
hideVáha, ohodnocení
leafČíselná hodnota přiřazená hraně, vypovídající o jejích vlastnostech
hideZdroj a Stok
leafOnačení význačných uzlů v grafech typu síť
hideIntenzita uzlu
leafKolik maximálně může daným uzlem protékat
leafPropustnost hrany
hidePolocesta
leafCesta po nenasycených hranách ohodnoceného grafu, která může jít i proti směru orientace
hideStabilní množina
leafstr. 18. pracovní texty přednášek
hideVlastnosti grafů
hideNeorientované
leafHrany nemají směr
hideOrientované
leafHany mají směr
leafHrany se označují jako dvojice (u,v) Hrana začíní ve vrcholu v a končí ve vrcholu u
leaf(uv) (vu) jsou růzmě orientované hrany mezi dvěma vrcholy (vv) je smyčka, hrana začínající i končící ve vrcholu v
hideMorfizmy
hideIsomorfismus
leafG a G' se liší pouze „očíslováním“ svých vrcholů.
leafHomomorfismus vrcholový
leafEpimorfismus vrcholový
leafMonomorfismus hranový
leafEpimorfismus hranový
hideSouvislý graf
leafKdyž pro každé dva libovolné body existuje cesta, která je spojí.
hideVlastnosti souvislých grafů
leafKaždý souvislý graf G obsahuje vrchol v s vlastnotí, že pokud v odebereme, G zůstane souvislý
leafV souvislém grafu je m (počet hran) vetší, nebo roven n (počtu vrcholů) -1
leafideaMa-li každý vrchol grafu alespoň n(počet vrcholů) / 2 hran, pak je G souvislý graf.
hideforwardSlabě souvislý
leafideaJe orientovaný gaf, pokud je souvislý po převedení na neorientovaný graf (simetrizaci).
hideforwardSilně souvislý
leafJe orientovaný graf, pokud v něm pro každou dvojic vrcholů x,y existuje orientovaná cesta z x do y i orientovaná cesta z y do x.
leafideaSlabě souvislý orientovaný graf je silně souvislý, právě když každá jeho hrana je obsažena v nějakém cyklu.
leafideaGraf je silně souvislý, právě když jeho kondenzovaný graf má jeden vrchol.
hideNesouvislý graf
leafPokud neexistuje pro libovolné dva vrcholy cesta, která je spojí.
hideStupeň grafu
leafNejvyšší počet hran jednoho vrcholu
hideVstupní stupeň
leafPočet hran vstupujících z vrcholu
hideVýstupní stupeň
leafPočet hran vystupujících z vrcholu
hideFaktor grafu
leafLibovolný podgraf grafu, který obsahuje všechny vrcholy. Ale nemusí obsahovat všechny hrany.
hideVlastní faktor
leafJe-li graf G a faktor různý. Neobsahuje všechny hrany.
leafNechť G je slabě souvislý orientovaný graf bez smyček. Potom čtvercová podmatice redukované incidenční matice řádu n -1 je rugulární, právě když odpovídající faktor je kostrou grafu G.
hideAcyklické orientiované grafy
leafTakové orientované grafy, které neobsahují žádný cyklus. (Jsou obdobou stromů.)
leafOrientovaný graf s konečnou množinou vrcholů je acyklický právě když každý jeho neprázdný podgraf obsahuje vstupní vrchol.
leafOrientovaný graf je acyklický právě když v každém jeho neprázdném podgrafu existuje výstupní vrchol.
leafOrientovaný graf je acyklický právě když v jeho vrcholy lze seřadit do posloupnosti (v1, ...vn) tak že pro každou hranu vi,vj paltí, že i<j
leafOrientovaný graf G bez smyček je acyklický právě když graf G* vzniklý přidáním všech smyček k tranzitivnímu uzávěru G+ je grafem uspořádání. (tj E(G*) je relace na V(G+)=V(G))
leafKondenzovaný graf je acyklický orientovaný graf
hideOhodnocenost grafu
leafOhodnocený graf (G,w) je orientovaný graf jehož hranám jsou přiazeny čísla v rozsahu 0 až nekonečno. (kladně ohodnocený). Číslo w hrany e se nazývá její ohodnocení (váha).
leafPři simetrizaci neorientovaného grafu dostanou obě nově vzniklé hrany stejné ohodnocení.
hideAlgoritmy
hideDijkstrův algoritmus
leaf12.2 Vstupem je ohodnocený orientovaný graf (G, w) a jeden vrchol v z množiny všech vrcholů V(G) a jeho výstupem je vážená vzdálenost mezi vrcholem v a libovolným vrcholem x a minimální cesta z Px z vrcholu v do vrcholu x.
leafPostup pro graf G. Příprava 1. Vytvoříme si nový graf T typu strom, do kterého budeme postupně přenášet zjištěné poznatky o grafu G. Z grafu G zvolíme jeden vrchol jako počáteční. To bude vrchol stromu T. Příprava 2. jeho horní odhad vzdálenosti od něj samotného je 0 Příprava 3. horní odhad vzdálenosti všech ostatních uzlů je nekonečno Příprava 4. přímým sousedům zvoleného vrcholu přiřadíme Krok 1. Pokud je náš graf T kostrou grafu G nebo všechny ostatní vrcholy G jsou z našeho výchozího bodu nedostupné, přejdeme na Konec. Jinak pokračujeme dalšími kroky. Krok 2. Z vrcholů grafu G si vybereme si vybereme ten, který jsme ještě do našeho stromu nepřevedli a který má minimální vzdálenost od našeho výchozího vrcholu. Pokud je jich více stejných, libovolně si jeden vrchol zvolíme. Krok 3. přidáme jej do našeho stromu a přepočítáme odhad vzdálenosti pro všechny jeho sousedy. Pokud je jeho sousedem některý z vrcholů, které již v našem grafu T máme a jehož odhad vzdálenosti by měl být měnší než je dosud, změníme ho. Krok 4. Přejdeme na Krok 1. a celý cyklus budeme opakovat Konec 1. Pro každý vrchol grafu T je hledanou minimální cestou cesta z vrcholu T, která je jednoznačně určena. její váha určuje váženou vzdálenost. Pro ostatní vrcholy grafu G, které v našem grafu T nemáme cesta neexistuje a vážená vazdálenost je nekonečno.
leafGraf G je souvislý, právě když je graf T vzešlý z Dijskrtova algoritmu jeho kostrou
hideJiný popis téhož
leafdijkstrova metoda hledání minimální kostry množiny hran: 1 - Obsahuje hrany, které jsou již vybrány. 2 - Hrany, z nichž právě jedna bude v příštím kroku přidána do mn. 1. 3 - Ostatní hrany. množiny uzlů: A - Uzly příslušné k hranám z mn. 1. B - Ostatní uzly. algoritmus: 1. krok: Libovolný uzel x1 dejte do mn. A. Všechny hrany s ním incidentní do mn. 2. 2. krok: Vyberte z mn. 2 nejkratší hranu a přidejte ji do 1. Její druhý uzel (xi) dejte do mn. A (první už tam je.) 3. krok: Nechť xi je uzel, který byl naposledy přidán do mn. A. Nechť H je množina hran, jejichž jeden uzel je xi a druhý je v mn. B. Do množiny 2 potom přidejte ty hrany z H, které buď nejsou incidentní s hranami z mn. 2, anebo s nimi incidentní jsou, ale jsou kratší. Pokud jsou kratší, přesuňte ty delší z mn. 2 do mn. 3. Opakujte od kroku 2, dokud nejsou všechny uzly v mn. A. Hrany v mn. 1 tvoří potom kostru grafu. Pozn. V mn. 1 2 se nevyskytuje kružnice.
leafUrčení počtu koster v orientovaném grafu
hideHladový algoritmus
leafPro nalezení minimální kostry souvislého grafu První devinice pochází od českého matematika Otakara Borůvky 1899-1995
leafJe-li H graf a e hrana s koncovými vrcholy V(H), pak H +e je graf, který vznikne přidáním hrany e ke grafu H. Algoritmus pracuje v n{počet vrcholů} -1 krocích. V i-tém kroku je definován faktor Li, který neobsahuje kružnice. (Les) Výsledný faktor Ln-1 je minimální kostrou.
hideFloydův algoritmus
leafUrčení distanční matice ohodnoceného orientovaného grafu
hideBorůvkův algoritmus
leafHledání minimální kostry 1. nalézt kružnici 2. najít její nejdelší hranu 3. tuto hranu vypustit 4. opakovat od bodu 1. dokud je v grafu nějaká kružnice 5. je nalezena minimální kostra
hideFord-Fulkersonův
leafNalezí maximálního toku
hidePopis
leafFord - Fulkersonův algoritmus: 1. krok (Inicializační): h G: t(h) = 0 2. krok (Nalezení zlepšující cesty): Hledejte posloupnost vrcholů vi pro i = 1, 2, ..., k takovou, že buď (vi,vi+1) , t(vi,vi+1) c(vi,vi+1), nebo (vi,vi-1) , t(vi,vi-1) 0 pro (vi,vi‑1) . Pokud žádnou takovou zlepšující cestu nelze najít, jděte na krok 5. 3. krok (Určení přírůstku toku): Pro i = 1, 2, ..., k je přírůstek toku di = (c(vi‑1,vi) ‑ c(vi,vi‑1)) + t(vi,vi-1). Přírůstek toku pro vybranou cestu je d = min {di} (nejmenší přírůstek přidělený v tomto kroku této cestě.) 4. krok: d'i = min {d, c(vi‑1, vi) - t(vi‑1, vi)}; d''i = d - d'i. Je-li (vi‑1, vi) t(vi‑1, vi) = (vi‑1, vi) + d'i. Je-li (vi, vi-1) t(vi‑1, vi) = (vi‑1, vi) - d''i. Opakuj krok 2. 5. krok: Konec. Výsledkem jsou toky přidělené jednotlivým hranám. Komentář ke kroku 2: Zlepšující cesta tedy vede orientovanými hranami grafu tak, že 1)jde buď stejným směrem jako je orientace dané hrany a kapacita této hrany je menší než tok, který jí již byl přidělen, 2)anebo jde opačným směrem než je orientace dané hrany a tok, který této hraně již byl přidělen, je větší než 0. Stejná zlepšující cesta může a zpravidla i musí být zvolena víckrát. Výhoda algoritmu: Pro celá čísla vede konečný počet kroků k cíli. (Pro reálná po převodu na celá také.) Nevýhoda: Velmi pomalé díky nedokonalosti kroku 2. Další algoritmy jsou takovými modifikacemi tohoto algoritmu že se liší jen krokem 2.
hideEdmonds–Karpův algoritmus
leafJde o vylepšení Ford-Fulkersonova algorimu tak aby nebyl závislý na velikosti ohodnocení hran Postup: Vždy zvolit takovou rezervní polocestu, která má nejmenší počet hran.
hideZnačení
leafG, H - graf
leafV - množina všech vrcholů grafu (vertex)
leafE - množina všech hran grafu (edge)
leafT - tah
leafu, v, w - konkétní vrcholy z množiny V
leafe - konkrétní hrana grafu
leaf(u,v) - hrana začínající v u a končící ve v
leafn - počet vrcholů grafu
leafm - počet hran grafu
leafk - délka kružnice k - u počítání s maticí sousednosti jde o mocninu
hideBinární stromy
leafT - strom
hider - kořen stromu
leafPevně zvolený, jeden z vrcholů grafu
hideh - hloubka
leafh - hloubka vrcholu w je délka cesty P z kořene r do w
leafd+, d- stupeň vrcholu orientovaného grafu
hideM(G) - incidenční matice
leafvi - řádek odpovídající vrcholu vi
leafej - sloupec odpovídající hraně ej
leafRm - vektorový prostor
leafMR(G) - redukovaná incidenční matice
leafA, B - čtvercové podmatice M(G)
leafh(M) - hodnost incidenční matice
leafAs - podmatice sloupců
leafL - Lapalaceova matice grafu G
leafL' - Lapaceova matice s vypuštěním posledního řádku a sloupce
hideR(G) - Matice řezů
leafDůkaz 10.6
leafS(G) - Matice sousednosti
leafD(G) - distanční matice
leaf(G,w) - Ohodnocený graf
hideOhodnocení grafu (w...)
leafw(e) - Váha, ohodnocení hrany
leafM - množina hran ohodnoceného orientovaného grafu
leafw(M) - součet ohodnocení všech hran
leafP - cesta
leafw(P) - součet ohodnocení hran, kterými cesta prochází
leafd^w(u,v) - je vážená vzdálenost vrcholů u a v (= Váha minimální cesty)
leafD^w(G) - w-distanční matice, matice vážených vzdáleností
leafz Zdroj, s Stok
leafai - ohodnocení uzlu
leafr(i,j) - ohodnocení hrany
leafA - podmnožina množiny všech vrcholů grafu
leaf|x| - velikost toku x
leafTheta - velikost toku polocesty
leafřez (A,Ä)
hideOperace prováděné s grafem
leafOdstranění vrcholu
leafOdstranění hrany
hideSymetrizace grafu
leafPřevod orientovaného grafu na neorientovaný. Odstraní se smyčky, násobné hrany se nahradí jednoduchými, zapomeneme orientaci.
hideOrientace grafu
leafPřevedení neorientovaného grafu na orientovaný
hideTranzitivní uzávěr
leafTranzitivní uzávěr orientovaného grafu je orientovaný graf s původními vrcholy a platí, že existuje hrana z uzlu u do uzlu v právě tehdy, když v původním orientovaném grafu existuje libovolná orientovaná cesta z uzlu u do uzlu v .
hideKondenzace grafu
leafKondenzace orientovaného grafu G je orientovaný graf Gc, jehož vrcholy jsou kvazikomponentami grafu G a hrany, které vedly mezi těmito kvazikomponentami povedou mezi těmito novými vrcholy. Vynechají se smyčky a pokud by mělo vést více hran mezi dvěma vrcholy v témže směruje, nahradí se jedinou.
hideOhodnocení grafu
leafPřidělení číselných hodnot hranám v rozsahu 0 až nekonečno
hideZdvojení uzlů
leafProvádí se u grafu, který má vyjdářenu intenzitu uzlů a my tuto intenzitu potřebujeme převést na ohodnocenou hranu.
leaf
hidePřidání fiktivního zdroje / stoku
leafPokud má síť více zdrojů / stoků, lze je převést na tzv. fiktivní zdroj / stok, doplněním hran od fiktivního zdroje ke skutečným zdrojům nebo od skutečných stoků k fiktivnímu stoku. Ohodnocení hran bude stejné jako propustnost jednotlivých uzlů
hideZnačkování vrcholů
leafMá-li vrchol značku, znamená to, že do něj vede cesta z daného výchozího vrcholu r. Algoritmus 1. [Inicializace] Označkujeme vrchol r, ostatní vrcholy jsou bez značek. 2. [Výběr hrany] Vybereme libovolnou hranu e, jejíž počáteční vrchol má značku a koncový vrchol nikoliv. Pokračujeme podle kroku 3. Jesliže taková hrana neexistuje, výpočet končí. 3. [Značkování] Označkujme vrchol Kv(e) a pokračujme ve výpočtu dle kroku 2.
hideMatice
hideIncidenční matice M(G) - Matice sousednosti
hideTotální unimodularita - je vlastnost čtvercových podmatic M(G)
leafJe-li M(G) incidenční matice orientovaného grafu G (bez smyček) a je-li B její čtvercová podmatice řádu r pro které platí, že 1<= r <= n, potom determinant matice B je 0 nebo +-1
hideOrientovaného grafu
leafIncidenční matice orientovaného grafu G je reálná matice o rozměrech n řádků (počet vrcholů) * m sloupců (počet hran). Definovaná vztahem M(G)=(mij) kde mij = +1 pokud hrana ej vychází z vrcholu vi mij = -1 pokud hraba ej vchází do vrcholu vi jinak 0. (řádky vrcholy, sloupce hrany)
leafV každém sloupci matice M(G) jsou právě dva nenulové prvky z nichž jeden je +1 a druhý -1 Důvodem je, že každá hrana obsahuje dva vrcholy v jednom končí a v jednom začíná.
leafHodnost incidenční matice M(G) je: Maximální velikost lineárně nezávislé množiny jejích řádků. Množina všech řádků matice M(G) je lineárně závislá.
leafPro slabě souvislý graf G má matice M(G) hodnost n-1. Platí, že každá množina n-1 řádků matice M(G) je lineárně nezávislá.
leafideaOrientovaný graf G má přesně k komponent, právě když hodnost M(G) = n(počet vrcholů) - k
leafSečtením všech řádků dostaneme nulový vektor
leafideaPočet koster grafu G je roven determinantu matice A.AT Za předpokadu, že G je slabě souvislý orientovaný graf bez smyček a A = Redukovaná incidenční matice G
hideNeorientovaného grafu
leafJe naplněna hodnotami 1 a 0 Řádky odpovídají uzlům Sloupce hranám V řádku je tolik jedniček, s kolika hranami je uzel spojen Ve sloupci jsou vždy dvě jedničky.
leafHodnost nad tělesem Z2 Řádky matice M(G) jsou vektory složené z m nul a jedniček. Můžeme je tedy interpretovat jako prvky vektorového prostoru Z2^m dimenze m nad tělesem Z2. Veškerá aritmetika v tomto prostoru je prováděna "po složkách" a modulo2.
leafCharaktersický vektor - vektor, který odpovídá nějaké množině hran M
hideRedukovaná incidenční matice MR(G)
leafVznikne vypuštěním posledního řádku incidenční matice.
leafPoskytuje o grafu G úplnou informaci
hideLaplaceova matice
hideL= MR(orientovaného G) * (MR(orientovaného G) * )^T
leafJe to čtvercová matice, která se vytvoří tak že na diagonálu [1,1] až [poslední řádek, poslední sloupec] se zapíšou čísla, které vyjařují počet hran uzlu. V [1,1] tedy bude počet hran uzlu 1 ve [2,2] počet hran uzlu 2 atd. Další čísla se doplňují tak, že pokud spolu uzly nejsou spojeny hranou bude číslo 0 pokud spolu mají hranu bude číslo -1 Nad diagonálou i pod ní jsou údaje stejné. Pokud mezi sebou mají uzly 1 a 2 mají hranu, bude na souřadnicích [1,2] i [2,1] číslo -1
hideTransponovaná matice
leafPrvni řádek se převede na první sloupec Druhý řádek na druhá sloupec atd..
hideSpeciální matice
leafSpeciální matice Nulová matice O: aij = 0 Jednotková matice E: aii = 1; i≠j ⇒ aij = 0 Neutralita E: EX=X, uE=u, … Diagonální matice: i≠j ⇒ aij = 0 Symetrická matice: aij = aji, tzn. A=AT Dolní (resp. horní) trojúhelníková matice: i<j (resp. i>j) ⇒ aij = 0 Regulární matice: det A ≠ 0 Singulární matice: det A = 0
hideMatice řezů R(G)
leafKaždý její řádek je charakterstický vektor množiny hran některého z řezu grafu G. (A každému řezu odpovídá jeden řádek)
hideMatice sousednosti
hideOrientovaného grafu
leafMatice n (počet vrcholů) * n Hodnoty jsou buď 1 (pokud vede hrana z daného vrcholu do druhého) nebo 0 pokud nevede. Graf může obsahovat smyčky (hrany, které začínají i končí v tom samém vrcholu) Pokud vede hrana z vrcholu 1 do vrcholu 2 bude na pozici [1,2] 1 jinak 0
hideNeorientovaného grafu
leafVytváří se podobně, jako u neorientovaného grafu ale nejprve se provede simetrizace grafu. (každá hrana je je nahrazena dvojicí protichůdných hran) Výsledná matice je pod i nad diagonálou stejná.
hideDistanční matice
leafMatice vyjadřující vzdálenost mezi jednotlivými uzly Je sestavena tak že: 0 je na pozici, [1,1], [2,2], [n,n] protože délka cesty z uzlu do něj samého je 0 Nekonečno - je na pozici, kdy nevede cesta z jednoho uzlu do druhého Číslo 1 až n-1 - udává počet hran mezi dvěma uzly. Na pozici [1,3], počet hran které je třeba projít abychom se dostali z uzlu 1 do uzlu 3. Nejmenší počet je 1 nejvyšší je asi n-1
leafU neorientovaného grafu se nejprve provede symetrizace
hideVážená matice sousednosti
leafZohledňuje váhy hran
leafZapisují se hodnoty vah hran mezi jednotlivými uzly. Pokud je mezu uzlem v1 a uzlem v2 hrana ohodnocená číslem 5,5 Bude v matici na souřadnicích [1,2] hodnota 5,5. Pokud spolu vrcholy hranu nemají, bude hodnota 0. Pokud má uzel hranu sám se sebou, bude hodnota její váhy na diagonále.
hidew-distanční matice, Matice vážených vzdáleností
leafu ohodnoceného orientovaného grafu (G, w) s vrcholy v1, ... vn je matice D^w(G) o rozměrech n x n, kde na jednotlivých souřadnicích jsou uvedeny minimální vzdálenosti mezi jednotlivými vrcholy. Sestavit lze například pomocí Dijkstrova algoritmu, provedeného pro každý z n vrcholů. Celková výpočetní náročnost tak bude O(n^3) Další možností je metoda s tzv. čtverečkovaným sčátáním a čtverečkovaným násobením - S Diskrétní matematika str. 136
hideRozložitelná
leafTaková matice, ve které existují oblasti A= A11, A12 0, A22 Kde A11 a A22 jsou čtvercové matice řádu alespoň 1 0 je nulová matice, nebo ji lze do toho tvaru převést stejnou pemutací řádků a sloupců tzv. simulánní permutace
hideSlabě rozložitelná
leafMatice A je slabe rozložitelná, jestliže existuje permutacní matice P tak, že PA je rozložitelná. Každá rozložitelná matice je také slabě rozložitelná. (naopak to neplatí)
hideÚplně nerozložitelná matice
leafČtvercová matice, která není slabě rozložitelná, se nazývá úplně nerozložitelná.
hideStrukturální matice
leafStrukturální matice rádu n >= 1 je čtvercová matice řádu n, u níž je dána pouze struktura nulových a nenulových prvku, ale nejsou určeny jejich konkrétní hodnoty Strukturální matice budeme značit obvyklým zpusobem s „krížkemÿ na místě nenulových prvků.
hideZjištění určité skutečnosti
hideZjištění acykličnosti grafu
leafZda graf obsahuje nebo neobsahuje kružnici
hidePočet koster grafu orientovaného grafu
hide9.8 Věta
leafNechť G je slabě souvislý orientovaný graf bez smyček a A = Determinantu incidenční matice grafu G. Potom počet koster grafu G je roven determinantu matice A . A^T
hide9.7 Cauchy-Binetova věta
leafNechť B je matice o rozměrech r * s, kde r <= s Potom platí, že determinant(B * B^T) = Suma všech I (determinantu BI)^2 kde I probíhá všechny r-prvkové množiny sloupců a BI je čtvercová podmatice matice B, určená sloupci z množiny I.
hidePočet koster neorientovaného grafu
hidePostup - Příklad 9.11
leaf1. Ke grafu vytvoříme Lapaceovu matici 2. Z matice vynecháme poslední a řádek a sloupec 3. Spočítáme determinant této matice 4. A to je počet koster neorientovaného grafu
hidePočet koster úplného neorientovaného grafu
leafÚplný graf (tedy takový, který má všechny vrcholy navzájem propojeny hranami) a má 2 a více vrcholů má n na (n-2) možných koster
hideZjištění počtu komponent orientovaného grafu
leafOrientovaný graf má přesně k komponent, právě když hodnost incidenční matice se rovná počtu vrcholů mínus počet komponent
leafPro slabě souvislý graf má incidenční matice hodnost (počet vrcholů-1)
hideZjištění počtu komponent neorientovaného grafu
leafVěta 10.1 Hodnost h2 matice M(G) je rovna n-k, právě když G má k komponent.
hideUrčit faktor grafu
leafKapitola 10.3
hideZjištění počtu sledů dané délky
leafVěta 11.2 Nechť G je orientovaný graf a číslo k >=0. Potom hodnota prvku na souřadnicích [i, j] umocněné matice sousednosti na k je rovna počtu sledů délky k z vrcholu i do vrcholu j. A polidštěně Hodnoty v k-té mocnině matice sousednosti udávají počet sledů délky k mezi jednotlivými vrcholy. Postup: 0. Pokud je graf neorientovaný, provedeme jeho symetrizaci (rozdvojit a osměrovat hrany) 1. Vytvoříme matici sousednosti orientovaného grafu 2. Máme první mocninu matice sousednosti, která říká, kolik sledů délky 1 vede mezi vrcholy. Například číslo na souřadnicích [1,2] řáká, kolik sledů délky 1 vede mezi vrcholy v1 a v2. Číslo na souřadnicích [1,1] udává počet sledů délky jedna z vrcholu v1 zase do vrcholu v1, tedy, jestli má vrchol v1 smyčku. 3. Umocníme matici sousednosti (vynásobíme ji stejnou maticí). Nyní čísla udávají počet sledů délky 2 mezi jednotlivými vrcholy. 4. Dalším umocňováním zjišťujeme další počty sledů danné délky (podle umocnění) mezi danými vrcholy.
hideUrčení acykličnosti grafu
leafZ mocnin matice sousednsti lze algebraickým způsobem určit zda je daný graf acyklický. Tvrzení 11.8 Orientovaný graf G je acyklický, právě když nějaká mocnina jeho matice sousednosti je nulová.
hideUrčení vzdálenosti mezi vrcholy
leafJednotlivé prvky distanční matice udávají délku nejkratší cesty mezi jednotlivými body. Na diagonále jsou 0 protože délka cesty z bodu do něj samotného je 0 Tam kde cesta není se udává nekonečno. (délky dle mocniny distanční matice)
leafPostup: U menších grafů se dá sestavit "od oka" U větších je doporučen tento postup 1. vytvoření matic sousednosti 1a. pro 0 mocninu (jen jedničky na diagonále) 1b. první mocninu - uzly ve vzdálenosti 1 . . 1n-1 pro nejvtší možnou vzdálenost cesty - což je n(počet vrcholů)-1 2. Začneme zapisovat do distanční matice - píšeme čísla mocnin ve kterých se poprvé objevil sled mezi vrcholy 2a - dle 0 mocniny matice sousednosti tak zapíšeme do distanční matice na diagonálu 0 2b - Tam kde se objeví číslo zapíšeme do distanční matice 1 - jednou zapsaná čásla už nepřepisujeme 2n - Tam kde dosud nejsou zapsaná čísla, napíšeme nekonečno
hideZda je graf silně souvislý
leafJeho distanční matice neobsahuje žádné znaky nekonečno
hideVyhledání maximálního toku
leafFord-Fulkerson Velikost maximálního toku je rovna propustnosti minimálního řezu oddělujícího zdroj a stok Postup: 1. Jako výchozí tok x zvolme nulový tok: xij := 0 pro každou hranu (i, j) z množiny všech hran grafu G 2. Jestliže v grafu existuje nějaká rezervní polocesta, upravíme tok podle ní. 2a - pokud je rezervní polocesta souhlasně orientovaná 2b - pokud je nesouhlasně orientovaná 2c - pokud je shodná - opakuje bod 2. dokud existuje rezervni polocesta 3. je nalezen maximalni tok
hideZjištění rozložitelnosti matice
leafPřevodem na grafovou úlohu a) Je-li graf silně souvislý, pak je matice nerozložitelná. b) str. 14 pracovních textů k TGD1
leafVeta 3.3. Čtvercová matice A je slabě rozložitelná práve když v jejím bigrafu existuje stabilní množina.
hideZda je matice regulární
leafKaždá regulární matice má lineární bigraf,
leafVeta 3.5. Čtvercová strukturální matice je genericky regulární práve když její bigraf B(A) má perfektní párování.
hideSložitost řešení
hideObecně
leafPolynomiální - maximální časovou náročnost je možné odhadnout polynomem n, n log n, n^2, n^3, n^4 .... Tyto algoritmy často pracují deterministicky = v každém kroku je znám krok další Exponenciální u algoritmů snažících se problém vyřešit hrubou sílou (postupně vyzkoušet všechny možnosti) 2^n -probrat všechny podmnožiny dané n-prvkové množiny 2! -probrat všechny permutace n-prvkové množiny do sebe n^n -probrat všechna zobrazení n-prvkové množiny do sebe
leafTřída P - Polynomiální - je znám algoritmus, jak danou úlohu vyřešit s polynomiální časovou náročností Třída NP - Nedeterministicky Polynomiální - Není znám algoritmus, který by danou úlohu pomáhal řešit v polynomiálním čase. Třída NPC (NP complet) NP-úplné - úlohy NP, u kterých, kdyby se podařilo nalézt efektivní řešení, vyrešila by se najednou celá skupina podobných problémů
hideZda je graf či není Eulerovský
leafSložitost polynomiální
hidemessagebox_warningZda je graf, nebo není Hamiltonosvký
leafProblém NP-úplný
hideDijkstrův algoritmus
leafO(n^2)
hideNalezení distanční matice
leafO(n^4)
leafVzdálenost libovolných dvou vrcholů je buď menší než n nebo nekonečná, stačí pro zjištění distanční matice spočítat n-1 mocnin matice sousednosti. Výpočet každé mocniny spočívá ve vynásobení dvou matic o rozměrech n x n, které vyžaduje O(n^3) aritmetických operací. Celková doba výpočtu tak bude O(n^4)
hideZda je graf silně souvislý
leafO(n^4)
leafStejně jako u nalezení distanční matice, protože graf je silně souvislý, pokud distanční matice neobsahuje nekonečno a není, ppokud obsahuje.
hideZjištění acykličnosti grafu
leafO(n^4) Výpočtem mocnin matice sousednosti dle tvrzení 11.8
hideVytvoření matice vážených vzdáleností (w-distanční)
leafO(n^3) Pomocí Dijkstrova algoritmu provedeného pro každý vrchol zvlášť.
leafO(n^4) Pomcí sestrojením pomocí čtverečkovaného sčítání a čtverečkovaného násobení
hideHladový algoritmus
leafO(mn^2) - m počet hran, n počet vrcholů
leafZa pomoci vylepšení známého jako Kruskalův algoritmus O(mn)
hidemessagebox_warningProblém obchodního cestujícího
leafTéměř n! - faktoriál počtu vrcholů
hidebookmarkProblém SAT
leafNP-úplný “problém splnitelnosti logických formulí” (anglicky “satisfiability problem” )
leaf2-SAT - je ještě polynomiální
hidebookmarkk-obarvitelnost
leafNP-úplný Obarvitelnost grafu k barvami
hidebookmarkExistence kliky velikosti k
leafNP-úplný
hidebookmarkProblémem IND
leafProblém existence nezávislé množiny uzlů dané velikosti – IND (angl “independent set” - nezávislá množina)
hideNalezení nevetšího toku
leafAlgoritmem Ford-Fulkerson -je bohužel závislý na velikosti ohodnocení hran 2Q
leafEdmonds–Karpuv algoritmus m^2n m= počet hran, n= počet uzlů
hideZdroje
leafSkripta - Diskrétní matematika R. Čada, T. Kaiser, Z. Ryjáček
leafPracovní texty přednášek Teorie grafů a diskrétní optimalizace 1 www.kma.zcu.cz/tgd1
leafDoc.RNDr.Milan BERKA,CSc. http://home.eunet.cz/berka/o/grafy.htm