Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- msz:grafy_obycejne [09. 06. 2012, 12.23:47] – [Souvislost grafu] pitel
+++ msz:grafy_obycejne [15. 08. 2026, 08.38:05] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== 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!

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku