Graficul (din greaca "scriu") este setul de noduri V și setul E de perechi de noduri neordonate și ordonate; Graficul este de obicei marcat cu G (V, E).
O margine este o pereche de noduri neordonate.
Arcul este o pereche ordonată de vârfuri.
Adică, arcul are o anumită direcție, dar marginea nu este.
Un grafic care conține doar margini este numit ne-orientat (sau non-graf);
Un grafic care conține numai arce este orientat (sau digraph).
Arcuri multiple și muchii - când două vârfuri sunt conectate prin mai multe muchii. sau prin mai multe arce unidirecționale.
Un multigraf este un grafic cu mai multe arce sau muchii.
Arcul (sau marginea) poate începe și se termină la același vârf, caz în care arcul (sau marginea) corespunzătoare se numește buclă.
Un pseudograf este un grafic care conține bucle.
Vârfurile conectate printr-o margine sau un arc sunt numite adiacente.
Marginile care au un vârf comun sunt, de asemenea, numite adiacente.
Incidența - un termen utilizat numai în legătură cu marginile și nodurile: dacă v1, v2 - partea de sus, și e = (v1, v2) - conectarea acestora la margine, atunci incidentul vârf v1 și marginea e, v2 și incidentul e margine sfat, de asemenea. Două vârfuri (sau două margini) nu pot fi incidente.
Este dovedit faptul că un spațiu tridimensional al oricărui grafic poate fi reprezentat sub forma de stivuire (top când este reprezentat de puncte și margini și arce - linii și săgeți, respectiv), astfel încât liniile care corespund marginilor (arce) nu se intersectează în punctele interioare. Pentru spațiu 2-dimensional, care nu este adevărat.
Un grafic plan este un grafic care poate fi reprezentat pe un plan fără margini de trecere (arce).
Graficul complet este un grafic. în care fiecare vertex este conectat la fiecare.
Un grafic complet este un grafic simplu în care fiecare pereche de vârfuri diferite este adiacentă.
Semi-gradul de apropiere (ieșire) a vârfului este numărul de arce care intră (ieșind) la (de) vârful (ele).
Gradul (valența) unui vârf este numărul de vârfuri conectate la un anumit vârf sau - numărul de margini ale unui grafic care intră într-un vertex dat.
Topul gol al graficului este un vârf izolat fără bucle.
Un vertex izolat este un vârf care nu este conectat la alte noduri prin arce sau muchii. Cu toate acestea, un astfel de vârf poate avea bucle. Se poate spune, de asemenea, că acesta este vârful fără arce sau margini care se încadrează în el. Și în cazul unui grafic fără bucle, acesta este un vârf al gradului 0 (apropo, un astfel de vârf poate fi deja numit gol).
Intrarea și ieșirea graficului sunt noduri care au o semnificație semantică corespunzătoare într-o anumită sarcină.
Path (cale) - o secvență de muchii (într-un grafic neorientat) și / sau arce (într-un grafic direcționat), astfel încât capătul unui arc (marginea) este începutul unui alt arc (margine). Sau o secvență de vârfuri și arce (marginile) în care fiecare element este incidental față de precedentul și ulterior.
Un lanț dintr-un grafic este o rută, toate marginile cărora sunt diferite.
Un grafic simplu este un grafic în care nu există muchii multiple și bucle.
Modul simplu este calea, ale cărei muchii sunt perechi diferite. Cu alte cuvinte, o cale simplă nu trece de două ori printr-o margine.
Un grafic orientat G (V, X) este considerat a fi unilateral. dacă pentru orice pereche de vârfuri vi. vj, există o cale fie de la vi la vj, fie de la vj la vi.
Se spune că un grafic orientat G (V, X) este puternic conectat. dacă pentru orice pereche de vârfuri vi. vj există o cale de la vi la vj, și de la vj la vi.
Calea Euler (lanț) într-un grafic este o cale arbitrară care trece prin fiecare margine a graficului o singură dată.
Ciclul Euler este calea euleriană, care este un ciclu.
Graficul Euler este un grafic care conține ciclul Euler.
Jumătate grafice - un grafic care conține calea Euleriană (lanț).
Calea Hamiltoniană (sau lanțul Hamiltonian) este o cale care conține fiecare vârf al graficului exact o dată. Calea Hamiltoniană, ale cărei noduri inițiale și finale coincid, se numește ciclul Hamiltonian.
Un grafic este Hamiltonian dacă și numai dacă închiderea lui este Hamiltonian.
Schița este o cale închisă în digraf.
Calea critică a unui grafic este calea lungimii maxime într-un grafic aciclic orientat.
Trimiteți-le prietenilor: