1 | 2 | 3    další >>

Vlatnosti neorientovaných grafů

Teoretická informatika - Semestrální práce


Vypracoval: Bedřich Lacina
Datum: říjen, listopad, prosinec 2002
Použitá literatura: Josef Kolář - skriptum Teoretická informatika - Česká informatická společnost - Praha 2000


Definice 1: Neorientovaný graf
Nechť H, U jsou libovolné disjunktní množiny a R : H -> U x U zobrazení, kde U x U je množina všech neuspořádaných dvojic [u,v], u,v nalezi.gif (1K) U. Neorientovaným grafem nazýváme uspořádanou trojici G = <H, U, R>, prvky množiny H jsou hranami grafu G, prvky množiny U uzly grafu G a zobrazení R incidencí grafu G.


obneorgr.gif (2K) Pojmy:
Pod pojmem incidence hrany h s uzly u, v, píšeme R(h) = [u, v], rozumíme, že každá hrana má dva krajní uzly. Pokud jsou uzly u, v stejné, nazýváme hranu smyčkou (viz Obrázek 1 hrana a). Pokud ale uzel neinciduje s žádnou hranou, nazýváme uzel izolovaným uzlem (viz Obrázek 1 uzel z). Pokud v grafu existují hrany se shodnou množinou krajních uzlů, nazíváme je rovnoběžné hrany (viz Obrázek 1 hrany d, e).
Graf, ve kterém existuje alespoň jedna dvojice rovnoběžných hran, se nazývá multigraf (tedy graf na Obrázku 1 je multigraf). Naopak graf bez rovnoběžných hran se nazývá prostý. Abychom tedy z grafu na Obrázku 1 udělali prostý graf, musíme odstranit jednu z rovnoběžných hran d, e. Na Obrázku 2 je tento prostý neorientovaný graf po dostranění hrany e.
Prostý graf bez smyček nazýváme obyčejný graf. Abychom z grafu na Obrázku 2 vytvořili obyčejný graf, musíme odstranit smyčku a (viz Obrázek 3).
Obrázek 1 - Obecný neorientovaný graf
prostygr.gif (2K) obycgr (2K)
Obrázek 2 - Prostý neorientovaný graf Obrázek 3 - Obyčejný neorientovaný graf

Definice 2: Úplný graf
Úplným grafem
nazýváme obyčejný graf KU = <( unad2.gif (1K)) , U>; pro n přirozené bude Kn označovat úplný graf o n uzlech. Prázndým grafem nazýváme graf D0= <0, 0>. Diskrétním grafem nazýváme graf DU = <0, U>; pro n přirozené bude Dn označovat diskrétní graf o n uzlech.


Pojmy:
Úplný graf je tedy takový, ve kterém je každý uzel propojen s každým právě jednou hranou, kromě sama sebe (v obyčejném grafu nejsou smyčky). Abychom z obyčejného grafu na Obrázku 3 vytvořili úplný graf, musíme odstranit izolovaný uzel z a propojit uzly u, y hranou e (viz Obrázek 4). Prázdný graf je graf bez uzlů a hran. Diskrétní graf se skládá pouze z izolovaných uzlů. Abychom tedy z obyčejného grafu na Obrázku 3 udělali diskrétní graf, musíme odstranit všechny hrany: b, c, d, f, g (viz Obrázek 5).
uplnygr.gif (2K) diskretg.gif (1K)
Obrázek 4 - Úplný graf o čtyřech uzlech - K4 Obrázek 5 - Diskrétní graf

Definice 3: Podgraf
Graf G' = <H', U', R'> nazýváme podgrafem grafu G = <H, U, R> (zapisujeme G' podmn.gif (1K) G), jestliže platí:

(H' podmn.gif (1K) H) a zároveň (U' podmn.gif (1K) U) a zároveň pro všechny hrany h nalezi.gif (1K) H': (R'(h) = R(h)).


Pojmy:
Podgraf G' = <H', U', R'>, jehož množina uzlů je shodná s množinou uzlů grafu G, nazýváme faktorem (též hranovým podgrafem grafu G). Podgrafy grafu na Obrázku 1 můžeme nazvat všechny grafy na obrázcích: Obrázek 2, Obrázek 3, Obrázek 5; další jsou na obrázcích: Obrázek 6 (odebrání hran b, g) a Obrázek 7 (odebrání uzlu y a hran b, c, f, g). Hranovým podgrafem (faktorem) grafu z Obrázku 1 můžeme nazvat grafy: Obrázek 2, Obrázek 3, Obrázek 5, Obrázek 6 (grafy mají shodné uzly u, v, x, y, z).
podgraf1.gif (2K) podgraf2.gif (2K)
Obrázek 6 - Hranový podgraf (faktor) Obrázek 7 - Podgraf grafu na Obrázku 1

Definice 4: Sjednocení, průnik
Sjednocením, resp. průnikem grafů G1 = <H1, U1, R1> a G2 = <H2, U2, R2> nazýváme graf

G = <H1 sjednoc.gif (1K) H2, U1 sjednoc.gif (1K) U2, R1, sjednoc.gif (1K) R2>      (píšeme G = G1 sjednoc.gif (1K) G2), resp.
G = <H1 prunik.gif (1K) H2, U1 prunik.gif (1K) U2, R1, prunik.gif (1K) R2>      (píšeme G = G1 prunik.gif (1K) G2).          

Dva grafy, jejichž průnikem je prázdný graf, nazýváme disjunktními grafy.


Definice 5: Rozdíl, doplněk grafů
Nechť G1 je podgrafem grafu G. Rozdílem grafů G a G1 (značíme G - G1) nazýváme takový minimální podgraf G2 podmn.gif (1K) G, pro který platí G = G1 sjednoc.gif (1K) G2. Doplňkem obyčejného grafu G = <H, U, R> nazýváme graf -G = KU - G, tzn. graf vzniklý odečtením grafu G od úplného grafu s množinou uzlů U.


doplnek.gif (2K) Pojmy:
Většinou se omezujeme na studium končných grafů, tzn. grafů s konečnými množinami uzlů i hran. Pod pojmem graf budeme rozumět konečný neprázdný neorientovaný graf bez smyček a izolovaných uzlů. Doplňkem grafu z Obrázku 3 je graf na Obrázku 8 (odstraníme všechny hrany: b, c, d, f, g a doplníme chybějící hrany k uzlu z: h, i, k, l a hranu j mezi uzly u, y).
Obrázek 8 - Doplněk grafu na Obrázku 3

            1 | 2 | 3    další >>