Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:msz:grafy_obycejne

Obyčejné grafy

Graph (mathematics)

Graf G = (U, H), kde:

  • U je konečná množina uzlů (vrcholů)
  • H je konečná množina hran, H ⊆ {{u, v}1) | u, vUuv}

Ohodnocený graf má u hran přiřazenou jejich váhu.

Úplný graf je, když je každý uzel spojený s každým. |H| = n(n − 1) / 2.

Stupně uzlů

Stupeň uzlu je počet hran které z něj vycázejí.

Suma stupňů všech uzlů je 2|H|2), protože každá hrana má 2 konce.

Cesty a kružnice

Cesta je posloupnost P = (v₀, e₁, e₁, …, eₙ, vₙ) pro kterou platí eᵢ = {vᵢ₋₁, vᵢ}3), vᵢvj, ij. Je to tedy posloupnost vrcholů, pro kterou platí, že v grafu existuje hrana z daného vrcholu do jeho následníka. Žádné dva vrcholy (a tedy ani hrany) se přitom neopakují.

Kružnice je cesta která má počáteční a koncový uzel stejný.

Pokud cesta (nebo kružnice) prochází všemi vrcholy, je to Hamiltonská cesta (nebo kružnice).

Souvislost grafu

Graf je souvislý, pokud mezi každými dvěma uzly existuje cesta. Prostě pokud se graf neskládá z izolovaných podgrafů (komponent), je souvislý.

Komponenta grafu je nějaký izolovaný podgraf. Pokud je graf souvislý, existuje právě jedna.

Most je ta hrana, kterou když odstraníme tak získáme dvě komponenty.

Stromy

Strom je spojitý graf bez cyklů.

Les je nespojitý graf jehož komponenty jsou stromy.

Kostry

Pokud budeme z grafu odebírat hrany až dostaneme strom, je to kostra grafu.

Zajímavé to začne být pokud máme ohodnocený graf a hledáme nejmenší kostru.

Kruskalův a Primův algoritmus pro hledání minimální kostry ohodnoceného grafu

  • Kruskal's algorithm – Vybírej nejlevnější hrany dokud nemáš pokryté všechny uzly. Nesmí vzniknout kružnice!
  • Prim's algorithm – Zvol si uzel, a z něj jdi nejlevnější hranou. Teď máš 2 uzly, zase přidej nejlevnější hranu. Atd. dokud nemáš všechny uzly. Zase bacha na kružnice!
1)
Kdyby to byl orientovaný graf, byla by to uspořádaní dvojice (u, v).
2)
Dvakrát počet hran
3)
Případně (vᵢ₋₁, vᵢ) pro orientované grafy.
/var/www/wiki/data/pages/pitel/msz/grafy_obycejne.txt · Poslední úprava: 03. 07. 2012, 13.53:31 (upraveno mimo DokuWiki)