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}¹⁾ | u, v ∈ U ∧ u ≠ v}

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.

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

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

Cesta je posloupnost P = (v₀, e₁, e₁, …, eₙ, vₙ) pro kterou platí eᵢ = {vᵢ₋₁, vᵢ}³⁾, vᵢ ≠ v_j, i ≠ j. 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).

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.

Strom je spojitý graf bez cyklů.

Les je nespojitý graf jehož komponenty jsou stromy.

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'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!