Grafikon se sastoji od vrhova i bridova. Vrhovi su povezani rubovima prema određenom svojstvu - relaciji incidencije koja definira skup bridova. U tom slučaju mogu nastati petlje i izolirani vrhovi.
Upute
Korak 1
Neka je zadan skup bridova grafa i data je relacija duž koje je moguće povući rub 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 vrhova. Da biste to učinili, izgradite kvadratnu tablicu, broj redaka i stupaca u tablici podudara se s brojem vrhova. Zatim stavite 1 na sjecište i-tog reda i j-tog stupca ako vrhovi i i j zadovoljavaju zadani omjer. Stavite 0 na presjek i-tog retka i j-tog stupca ako omjer za odgovarajuće elemente nije zadovoljen.
U našem se primjeru prvi redak 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, netočna nejednakost, pa će ovaj element tablice biti 0
1 + 8 <8, opet 0
3. korak
Da biste saznali broj bridova, prebrojite ih 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.
4. korak
Izgradite matricu incidenata (rubova). Da biste to učinili, nacrtajte tablicu, broj redaka u njoj jednak je broju vrhova na grafikonu, a broj stupaca jednak broju rubova. Stavite jedinice na one crte koje će biti povezane rubom. 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 graf. Postavite vrhove na papir na bilo koji način i spojite ih rubovima pomoću konstruiranih tablica. Vrhovi koji nisu povezani rubovima nazivaju se izoliranim.
