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 editovat
Graf je diskrétní, pokud .
Diskrétní graf o vrcholech je obvykle označován symbolem .
Význam editovat
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 editovat
Externí odkazy editovat
Obrázky, zvuky či videa k tématu diskrétní graf na Wikimedia Commons
