Diskrétní graf

graf, v němž žádné dva vrcholy nejsou spojené hranou (teorie 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.

Diskrétní graf s 6 uzly

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