Diskrétní graf

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)

Aktuální verze z 14. 8. 2022, 14:51

Diskrétní graf s 6 uzly

Diskrétní graf je matematický pojem z oboru teorie grafů označující takový graf, v němž žádné dva vrcholy nejsou spojené hranou.

Definice

Graf \( G = (V, E) \,\! \) je diskrétní, pokud \(E = \emptyset \,\!\).
Diskrétní graf o \(n\) vrcholech je obvykle označován symbolem \( D_n \,\! \).

Význam

Diskrétní graf je sám o sobě z pohledu teorie grafů poměrně nezajímavá struktura. Jeho význam (a důvod, proč jej vůbec definovat jako samostatný pojem) se projevuje ve chvíli, kdy uvažujeme o množině všech možných grafů na určité pevně dané množině vrcholů. V takovéto množině je diskrétní graf jejím nejmenším prvkem vzhledem k uspořádání relací "být podgrafem", tj. množina hran každého grafu je nadmnožinou množiny hran diskrétního grafu.

Od diskrétního grafu začínají mnohé grafové algoritmy - například Borůvkův hladový algoritmus pro hledání minimální kostry grafu.

Doplňkem diskrétního grafu je graf, který obsahuje všechny myslitelné hrany na dané množině vrcholů, tj. úplný graf.

Související články

Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii

@@ Řádka 3: / Řádka 3: @@
 == Definice ==
-Graf <math> G = (V, E) \,\! </math> je '''diskrétní''', pokud <math>E = \emptyset \,\!</math>.<br />
+Graf <big>\( G = (V, E) \,\! \)</big> je '''diskrétní''', pokud <big>\(E = \emptyset \,\!\)</big>.<br />
-Diskrétní graf o <math>n</math> vrcholech je obvykle označován symbolem <math> D_n \,\! </math>.
+Diskrétní graf o <big>\(n\)</big> vrcholech je obvykle označován symbolem <big>\( D_n \,\! \)</big>.
 == Význam ==