GRAFY GRAFY Graf G je definován jako uspořádaná dvojice ( V,E), kde V je množina vrcholů grafu (též značíme(G(Vr )) a E (G(E)), je množina hran. Každá hrana je dvouprvkovou podmnožinou množiny vrcholů: množina E se skládá z dvouprvkových množin (hrana „spojuje" vrcholy, které jsou v ní obsaženy). příklad • Příkladem grafu může být dvojice (V,E), kde • V = {1, 2, 3, 4, 5, 6} • E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4; 5}, {4, 6}} možné znázornění příkladu GRAFY Sousední vrcholy. Řekneme, že dva vrcholy jsou sousední, pokud mezi nimi vede hrana (jinými slovy, u, v E V jsou sousední, pokud {u, v} E E). Stupeň vrcholu je počet hran, které z daného vrcholu vychází (neboli stupeň vrcholu x je | {{u, v} E E Iu- x A v = x}\). Podgraf grafu G = (V,E) je graf G' = (V ',£')takový, že V' c v a E' c E. Je důležité, aby i G' byl graf, tedy aby platilo \/{u, v} E E' (u E V' A v E V'). (Podgraf tvoří vybrané vrcholy a hrany původního grafu.) Izomorfismus mezi grafy G s G' je bijekce / : V (G) -> V [G')f kde platí \/{u, v} E G(E) ({ f (u), f (v)} E G(E')). Izomorfismus říká, že grafy jsou shodné, až na pojmenování vrcholů-je možné přejmenovat vrcholy tak, abychom z jednoho grafu dostali druhý. Řekneme, že grafy jsou izomorfní (shodné), pokud mezi nimi existuje izomorfismus (tedy jsme schopni nalézt bijekci f, která splňuje kritérium izomorfismu). o TYPY GRAFU • Souvislý graf: graf ve kterém existuje cesta mezi každými dvěma vrcholy. (Opakem je graf nesouvislý). • Acyklický graf: graf, který neobsahuje cyklus. Též les, protože jeho souvislé části jsou stromy. příklady grafů ORIENTOVANÝ GRAF Orientovaný graf. Hrany grafu jsou orientovány. U každé hrany rozeznáváme zdrojový a cílový vrchol. Formální definice: Množina hran není množinou (neuspořádaných) dvouprvkových podmnožin, ale uspořádaných dvojic, kde je jednoznačně dán první (zdrojový vrchol) a druhý (cílový vrchol) prvek. OHODNOCENÝ GRAF Ohodnocený graf. Přiřazuje každé hraně reálné číslo, které nazýváme ohodnocení. (Tato vlastnost nám umožní modelovat např. vzdálenost mezi místy na mapě.) Formálně k definici grafu přidáme ohodnocovací funkci e : E(G) -> R. příklad OG MULTIGRAF Multigraf povoluje více hran mezi stejnou dvojicí vrcholů. Povoluje hrany začínající i končící ve stejném vrcholu, tzv. „smyčky". Možnosti formální reprezentace takovéto struktury jsou různé, např. ke každé hraně (dvouprvkové množině) můžeme přidat třetí prvek, index, který odliší dvě hrany mezi stejnou dvojicí vrcholů. Přidaný prvek pak nesmí být obsažen v množině vrcholů. GRAF JAKO RELACE Množina hran v orientovaném grafu je množina uspořádaných dvojic. Je tedy možné na graf pohlížet jako na binární relaci na množině vrcholů. Můžeme tedy graf reprezentovat jako tabulku příslušné relace, tzv. matici sousednosti. Neorientovaný graf lze v tomto formátu zapsat jako symetrickou relaci, matice sousednosti je tedy v tomto případě byla symetrická. příklad vrchol 1 2 3 4 5 6 1 0 1 0 0 1 0 2 1 0 1 0 1 0 3 0 1 0 1 0 0 4 0 0 1 0 1 1 5 1 1 0 1 0 0 6 0 0 0 1 0 0 DALŠÍ SPOJENÉ POJMY Délkou cesty v grafu rozumíme počet hran v této cestě. V případě ohodnoceného grafu délkou cesty obvykle rozumíme součet ohodnocení hran této cesty. Délku nejkratší cesty mezi dvěma vrcholy pak označujeme jako vzdálenost mezi vrcholy. Souvislé komponenty v grafu jsou jeho největší souvislé podgrafy - na obrázku je poznáme snadno, jde o souvislé „ostrůvky" které vzájemně nejsou spojeny žádnou hranou. Jinými slovy lze také říct, že se jedná o největší podgrafy takové že mezi každými dvěma vrcholy každého takového podgrafu vede cesta. APLIKACE Příkladem lingvistického využití teorie grafů je syntaktický strom, kterým znázorňujeme syntaktické odvození věty. Kořenem je vrchol , listy jsou pak slova dané věty. SYNTAKTICKÝ STROM saw man with telescope