Graf se sastoji od vrhova i rubova. Vrhovi su povezani rubovima prema određenom svojstvu - incidencijalnom odnosu, koji definira skup rubova. U tom slučaju mogu se oblikovati petlje i izolirani vrhovi.
Priručnik s uputama
1
Neka je postavljen skup rubova grafikona i odnos dat pomoću kojeg se može izvući rub iz jedne verzije u drugu. Kao primjer, skup vrhova {1, 2, 3, 4, 5, 6, 7, 8}, dvije vrhove x i y nalaze se u omjeru x + y <8.
2
Izgradite matricu susjedne kralježnice. Da biste to učinili, napravite kvadratnu tablicu, broj redaka i stupaca u tablici odgovara broju vrhova. Zatim stavite 1 na sjecište i-tog reda i j-og stupca, ako vrhovi i i j zadovoljavaju zadani omjer. Stavite 0 na sjecište i-tog reda i j-og stupca ako omjer odgovarajućih elemenata nije zadovoljen.
U našem primjeru prvi se red ispunjava kako slijedi:
1 + 1 <8, dakle na raskrižju 1. reda i 1. stupca je 1
1 + 2 <8, opet 1
1 + 3 <8, opet 1
…
1 + 7 <8, netočna nejednakost, tada će ovaj element tablice biti 0
1 + 8 <8, opet 0
3
Da biste saznali broj rubova, računajte broj jedinica u matrici susjednosti, a da ne rupate rubove.
U primjeru je dobivena simetrična matrica, stoga su jedinice najprije izračunate iznad glavne dijagonale matrice (označene plavom bojom), a zatim jedinice na glavnoj dijagonali (označene crvenom bojom). Ukupni broj rebara je 12.
4
Izgradite matricu incidenata (rubova). Da biste to učinili, nacrtajte tablicu, broj redaka u njoj jednak je broju vrhova grafikona, a broj stupaca jednak je broju rubova. Stavite jedinice u linije koje će biti povezane rubom. Rubovi koji vode od vrha do njega nazivaju se petlje i dodaju na kraj matrice. U stupcima koji odgovaraju petlji nalazi se samo jedna jedinica, za razliku od ostalih rubova.
5
Sada nacrtajte graf. Rasporedite vrhove na papiru proizvoljno i povežite ih s rubovima pomoću konstruiranih tablica. Vrhovi koji nisu povezani rubovima nazivaju se izoliranim.
Obratite pažnju
Na slici su prikazana rebra radi jasnoće. Obično se težina rebra piše preko rebra.
