graphelméleti

Graphelméleti, known in English as graph theory, is the branch of mathematics that studies graphs—abstract structures consisting of vertices (or nodes) connected by edges. Graphs can be undirected or directed (digraphs), and they may be weighted or unweighted. Generalizations include multigraphs, where several edges may connect the same pair of vertices, and graphs with loops.

Core concepts in graphelméleti include connectivity, paths, cycles, and degrees. A path is a sequence of edges joining a sequence of vertices, while a cycle is a closed path with distinct internal vertices. The degree of a vertex counts incident edges (in directed graphs, in-degrees and out-degrees are distinguished). Subgraphs, trees, and forests describe related structures. Planarity concerns whether a graph can be drawn on a plane without crossing edges. The study also covers spectral properties, using matrices associated with graphs such as the adjacency and Laplacian matrices.

Key problems and theorems drive much of the field. The Four Color Theorem asserts that every planar graph can be colored with at most four colors so that adjacent vertices have different colors. Euler’s formula relates vertices, edges, and faces in planar graphs. The Handshaking Lemma states that the sum of vertex degrees equals twice the number of edges. Algorithmic graph theory focuses on efficient procedures to solve problems on graphs, including search algorithms, shortest-path methods, and maximum-flow/min-cut frameworks.

Applications of graphelméleti span computer networks, social and biological networks, chemistry, logistics, and scheduling. The field also encompasses probabilistic graph theory, random graphs, and various branches such as structural, algorithmic, and spectral graph theory, contributing to both theoretical insight and practical problem solving.