====== Obyčejné grafy ======
{{ http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/300px-6n-graf.svg.png}}
[[wp>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//}((Kdyby to byl orientovaný graf, byla by to uspořádaní dvojice (//u//, //v//).)) | //u//, //v// ∈ //U// ∧ //u// ≠ //v//}

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

**[[wp>Complete graph|Úplný graf]]** je, když je každý uzel spojený s každým. |//H//| = //n//(//n// − 1) / 2.
===== Stupně uzlů =====
**[[wp>Degree (graph theory)|Stupeň uzlu]]** je počet hran které z něj vycázejí.

Suma stupňů všech uzlů je 2|//H//|((Dvakrát počet hran)), protože každá hrana má 2 konce.
===== Cesty a kružnice =====
**[[wp>Path (graph theory)|Cesta]]** je posloupnost //P// = (//v//₀, //e//₁, //e//₁, ..., //eₙ//, //vₙ//) pro kterou platí //eᵢ// = {//vᵢ//₋₁, //vᵢ//}((Případně (//vᵢ//₋₁, //vᵢ//) pro orientované grafy.)), //vᵢ// ≠ //v<sub>j</sub>//, //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í.

**[[wp>Cycle (graph theory)|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 [[wp>Hamiltonian path|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ý.

**[[wp>Connected component (graph theory)|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 =====
**[[wp>Tree (graph theory)|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 **[[wp>Spanning tree|kostra grafu]]**.

Zajímavé to začne být pokud máme ohodnocený graf a hledáme [[wp>Minimum spanning tree|nejmenší kostru]].
===== Kruskalův a Primův algoritmus pro hledání minimální kostry ohodnoceného grafu =====
  * [[wp>Kruskal's algorithm]] -- Vybírej nejlevnější hrany dokud nemáš pokryté všechny uzly. Nesmí vzniknout kružnice!
  * [[wp>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!