Diskrétní graf

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 ${\displaystyle G=(V,E)\,\!}$ je diskrétní, pokud ${\displaystyle E=\emptyset \,\!}$.
Diskrétní graf o ${\displaystyle n}$ vrcholech je obvykle označován symbolem ${\displaystyle 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

• Souvislý graf
• Úplný graf
• Kostra grafu

Externí odkazy

• Obrázky, zvuky či videa k tématu Diskrétní graf na Wikimedia Commons