Grafikon se sastoji od vrhova i bridova. Vrhovi su povezani ivicama prema određenom svojstvu - relaciji incidencije, koja definira skup bridova. U tom slučaju mogu nastati petlje i izolirani vrhovi.
Instrukcije
Korak 1
Neka je dan skup ivica grafa i data je relacija duž koje je moguće povući ivicu iz jednog vrha u drugi. Kao primjer, skup vrhova {1, 2, 3, 4, 5, 6, 7, 8}, dva vrha x i y su u omjeru x + y <8.
Korak 2
Izgraditi matricu susjedstva temena. Da biste to učinili, izgradite kvadratnu tablicu, broj redova i stupaca u tablici podudara se s brojem vrhova. Zatim stavite 1 na presjek i-tog reda i j-tog stupca ako vrhovi i i j zadovoljavaju zadati omjer. Stavite 0 na presjek i-tog reda i j-tog stupca ako omjer za odgovarajuće elemente nije zadovoljen.
U našem primjeru prvi se red popunjava kako slijedi:
1 + 1 <8, tako da je 1 na presjeku 1. reda i 1. stupca
1 + 2 <8, opet 1
1 + 3 <8, opet 1
1 + 7 <8, netačna nejednakost, pa će ovaj element tablice biti 0
1 + 8 <8, opet 0
Korak 3
Da biste saznali broj bridova, prebrojite broj u matrici susjedstva bez dupliciranja rubova.
U primjeru je dobivena simetrična matrica, pa smo prvo prebrojali one iznad glavne dijagonale matrice (označene plavom bojom), a zatim one na glavnoj dijagonali (označene crvenom bojom). Ukupan broj rebara je 12.
Korak 4
Izgradite matricu incidenata (ivica). Da biste to učinili, nacrtajte tablicu, broj redova u njoj jednak je broju vrhova na grafikonu, a broj stupaca jednak broju rubova. Stavite jedinice na one linije koje će biti povezane ivicom. Rubovi koji vode od vrha do njega nazivaju se petlje i dodaju se na kraj matrice. U stupcima koji odgovaraju petljama postoji samo jedna jedinica, za razliku od ostalih rubova.
Korak 5
Sada nacrtajte grafikon. Postavite vrhove na papir na bilo koji način i spojite ih rubovima pomoću konstruiranih tablica. Vrhovi koji nisu povezani ivicama nazivaju se izoliranim.
