Graf sa skladá z vrcholov a hrán. Vrcholy sú spojené hranami podľa určitej vlastnosti - vzťahu incidencie, ktorá definuje množinu hrán. V takom prípade môžu vzniknúť slučky a izolované vrcholy.
Inštrukcie
Krok 1
Nech je daná množina hrán grafu a je uvedený vzťah, pozdĺž ktorého je možné nakresliť hranu z jedného vrcholu do druhého. Napríklad množina vrcholov {1, 2, 3, 4, 5, 6, 7, 8}, dva vrcholy xay sú v pomere x + y <8.
Krok 2
Vytvorte vrcholovú maticu susednosti. Ak to chcete urobiť, zostavte štvorcovú tabuľku, počet riadkov a stĺpcov v tabuľke sa zhoduje s počtom vrcholov. Potom dajte 1 na priesečník i-tého riadku a j-tého stĺpca, ak vrcholy i a j vyhovujú danému pomeru. Ak nie je splnený pomer pre príslušné prvky, dajte 0 na priesečník i-tého riadku a j-tého stĺpca.
V našom príklade je prvý riadok vyplnený takto:
1 + 1 <8, takže na križovatke 1. riadku a 1. stĺpca je 1
1 + 2 <8, opäť 1
1 + 3 <8, opäť 1
1 + 7 <8, nesprávna nerovnosť, takže tento prvok tabuľky bude 0
1 + 8 <8, opäť 0
Krok 3
Ak chcete zistiť počet hrán, spočítajte počet tých v matici susedstva bez toho, aby ste hrany duplikovali.
V príklade sa získala symetrická matica, takže sme spočítali najskôr tie nad hlavnou uhlopriečkou matice (označené modrou farbou), a potom tie, ktoré sú na hlavnej uhlopriečke (označené červenou farbou). Celkový počet rebier je 12.
Krok 4
Vytvorte maticu incidentov (hrán). Za týmto účelom nakreslite tabuľku, počet riadkov v nej sa rovná počtu vrcholov v grafe a počet stĺpcov sa rovná počtu hrán. Vložte jednotky na tie čiary, ktoré budú spojené okrajom. Hrany vedúce z vrcholu k nemu sa nazývajú slučky a pridávajú sa na koniec matice. V stĺpcoch zodpovedajúcich slučkám je na rozdiel od ostatných okrajov iba jedna jednotka.
Krok 5
Teraz nakreslite graf. Vrcholy ľubovoľne položte na papier a pomocou skonštruovaných tabuliek spojte s okrajmi. Vrcholy, ktoré nie sú spojené hranami, sa nazývajú izolované.
