Teorie grafů: vlastnosti a části grafů

MZJ
Zkopírovat krátkou adresu (umime.to/MZJ)
Ukázat QR kód

umime.to/MZJ


Stáhnout QR kód
Ukázat/skrýt shrnutí

Graf je souvislý, pokud mezi každými dvěma z jeho vrcholů vede cesta. To znamená, že všechny vrcholy jsou spolu nějak propojené –⁠ dokážeme v grafu přejít po hranách z každého vrcholu do všech ostatních.

Komponenta souvislosti je část grafu, která je souvislá, ale pokud bychom do ní chtěli zahrnout nějaké další hrany nebo vrcholy, souvislá by být přestala. Každý graf je rozdělený na několik komponent souvislosti. Pokud je graf souvislý, tvoří sám o sobě jednu komponentu souvislosti. Graf na obrázku není souvislý a skládá se ze 4 komponent souvislosti, jedna z nich je vyznačená žlutě.

Podgraf je část (tedy některé vybrané vrcholy a hrany) grafu, která sama o sobě také tvoří graf. Každá hrana v podgrafu tedy musí mít na obou svých koncích vrchol, který také patří do podgrafu. Žluté vrcholy a hrany na obrázku tvoří podgraf.

V úplném grafu je každý vrchol je spojený s každým. Tento graf má tedy maximální počet hran, který může mít.

Strom je souvislý graf, který neobsahuje žádnou kružnici (cyklus) jako podgraf. Stromy mají mnoho zajímavých vlastností (např. mezi každými dvěma vrcholy vede právě jedna cesta) a často se v informatice používají (např. pro přehledné a efektivní uložení dat).

Souhrn mi pomohl
Souhrn mi nepomohl
Souhrn je skryt.

Rozhodovačka

Rychlé procvičování výběrem ze dvou možností.


Teorie grafů: vlastnosti a části grafů  
Zobrazit souhrn tématu


NAPIŠTE NÁM

Děkujeme za vaši zprávu, byla úspěšně odeslána.

Napište nám

Nevíte si rady?

Nejprve se prosím podívejte na časté dotazy:

Čeho se zpráva týká?

Vzkaz Obsah Ovládání Přihlášení Licence