Graficul este format din vârfuri și margini. Vârfurile sunt conectate prin margini conform unei anumite proprietăți - relația de incidență, care definește setul de muchii. În acest caz, se pot forma bucle și vârfuri izolate.
Manual de instrucțiuni
1
Să fie dat un set de muchii ale unui grafic și o relație dată prin care se poate desena o margine de la un vertex la altul. Ca exemplu, setul de vertexi {1, 2, 3, 4, 5, 6, 7, 8}, cele două vârfuri x și y sunt în raportul x + y <8.
2
Construiți o matrice de adjacență a vertexului. Pentru a face acest lucru, construiți un tabel pătrat, numărul de rânduri și coloane din tabel se potrivește cu numărul de vârfuri. Apoi puneți 1 la intersecția rândului i și coloanei j, dacă vertexurile i și j satisfac raportul dat. Puneți 0 la intersecția rândului i și a coloanei j, dacă raportul pentru elementele corespunzătoare nu este satisfăcut.
În exemplul nostru, prima linie este completată după cum urmează:
1 + 1 <8, deci la intersecția din primul rând și prima coloană este 1
1 + 2 <8, din nou 1
1 + 3 <8, din nou 1
…
1 + 7 <8, inegalitate incorectă, atunci acest element de tabel va fi 0
1 + 8 <8, din nou 0
3
Pentru a afla numărul de muchii, numărați numărul de unități din matricea de adiacență, în timp ce nu tăiați marginile.
În exemplu, s-a obținut o matrice simetrică, prin urmare, mai întâi unitățile au fost calculate deasupra diagonalei principale a matricei (marcată cu albastru), iar apoi unitățile de pe diagonala principală (marcată cu roșu). Numărul total de coaste este de 12.
4
Construiți o matrice de incidente (margini). Pentru a face acest lucru, desenați un tabel, numărul de rânduri din el este egal cu numărul de vârfuri ale graficului, iar numărul de coloane este egal cu numărul de muchii. Puneți unitățile în liniile care vor fi conectate printr-o margine. Marginile care duc de sus la ea se numesc bucle și se adaugă la capătul matricei. În coloanele corespunzătoare buclelor, există o singură unitate, spre deosebire de celelalte muchii.
5
Acum desenați un grafic. Aranjați vertexurile pe hârtie în mod arbitrar și conectați-le cu margini folosind tabelele construite. Vertexurile care nu sunt conectate prin margini se numesc izolate.
Fii atent
Figura arată coaste pentru claritate. De obicei, greutatea coastei este scrisă peste coaste.
