Studijní materiály

Zpět

Hromadně přidat materiály

Termíny z teorie grafů

A0B01LGR - Logika a grafy

Hodnocení materiálu:

Vyučující: prof.RNDr. Marie Demlová CSc.

Popisek: Seznam a vysvetlení pojmů z teorie grafů

Zjednodušená ukázka:

Stáhnout celý tento materiál

ouvislosti.
Kondenzace - Kondenzace je taková operace, která ze silné komponenty vytvoří jeden uzel.
Kostra grafu - Kostra souvislého grafu G je takový podgraf souvislého grafu G na množině všech jeho vrcholů (viz. faktor), který je stromem.
Kruskakův algoritmus - Algoritmus využívající se k nalezení minimální kostry grafu, jehož hrany mají nezáporné ohodnocení. U souvislého grafu hledá podmnožinu hran, která tvoří strom obsahující všechny uzly, s tím, že selková váha hran grafu je minimální. V případě grafu o více komponentách, hledá algoritmus les minimálních koster, tedy minimální kostru každé komponenty. Kruskalův algoritmus je příkladem kladového algoritmu.
Kružnice - neboli cyklus je takový graf, který se skládá s jediného cyklu - tedy uzavřené posloupnosti propojených vrcholů.
Minimální kostra grafu - Je dán souvislý graf G spolu s ohodnocením hran c, tj. pro každou hranu e ÎE(G) je dáno číslo c(e) (číslo c(e) nazýváme cenou hrany e). Minimální kostra grafu G = (V, E) je taková kostra grafu K = (V, L), že Equation.3 je nejmenší (mezi všemi kostrami grafu G).
Násobné hrany - více hran spojujících stejné vrcholy.
Neorientovaná hrana - neuspořádaná dvojice; bez vyznačení směru průchodu, hranou lze procházet oběma směry.
NP-úplná úloha -
Ohodnocení hrany - vyjadřuje kvalitu nebo kvantitu vztahu mezi dvěma vrcholy.
Optimalizační úloha - v optimalizačních úlohách jsou hrany grafu ohodnoceny délkami a požaduje se nalezení hemiltonovské cesty, kružnice nebo cyklu s co nejmenším součtem délek jednotlivých hran tvořících cestu, kružnici nebo cyklus.
Orientovaná hrana - uspořádaná dvojice vrcholů; má vyznačen směr průchodu, hranou lze procházet pouze ve vyznačeném směru.
Orientovaný graf - Je to takový graf, jehož hrany jsou uspořádané dvojice.
Podgr

Stáhnout celý tento materiál

Předchozí

1 2 3

Další

Vloženo: 3.01.2011, vložil: Filip Albert

Velikost: 32,50 kB

Stáhnout celý tento materiál

Komentáře

Tento materiál neobsahuje žádné komentáře.

Mohlo by tě zajímat:

Skupina předmětu A0B01LGR - Logika a grafy
Reference vyučujících předmětu A0B01LGR - Logika a grafy
Reference vyučujícího prof.RNDr. Marie Demlová CSc.

Podobné materiály