MAT 10. Orientované grafy

Card Set Information

Author:
hrbi
ID:
222348
Filename:
MAT 10. Orientované grafy
Updated:
2013-06-04 06:17:46
Tags:
mat
Folders:

Description:
msz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Orientovaný graf
    • G=(U,H,e), kde e:H->{(u,v)|u,v∈U} je zobrazení, které každé hraně přiřadí orientovanou dvojici uzlů (u,v). Říkáme, že hrana vede z uzlu u do uzlu v.
  2. Vstupní a výstupní stupeň uzlu
    deg+(u)=|M|, deg-(u)=|N|, kde M={h∈H|∃v∈U:e(h)=(v,u)} a N={h∈H|∃v∈U:e(h)=(u,v)}
  3. Symetrická orientace grafu
    • Mám-li obyčejný G=(U,H), pak je možno dodefinovat orientovaný graf G'=(U',H',e) tak, že pro každou hranu {u,v}∈H existují v H' právě dvě hrany h, h' takové, že e(h)=(u,v) & e(h')=(v,u). Přitom v H' žádné jiné hrany nejsou.
    • Takovýto graf se nazývá symetrickou orientací grafu G. Jinými slovy, hrana v obyčejném grafu mezi uzly u a v se nahradí oběma orientovanými hranami mezi těmito uzly v novém grafu.
  4. Orientace grafu
    Mám-li obyčejný graf G=(U,H), je možno dodefinovat orientovaný graf G'=(U',H',e) tak, že pro každou hranu {u,v}∈H existuje v H' jediná orientovaná hrana h taková, že e(h)=(u,v) nebo e(h)=(v,u) a přitom H' žádné jiné hrany neobsahuje.
  5. Symetrizace grafu
    • Mám-li orientovaný G=(U,H,e), pak existuje jednoznačně obyčejný G'=(U',H',e), který se nazývá symetrizací grafu G.
    • Položíme H'={{u,v}|u,v∈U, u!=v, ∃h∈H:(e(h)=(u,v) | e(h)=(v,u))}.
  6. Souvislost, silná souvislost
    • Orientovaný G=(U,H,e) je souvislý, jestliže jeho symetrizace G'=(U',H') je souvislý graf.
    • Orientovaný G=(U,H,e) je SILNĚ souvislý, jestliže pro libovolné dva uzly u,v∈U existuje orientovaná cesta z u do v.
  7. Turnaj
    • Orientovaný graf T=(U,H,e) bez smyček se nazývá turnajem, když pro každou množinu uzlů {u,v},u,v∈U, u!=v existuje právě jedna hrana h∈H taková, že e(h)=(u,v) | e(h)=(u,v).
  8. Eulerovský graf
    Orientovaný graf G=(U,H,e) se nazývá eulerovský, jestliže v něm existuje uzavřený orientovaný tah obsahující všechny jeho hrany.
  9. Dijkstra
    • neporadí si se zápornou cenou hran
  10. Floyd-Warshall
    • poradí si se zápornou cenou hran
    • neporadí si se záporným cyklem/smyčkou
    • matice

What would you like to do?

Home > Flashcards > Print Preview