Graf je sestavljen iz tock in robov. Vrhovi so povezani z robovi glede na določeno lastnost - vpadno razmerje, ki določa nabor robov. V tem primeru se lahko oblikujejo zanke in izolirane tocke.
Navodila za uporabo
1
Naj bo določen niz robov grafa in razmerje, s katerim lahko narišemo rob iz ene točke v drugo. Primer je nabor tock {1, 2, 3, 4, 5, 6, 7, 8}, obe točki x in y sta v razmerju x + y <8.
2
Sestavite matriko sosednjega toka. Če želite to narediti, sestavite kvadratno tabelo, število vrstic in stolpcev v tabeli se ujema s številom opornic. Nato na presečišče i-te vrstice in j-tega stolpca postavite 1, če točki i in j izpolnjujeta dano razmerje. Na presečišču i-te vrstice in j-tega stolpca postavite 0, če razmerje za ustrezne elemente ni izpolnjeno.
V našem primeru je prva vrstica napolnjena na naslednji način:
1 + 1 <8, torej na presečišču 1. vrstice in 1. stolpca je 1
1 + 2 <8, spet 1
1 + 3 <8, spet 1
…
1 + 7 <8, napačna neenakost, potem bo ta element tabele 0
1 + 8 <8, spet 0
3
Če želite izvedeti število robov, preštejte število enot v sosednji matriki, pri čemer ne ropate robov.
V primeru smo dobili simetrično matrico, zato smo najprej izračunali enote nad glavno diagonalo matrice (označene z modro barvo), nato pa enote na glavni diagonali (označene z rdečo). Skupno število reber je 12.
4
Sestavite matrico incidentov (robov). Če želite to narediti, narišite tabelo, število vrstic v njej je enako številu vrstic grafikona, število stolpcev pa je enako številu robov. Enote postavite v črte, ki bodo povezane z robom. Robovi, ki vodijo od vrha do njega, se imenujejo zanke in dodajo na konec matrice. V stolpcih, ki ustrezajo zankam, je samo ena enota, za razliko od drugih robov.
5
Zdaj narišite graf. Točke na papirju poljubno razporedite in povežite z robovi s pomočjo izdelanih tabel. Vrhovi, ki niso povezani z robovi, se imenujejo izolirani.
Bodite pozorni
Slika prikazuje rebra zaradi jasnosti. Običajno se teža rebra zapiše čez rebro.
