Diskrétní graf
Z Wikipedie, otevřené encyklopedie
Diskrétní graf je matematický pojem z oboru teorie grafů označující takový graf, v němž žádné dva vrcholy nejsou spojené hranou.
[editovat] Definice
Graf 
je diskrétní, pokud 
.
Diskrétní graf o n vrcholech je obvykle označován symbolem 
.
[editovat] 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
[editovat] Podívejte se také na
 |
Související články obsahuje: |
