Elemente de teoria grafurilor

        Grafurile pot fi aplicate cu succes pentru a modela probleme specifice analizei circuitelor electrice, găsirea celui mai scurt drum, analiza planificării proiectelor, critica textelor literare, rețele sociale, aplicații din domeniul chimiei și economiei.

        Definiţii: Se numeşte graf neorientat o pereche ordonată de mulţimi G=(X, U), unde: X = {x1, x2, x3, …, xn}este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U o mulţime finită de perechi neordonate de forma (xi, xj), unde i≠j şi xi, xj∈X, numite muchii. O muchie uneşte două noduri. X = mulţimea nodurilor sau vârfurilor, iar U = mulţimea muchiilor grafului G. Un vecin al unui vârf este orice vârf care este adiacent lui în graf. O muchie u∈U este deci o submulţime {x, y} de vârfuri distincte din X şi se notează u = [x, y]. x şi y sunt adiacente în G, iar u şi x sunt incidente la fel ca u şi y. x şi y se numesc extremităţile muchiei u. Dacă u1 şi u2 sunt 2 muchii care au o extremitate comună, ele se numesc incidente. Mulţimea muchiilor are proprietatea de simetrie, deoarece [x, y]∈U dacă şi numai dacă [y,x]∈U.

        Un vârf care are gradul 0 (deci pentru care nu există vreo muchie incidentă cu el) se numeşte vârf izolat. Un vârf care are gradul 1 (deci care este incident cu o singură muchie) se numeşte vârf terminal.

       Exemplu: Pentru graful G definit anterior, d (11) = 0, deci vârful 11 este izolat. Fie un graf neorientat cu n noduri şi m muchii. Dacă notăm cu d1, d2, d3, …, dn gradele celor n noduri, atunci avem relaţia: d1 + d2 + d3 + … + dn = 2m 

        Definiţii: Se numeşte lanţ L = [x0, x1, …, xn]o succesiune de vârfuri cu proprietatea că oricare două vârfuri consecutive sunt adiacente. Vârfurile x0 şi xn se numesc extremităţile lanţului. Numărul n se numeşte lungimea lanţului şi este numărul de muchii din care este format. Lanţul care conţine numai vârfuri distincte, două câte două, este lanţ elementar. Lanţul care conţine numai muchii distincte este lanţ simplu. Dacă muchiile unui lanţ nu sunt distincte se numeşte lanţ compus. O matrice pătratică de ordin n se numeşte matricea lanţurilor, dacă: