grafuri

Grafuri reprezintă o disciplină matematică și o reprezentare utilă pentru relații între obiecte. Un graf se compune din vârfuri (mulțimea V) și muchii (mulțimea E). Un graf este adesea notat G=(V,E). Vârfurile pot reprezenta obiecte precum orașe sau utilizatori, iar muchiile pot conecta două vârfuri. Muchiile pot fi neorientate sau orientate, iar în multe cazuri pot avea greutăți, indicând costuri, distanțe sau capacități.

Clase fundamentale: grafuri simple, grafuri multigrafuri (cu mai multe muchii între aceleași perechi de vârfuri) sau grafuri cu bucle; grafuri neorientate sau orientate (digrafuri); grafuri ponderate sau neponderate; grafuri complete, aciclice, ciclice; grafuri conectate sau deconectate.

Reprezentări: lista de adiacență, matricea de adiacență și matricea de incidență. Lista de adiacență este eficientă pentru grafuri sparse, în timp ce matricea de adiacență permite acces rapid la vecinii unui vârf și este utilizată pentru calcule matriciale.

Proprietăți și concepte: drumul (cala) dintre vârfuri, cicluri, conectivitate și gradul unui vârf (numărul de muchii incidente). În grafuri orientate, se studiază orientarea arcelor, drumuri, cicluri orientate și posibilitatea unei ordonări topologice; arbori (arbori de acoperire, arbori minim spațiali) sunt subtipuri importante.

Algoritmi relevanți: parcurgere în lărgime (BFS) și în adânime (DFS) pentru explorare; drumuri minime cu Dijkstra și Bellman-Ford; proceduri pentru arbori minimi cu Kruskal și Prim; algoritmi pentru drumuri între toate perechile (Floyd–Warshall).

Istorie și aplicații: grafurile au fost fundamentate în dezvoltarea teoriei de către Euler în secolul al XVIII-lea, în faimoasa problemă a podurilor din Königsberg. Aplicațiile includ proiectarea rețelelor de transport și comunicații, analiza rețelelor sociale, optimizarea fluxurilor și planificarea în biologie și economie.