grafteori

Grafteori, or graph theory, is a branch of mathematics and computer science that studies graphs: abstract structures described by a set of vertices (nodes) connected by edges (links). A graph G is typically written as G=(V,E). Edges may be undirected or directed (digraphs), and can be weighted. Graphs can be simple (no parallel edges or loops) or multigraphs and may be planar or nonplanar.

Key notions include paths, cycles, and connectivity. The degree of a vertex counts incident edges. A graph is connected if there is a path between every pair of vertices; otherwise it has connected components. Subgraphs, spanning trees, and cycles are central objects. Planar graphs can be drawn on a plane without edge crossings.

Core algorithmic topics: shortest path algorithms (Dijkstra, Bellman-Ford); all-pairs shortest paths (Floyd-Warshall). Minimum spanning trees (Prim, Kruskal). Max-flow min-cut theorem and associated algorithms (Ford-Fulkerson, Edmonds-Karp). Eulerian paths and cycles characterize routes that traverse every edge exactly once; Hamiltonian paths and cycles concern visits to every vertex.

History: Graph theory originated with Leonhard Euler's 1736 solution to the Königsberg bridge problem, which laid the foundations for treating problems as graphs and questions about traversability. The term graph and the modern formal framework developed over the 19th and 20th centuries.

Applications span computer networks, transportation and logistics, social networks, circuit design, chemistry, biology, and scheduling. Graph theory remains a vibrant area of research, linking combinatorics, algebra, geometry, and computer science, and providing practical tools for data analysis and optimization.