Graf sa skladá z vrcholov a hrán. Vrcholy sú spojené hranami podľa určitej vlastnosti - incidenčný vzťah, ktorý definuje množinu hrán. V tomto prípade sa môžu tvoriť slučky a izolované vrcholy.
Návod na použitie
1
Nech je daná množina hrán grafu a vzťah, pomocou ktorého je možné nakresliť hranu z jedného vrcholu na druhý. Ako príklad možno uviesť, že sada vrcholov {1, 2, 3, 4, 5, 6, 7, 8}, obidva vrcholy xay sú v pomere x + y <8.
2
Zostavte maticu blízkosti vrcholu. Za týmto účelom vytvorte š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-teho riadku a j-teho stĺpca, ak vrcholy i a j spĺňajú daný pomer. Ak nie je pomer zodpovedajúcich prvkov splnený, umiestnite 0 na priesečník i-teho riadku a j-teho stĺpca.
V našom príklade je prvý riadok vyplnený nasledovne:
1 + 1 <8, takže v priesečníku 1. riadku a 1. stĺpca je 1
1 + 2 <8, opäť 1
1 + 3 <8, opäť 1
…
1 + 7 <8, nesprávna nerovnosť, potom bude tento element tabuľky 0
1 + 8 <8, opäť 0
3
Ak chcete zistiť počet hrán, spočítajte počet jednotiek v susednej matici bez toho, aby ste okraje ripovali.
V príklade bola získaná symetrická matica, preto boli najprv jednotky vypočítané nad hlavnou uhlopriečkou matrice (označené modrou farbou) a potom jednotky na hlavnej diagonále (označené červenou farbou). Celkový počet rebier je 12.
4
Zostavte maticu incidentov (hrany). Na tento účel nakreslite tabuľku, počet riadkov v nej sa rovná počtu vrcholov grafu a počet stĺpcov sa rovná počtu hrán. Vložte jednotky do čiar, ktoré budú spojené okrajom. Hrany vedúce zhora nadol sa nazývajú slučky a pripočítajú sa na koniec matrice. V stĺpcoch zodpovedajúcich slučkám je na rozdiel od ostatných hrán iba jedna jednotka.
5
Teraz nakreslite graf. Usporiadajte vrcholy na papieri ľubovoľne a pomocou vytvorených tabuliek ich spojte s okrajmi. Vrcholy, ktoré nie sú spojené hranami, sa nazývajú izolované.
Venujte pozornosť
Obrázok ukazuje rebrá kvôli prehľadnosti. Zvyčajne sa hmotnosť rebra zapisuje cez rebro.
