Teoria grafurilor a fost recent utilizat pe scară largă în diverse domenii ale științei și tehnologiei. Dezvoltarea rapidă a acestei teorii a fost dat la crearea tehnologiei de calculator, care permite să rezolve multe dintre sarcini algoritmice.
Count - o combinație a celor două seturi finite: un set de puncte și un set de linii de legătură unele perechi de aceste puncte. Setul de puncte numite noduri (noduri) a graficului. O pluralitate de linii care leagă nodurile grafului, numite muchii (arce) ale graficului.
Grafic regia (digraph) - un grafic în care sunt orientate toate marginile, de exemplu, marginile care sunt atribuite direcția.
graf neorientat (neorgraf) - grafic cu toate muchiile unui nedirijat, adică ale căror margini nu sunt definite direcție.
Count Mixed - Count conținând ambele margini dirijate și nedirijate.
O buclă este o margine. conectarea Vertex cu el însuși. Două noduri se numesc adiacente dacă există o muchie de legătură acestora. Coastele. care leagă aceeași pereche de noduri se numesc multipli.
grafic simplu - un grafic în care nu se bucle sau mai multe margini.
Multigraf - un grafic în care oricare două vârfuri sunt conectate prin mai mult de o muchie.
Route în grafic este o secvență alternantă finită de noduri adiacente și muchii care leagă nodurile.
Traseul este deschis, dacă început și de sfârșit nodurile sale sunt diferite, în caz contrar se spune să fie închis.
Traseul se numește lanț. în cazul în care toate marginile sale sunt diferite. Un circuit deschis se numește o cale. dacă toate nodurile sale sunt diferite.
Un circuit închis se numește ciclu. în cazul în care toate nodurile sale sunt diferite, cu excepția cele din urmă.
Un grafic este conectat în cazul în care există o modalitate de a le conecta la orice pereche de noduri.
greutate vertex - număr (real, întreg sau rațional) furnizat în corespondență cu partea superioară (interpretat ca un cost, productivitate, etc ...). Greutate (lungime) a nervurii - un număr sau câteva numere care sunt interpretate în raport cu lungimea marginii, lățime de bandă, etc ...
Grafic Weighted - grafic, fiecare muchie se atribuie o anumită valoare (greutatea marginii).
Selectarea structurii de date pentru stocarea în memoria calculatorului a graficului este de o importanță fundamentală în dezvoltarea unor algoritmi eficienți. Luați în considerare câteva moduri de a reprezenta un grafic.
Având în vedere un grafic cu numărul de noduri este n, iar numărul de muchii - m. Fiecare apex nervură și fiecare au o greutate - un număr întreg pozitiv. Dacă graficul nu este etichetat, se consideră că greutatea este egală cu unu.
Listă de coaste - acest set este format din perechi de noduri adiacente. Pentru stocare folosesc de obicei o matrice unidimensională de lungime m, conține o listă de perechi de noduri adiacente o margine a graficului. Listă de coaste este mai convenabil să pună în aplicare diferite algoritmi pe grafice, în comparație cu alte metode.
Matricea de adiacență - un tablou bidimensional de dimensiune n x n, elemente ale căror valori sunt caracterizate smezhnostyuvershin grafic. În acest caz, valoarea elementului de matrice este atribuit numărul de muchii care se conectează nodurile corespunzătoare. Această metodă este eficientă atunci când este necesar să se verifice adiacența sau găsi greutatea marginii pe cele două vârfuri date.
Incidență Matrix - o matrice bidimensională de dimensiune n x m, care specifică relația dintre elementele (graficul incident de margine și vertex). Coloanele corespund marginilor. line - înălțimi. O valoare nenulă în celula matricei indică legătura dintre partea superioară și margine. Această metodă este de stocare cea mai încăpătoare, dar este mai ușor să găsească cicluri în grafic.
Există mai mulți algoritmi de grafice, care se bazează pe o enumerare sistematică a nodurilor. astfel încât fiecare nod este vizualizat (vizitat) exact o dată. Prin urmare, o sarcină importantă este de a găsi metode bune pentru a căuta în cutie.
În rezolvarea multor probleme, folosind grafice, avem nevoie de metode eficiente de runde regulate de noduri și muchii. Metodele standard și cele mai comune includ:
Aceste metode sunt cel mai adesea considerate a graficelor îndreptate. dar ele sunt, de asemenea, aplicabile neorientat, marginile sunt considerate a fi bidirecțională. algoritmi traversal în profunzime și lățimea sunt baza deciziei de diferite sarcini de procesare grafice, cum ar fi construirea unei păduri se întinde. proverkisvyaznosti. aciclicitate, calcularea distanțelor între noduri și altele.