grafiteoria

Grafiteoria, or graph theory, is a branch of mathematics that studies graphs as representations of relations among objects. A graph G consists of a set of vertices V and a set of edges E connecting pairs of vertices. Edges may be undirected or directed, giving undirected graphs, directed graphs (digraphs), or mixed forms. Graphs can be simple, with no loops or multiple edges, or more generally include parallel edges and loops, forming multigraphs and pseudographs.

Key concepts include degree (the number of incident edges), adjacency, paths, cycles, connectivity, and subgraphs. Special types of graphs include trees (connected acyclic graphs), planar graphs (graphs drawable without crossing edges), weighted graphs (edges carry weights), and bipartite graphs (vertices partitioned into two sets with edges only between sets).

Important problems and results in grafiteoria encompass finding paths and circuits (such as shortest paths, Eulerian paths, and Hamiltonian cycles), coloring problems (the chromatic number), and network flows. Foundational milestones include Euler’s solution to the Königsberg bridges problem and numerous theorems related to planarity, tree characterizations, and graph decompositions. Algorithmic aspects study procedures to solve these problems efficiently, with notable algorithms such as Dijkstra’s for shortest paths, Bellman-Ford, Kruskal’s and Prim’s for minimum spanning trees, and Ford-Fulkerson for maximum flow.

Applications of grafiteoria span computer networks, social networks, biology, chemistry, logistics, scheduling, and circuit design. The field originated in the 18th century with contributions by Euler and has since evolved into a central area of discrete mathematics and theoretical computer science, with ongoing research in algorithmic graph theory, random graphs, and spectral graph theory.