Poznámky k teorii grafů

Souvislost grafu ve smyslu: Počet všech vrcholů je alespoň stupně n/2

List stromu = každý vrchol, který má jen jednu hranu

Má-li strom alespon dva vrcholy, pak má alespon dva listy.

Každý vrchol je s každým propojen hranou

Nemá žádné hrany

Aby 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ů.

Souvislý 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.)

Obsahuje 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.

Graf G je stromem, právě když pro každé dva vrcholy existuje právě jedna cesta.

Graf G je stromem, právě když pro každé dva vrcholy existuje právě jedna cesta.

Graf je strom, kprávě když je souvislý a má n-1 hran

Graf je strom právě když je souvislý a nemá žádný souvislý vlastní faktor

Graf G je strom, právě když je souvislý a nemá žádný souvislý vlastní faktor

Používá se k modelování rozhodovacích procesů

Každý strom, v němž má každý vrchol nejvýše dva potomky.

Bigraf 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.

Graf je bigrafem, právě když je graf acyklický a každý uzel je vstupní nebo výstupní.

Symetrizací bigrafu je biparitní neorientovaný graf

Ú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

def 3.7

Počet všech hran spojených s vrcholem

Vrchol orientovaného grafu, který nemá vstupní hrany

Vrchol orientovaného grafu, který nemá výstupní hrany

Bez určení odkud kam vedou

Mají směr, výchozí a cílový uzel

Začíná a končí ve stejném vrcholu

Pokud existuje cesta z vrcholu x do v a z v do z, je logické, že bude existovat cesta z x do z

Uzavřený sled, který prochází všemi vrcholy grafu právě jednou

Začíná i končí stejným vrcholem

Je nazýván Eulerovským, pokud používá každou hranu grafu právě jednou

Maximální slabě souvislé podgrafy. (Maximální podgrafy po převodu grafu na neorientovaný graf.)

U orientovaného grafu G každý jeho indukovaný podgraf na množině vrcholů, která tvoří některou ze tříd ekvivalence.

Laicky: čá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.

Objevuje se v úlohách, kde se hledá optimální propojení objektů.

G a G' se liší pouze „očíslováním“ svých vrcholů.

Každý souvislý graf G obsahuje vrchol v s vlastnotí, že pokud v odebereme, G zůstane souvislý

V souvislém grafu je m (počet hran) vetší, nebo roven n (počtu vrcholů) -1

Ma-li každý vrchol grafu alespoň n(počet vrcholů) / 2 hran, pak je G souvislý graf.

Je orientovaný gaf, pokud je souvislý po převedení na neorientovaný graf (simetrizaci).

Je 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.

Slabě souvislý orientovaný graf je silně souvislý, právě když každá jeho hrana je obsažena v nějakém cyklu.

Graf je silně souvislý, právě když jeho kondenzovaný graf má jeden vrchol.

Počet hran vstupujících z vrcholu

Počet hran vystupujících z vrcholu

Je-li graf G a faktor různý. Neobsahuje všechny hrany.

dijkstrova 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.

Ford - 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.

Pevně zvolený, jeden z vrcholů grafu

h - hloubka vrcholu w je délka cesty P z kořene r do w

Je-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

Incidenč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)

V 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á.

Hodnost 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á.

Pro 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á.

Orientovaný graf G má přesně k komponent, právě když hodnost M(G) = n(počet vrcholů) - k

Sečtením všech řádků dostaneme nulový vektor

Cauchy-Binetova věta

Poč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

Je 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.

Hodnost 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.

Charaktersický vektor - vektor, který odpovídá nějaké množině hran M

Je 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

Matice 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

Vytváří 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á.

Matice 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í)

Čtvercová matice, která není slabě rozložitelná, se nazývá úplně nerozložitelná.

Nechť 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

Nechť 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.

1. 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

Ú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