Un grafic este colecția a două seturi: vârfuri și muchii. între elementele a căror relație de incidență este definită - fiecare margine este întâlnită la exact două vârfuri. pe care îl conectează. În acest caz, se consideră că vârful și marginea sunt întâmpinate unul cu celălalt, și vârfuri. care sunt puncte finale pentru margine, se spune că sunt adiacente. Relația de incidență este cel mai important element al graficului, deoarece determină modul de combinare a seturilor și într-un singur obiect grafic.
O margine care unește două vârfuri poate avea o direcție de la un vârf la altul; în acest caz se numește direcție. sau orientate. sau un arc și este reprezentat de o săgeată care indică de la un vârf (început) la altul (sfârșit). Un grafic care conține arce este numit orientat, sau digraph. Un grafic care conține numai margini se numește un grafic nedirecționat sau un n-graf.
Fig. 3.1. a) este n-graful; b) - digraf.
Marginile care intră în aceeași pereche de vârfuri sunt numite multiple. Un grafic care conține mai multe margini este numit multigraf. O margine a cărei vârfuri terminale coincid se numește o buclă.
Vârful care nu intră în contact cu nici o margine se numește izolat. Un grafic poate consta numai din vârfuri izolate. În acest caz se numește un grafic nul.
Un grafic fără bucle și muchii multiple este considerat a fi complet. dacă fiecare pereche de vârfuri este conectată printr-o margine.
Fig. 3.2. a) graficul complet, b) graficul nul, c) multigraful
O adăugare a unui grafic este un grafic. având aceleași noduri ca și graficul. și care conține numai acele margini care trebuie adăugate în grafic. pentru a obține graficul complet.
Fig. 3.3. a) graficul G, b) complementul graficului G.
Fiecărui graf neorientat corespunde un grafic orientat cu același set de vârfuri în care fiecare margine este înlocuită cu două arcuri care intră în același vârfuri și care au direcții opuse.
Gradul local (sau pur și simplu gradul) unui vârf al unui n-graf este numărul de margini. incident spre vârf. În n-graf, suma gradelor tuturor vârfurilor este egală cu dublul numărului de margini ale graficului; este chiar dacă presupunem că bucla contribuie 2 la gradul de vârf:
Suma gradelor vârfurilor oricărui grafic este de două ori mai mare decât numărul muchiilor sale. Rezultă că în n-grafic numărul de vârfuri de grad ciudat este egal.
Un exemplu. Graficul H din Fig. 3.1a are două noduri de grad ciudat (vertex u). Gradele vârfurilor rămase sunt egale.
Pentru vârfurile unui digar sunt definite două grade locale:
- numărul de arce provenind din partea de sus;
- numărul de arce care intră în vertex.
Buclele contribuie la 1 aceste două puteri.
În digraph, sumele gradelor tuturor vârfurilor sunt egale cu numărul de arce ale acestui grafic și sunt egale una cu cealaltă:
Un exemplu. Pentru diagrama din Fig. 3.1b gradele locale ale vârfurilor sunt egale:
Articole similare
Trimiteți-le prietenilor: