Graf je sestavljen iz oglišč in robov. Oglišča so povezana z robovi glede na določeno lastnost - vpadno razmerje, ki definira množico robov. V tem primeru lahko nastanejo zanke in izolirane točke.
Navodila
Korak 1
Naj bo podan niz robov grafa in podana je relacija, po kateri je mogoče narisati rob iz ene točke v drugo. Kot primer je nabor točk {1, 2, 3, 4, 5, 6, 7, 8}, dve točki x in y v razmerju x + y <8.
2. korak
Zgradite matriko sosednosti oglišča. Če želite to narediti, zgradite kvadratno tabelo, število vrstic in stolpcev v tabeli sovpada s številom točk. Nato postavite 1 na presečišče i-te vrstice in j-tega stolpca, če točki i in j izpolnjujeta dano razmerje. Na presečišče i-te vrstice in j-tega stolpca postavite 0, če razmerje za ustrezne elemente ni izpolnjeno.
V našem primeru se prva vrstica izpolni na naslednji način:
1 + 1 <8, torej je na presečišču 1. vrstice in 1. stolpca 1
1 + 2 <8, spet 1
1 + 3 <8, spet 1
1 + 7 <8, napačna neenakost, zato bo ta element tabele 0
1 + 8 <8, spet 0
3. korak
Če želite izvedeti število robov, preštejte število tistih v matriki sosednosti, ne da bi podvojili robove.
V primeru smo dobili simetrično matrico, zato smo najprej prešteli tiste nad glavno diagonalo matrike (označene z modro), nato pa še tiste na glavni diagonali (označene z rdečo). Skupno število reber je 12.
4. korak
Zgradite matriko incidentov (robov). Če želite to narediti, narišite tabelo, število vrstic v njej je enako številu točk na grafu, število stolpcev pa je enako številu robov. Postavite enote na tiste črte, ki bodo povezane z robom. Robovi, ki vodijo od oglišča do njega, se imenujejo zanke in se dodajo na konec matrike. V stolpcih, ki ustrezajo zankam, je v nasprotju z ostalimi robovi samo ena enota.
5. korak
Zdaj nariši graf. Točke na papir postavite na kakršen koli način in jih z izdelanimi tabelami povežite z robovi. Točke, ki niso povezane z robovi, se imenujejo izolirane.
