Concepte de bază ale teoriei graficului
Formal, graficul este o pereche ordonată G = (V, E) din seturi dintre care primul este format din vârfuri sau noduri ale grafului, iar celălalt - din marginile sale. O margine se conectează două noduri. Atunci când se lucrează cu grafice suntem adesea interesați de modul de a deschide calea marginilor de la un nod la altul. Prin urmare, vom vorbi despre mișcarea marginii; acest lucru înseamnă că ne îndreptăm din vârful A al graficului la un alt nod B asociat cu ea o margine AB (graficul margine care leagă două vârfuri, pentru concizie notat cu această pereche de vârfuri). În acest caz, se spune că A este adiacent la B, sau că cele două vârfuri adiacente.
Un grafic poate fi orientat sau nu. Coaste graf neorientat, de multe ori se face referire la conta pur și simplu, puteți merge în ambele direcții. În acest caz, o margine - o pereche neordonată de vârfuri, capete. Într-un grafic sau digraph direcționat, marginile sunt perechile de noduri ordonate: primul vârf - este marginea de sus, iar al doilea - la sfârșitul anului. Mai mult, pentru concizie vom vorbi pur și simplu despre margini, iar acestea sunt concentrate sau nu va fi clar din context.
Mai târziu, vom trage pur și simplu, grafice și nu pune o mulțime de ei. Vârfurile vor fi reprezentate prin cercuri, iar marginile - segmente. În interiorul cercurilor vor fi scrise vertex etichete. Nervurile graf direct vor fi prevăzute cu săgeți care indică direcția de deplasare admisă de-a lungul marginii.
Figura 1 este o reprezentare grafică a unui nedirijat (a) și orientate (b) graficele împreună cu descrierea lor formală.
terminologie
Analiza completă - un grafic în care fiecare nod este conectat cu oricine altcineva. Numărul muchiilor dintr-un grafic complet fără bucle cu N noduri este egal cu (N2 - N) / 2. În caseta orientirvoannom completă a permis trecerea de la orice nod la orice alt. Deoarece graficul de tranziție de margine este permisă în ambele direcții, și trecerea unei muchii în digraph - numai într-o singură, în digraph coaste de două ori pline, adică, numărul lor este egal cu N2 - N.
Subgrafic (VS. ES) grafic sau digraph (V, E) este format dintr-un subset de noduri și un subset de muchii conectându-le.
Cale în grafic sau grafic regia - este o secvență de muchii, care pot avea loc, la rândul său. Cu alte cuvinte, calea de la vertex trece prin punctul A B incepe de la A și trece prin setul de nervuri, atâta timp cât vertexul este atins B. În termeni formali, calea de sus vi vertex vj într-o secvență de margini vi vi + 1. vi + 1, vi + 2. vj-1, vj. Cerem ca orice nod întâlnit în acest fel nu mai mult de o dată. În orice fel este lungimea - numărul de muchii din ea. Lungimea AB, BC, CD, DE este egal cu 4.
Într-un grafic ponderat sau digraph fiecare margine atribuit un număr numit greutatea marginii. Când imaginea este înregistrată de obicei grafic margini in apropiere de greutatea de margine. În descrierea formală a greutății va constitui un element suplimentar dezordonat sau ordonat pereche de vârfuri (care formează împreună cu această pereche, „t“). Când lucrați cu grafice îndreptate considerăm greutatea înotătoarelor trece prețul pe ea. Costul calea pe un grafic ponderat este suma greutăților de margini ale căii. Calea cea mai scurtă într-un grafic ponderat - aceasta este calea cu greutate minimă, chiar dacă numărul de muchii din calea și poate fi redusă. Dacă, de exemplu, calea P1 cuprinde cinci coaste, cu o greutate totală de 24, iar P2 cale - a trei muchii cu o greutate totală de 36, atunci calea P1 este considerată a fi mai scurt.
Un grafic sau digraph este conectat în cazul în care fiecare pereche de noduri pot fi conectate la cel puțin un fel. Ciclul - o cale care începe și se termină în același Vertex. In graficul sau digraph cicluri aciclici disponibile. Un grafic conectat se numește aciclic (dezrădăcinarea) copac. Structura de copac nerădăcinoși este aceeași ca și cea a lemnului, numai că nu este selectată rădăcină. Cu toate acestea, fiecare nod copac nerădăcinoși poate servi ca rădăcină.