Graficul este format din vârfuri și muchii. Vârfurile sunt conectate prin margini conform unei anumite proprietăți - relația de incidență, care definește setul de margini. În acest caz, se pot forma bucle și vârfuri izolate.
Instrucțiuni
Pasul 1
Să se dea mulțimea muchiilor grafului și să se dea relația de-a lungul căreia este posibil să se traseze o margine de la un vârf la altul. De exemplu, setul de vârfuri {1, 2, 3, 4, 5, 6, 7, 8}, două vârfuri x și y sunt în raportul x + y <8.
Pasul 2
Construiți o matrice de adiacență la vârf. Pentru a face acest lucru, construiți un tabel pătrat, numărul de rânduri și coloane din tabel coincide cu numărul de vârfuri. Apoi puneți 1 la intersecția rândului I și a J coloană dacă vârfurile i și j satisfac raportul dat. Puneți 0 la intersecția rândului I și a J-a coloană dacă raportul pentru elementele corespunzătoare nu este îndeplinit.
În exemplul nostru, prima linie este completată după cum urmează:
1 + 1 <8, deci este 1 la intersecția primului rând și a primei coloane
1 + 2 <8, din nou 1
1 + 3 <8, din nou 1
1 + 7 <8, inegalitate incorectă, deci acest element al tabelului va fi 0
1 + 8 <8, din nou 0
Pasul 3
Pentru a afla numărul de muchii, numărați numărul celor din matricea de adiacență fără a dubla marginile.
În exemplu, s-a obținut o matrice simetrică, așa că am numărat mai întâi cele de deasupra diagonalei principale a matricei (marcate cu albastru), apoi cele de pe diagonala principală (marcate cu roșu). Numărul total de coaste este de 12.
Pasul 4
Construiți o matrice de incidente (margini). Pentru a face acest lucru, desenați un tabel, numărul de rânduri din acesta este egal cu numărul de vârfuri din grafic, iar numărul de coloane este egal cu numărul de muchii. Puneți unități pe acele linii care vor fi conectate printr-o margine. Marginile care duc de la vârf la acesta se numesc bucle și sunt adăugate la capătul matricei. În coloanele corespunzătoare buclelor, există o singură unitate, spre deosebire de restul marginilor.
Pasul 5
Acum desenează un grafic. Așezați vârfurile pe hârtie în orice mod și conectați-le cu margini folosind mesele construite. Vârfurile care nu sunt conectate prin margini se numesc izolate.
