Teorie grafů
Graf je uspořádaná dvojce množin V a E, kde množina V je množina vrcholů grafu a množina E je množina hran.
G = (V,E)
Úplný graf je taková graf, ve kterém jsou každe dva vrcholy spojene hranou.
Bipartitní graf - množinu vrcholu lže roždelit na dve Časti, pricemž ž každeho vrcholu jedne Časti jde hrana použe do vrcholu druhe casti a naopak. Pokud jde ž každeho vrcholu jedne casti hrana do každeho vrcholu druhe cásti, mluvíme o úplném bipartitním grafu.
Podgraf grafu G je graf H, ktery vžnikl odebraním nekterách vrcholu a hran ž puvodního grafu G.
Pri odebrání vrcholu je nutne vymažat všechny hrany vedoucí do/ž tohoto vrcholu. Pokud byly odebrany jen tyto hrany, nažává se podgraf indukovaný. Pokud byly odebrany i jine hrany, jde obecne o podgraf.
• Graf H je podgrafem grafu G, jestliže V (H) C V (G) a E(H) C E (G).
• Graf H je indukovaným podgrafem grafu G, jestliže V (H) C V (G).
1
Dva grafy G = (V,E) a G1 = {V,E1) nazýváme isomorfní, jestliže existuje bijektivní zobrazení f : V — V1 tak, že platí:
[x,y}£ E &{f{x),f(y)}e E'.
Cesta v grafu - posloupnost vrcholu a hran (v0, e1; v1,..., et, kde vrcholy v0,...,vt jsou navzájem ruzne vrcholy grafu G a pro každe i = 1,2,...,t je ej = {vi_i,vi} je prvkem E(G).
RŘekneme, ze graf G je souvislý, jestlize pro kazde jeho dva vrcholy x a y existuje v G cesta z x do y.
Kružnicí (cýklem) v grafu rozumíme posloupnost vrcholu a hran (v0,e1,v1,... ,et,vt = v0), kde vrcholy v0,..., vt-1 jsou navzájem ruzne vrcholy grafu G a pro kazde i = 1, 2,..., t je ej = {vj_i,vj} je prvkem E(G).
2
Nechť G je graf, v jeho vrchol. Symbolem degG(v) označme počet hran grafu G obsahujících vrchol v. Číslo degG(v) nazveme stupnem vrcholu v v grafu G.
2 1
2 3
Necht' G = (V, E) je graf s n vrcholy. Oznacme vrcholy v1,... ,vn (v nejakím libovolnem poradí). Matice sousednosti grafu G je ctvercova matice A(G) = (aij)nj=1 definovana predpisem:
1    pro {vi, v j } G E 0 jinak
1 2
011
10 0)
100
• Pro neorientovane grafy platí, ze jejich matice sousednosti jsou symetricke.
• Pokud je graf G úplný, obsahuje matice A(G) s výjimkou hlavní diagonaly same jednicky.
1. Zapiste matici sousednosti pro graf:
aij
AT
Orientovaný graf G je dvojice (V, E), kde E C V x V. Prvky E nazyvame Šipky nebo orientovane hrany. Orientovaní hrana e mí tvar Ríkame, ze tato orientovana hrana
vychaízíí z x a koncí v y.
Graf 1
2. Zapište matici sousednosti pro Graf 1.
3
Funkci, která k hranám přiřadí čísla nazveme ohodnocením hran a označíme ji w.
w : E(G) — (0, oo)
Strom je souvislý graf neobsahující kružnici.
Kostra grafu - libovolný podgraf, který hranami spojuje vSechny vrcholy původního grafu a žaroveň sam neobsahuje žadnou kružnici (tj. jde o strom).
Necht' G = (V, E) je orientovaný graf. Množinu W C V (tedy podmnožinu množiny vrcholu) nažveme jadrem grafu G, jestliže platí nasledující dve podmínky:
(a) Je-li (u0, u1) G E a u0 G W, pak u\ ^ W.
(b) Jestliže u0 G W, pak existuje u1 G W tak, že (u0,u1) G E.
4
3. Určete jádro grafu:
Více na http://teorie-grafu.elfineer.cz/
5