Diskrétní graf

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

Externí odkazy

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