| Abstrakt: | Mladá, ale dnes už doširoka bohatá teória grafov, vzniká koncom 19. a ďalej sa rozvíja začiatkom 20. storočia. Počiatky tejto teórie formovali matematici, ktorý riešili rôzne problémy, pri ktorých sa dalo abstrahovať od povahy zadania. Algoritmy a dokázané vlastnosti niektorých grafov majú široké uplatnenie v informatike.
Overiť vlastnosť na grafe, znamená dokázať, či graf má danú vlastnosť, alebo nemá. Každý graf má napríklad každý svoj vrchol spojený s každým druhým vrcholom hranou, alebo má spojené iba niektoré dvojice vrcholov. V tomto prípade hovoríme, že daný graf je kompletný, alebo nie je. Budeme uvažovať iba grafy z jednoduchými hranami. Vylučujeme multihrany a slučky. Graf s jedným vrcholom je graf. Takýto graf nemôže mať ani jednu hranu. Graf s dvoma vrcholmi má dve konfigurácie: s hranou alebo bez hrany. Práve sme opísali prvé tri grafy z lexikografického usporiadania grafov. Takýmto postupom môžeme generovať grafy. Chceme ukazovať vlastnosti grafov. Grafy reprezentujeme ako body na ploche, alebo v priestore. Ofarbujeme ich podľa toho či overená vlastnosť je na preverovanom grafe splnená, alebo nie je. Máme možnosť nahliadnuť na grafickú reprezentáciu vybraného, overeného grafu. Grafy môžme generovať od nami zvolenej konfigurácie a počtu vrcholov. Graf ktorý sa vygeneruje, overí sa na ňom vlastnosť a potom sa zobrazí na plochu, alebo do priestoru ako farebný bod. Výsledný obrázok odhaľuje skupiny grafov, alebo naopak výnimky, ktoré danú vlastnosť nemajú.
|
|---|