Fact-checked by Grok 2 weeks ago

Graph theory

Graph theory is a branch of discrete mathematics that studies graphs, which are abstract mathematical structures consisting of a set of vertices (or nodes) representing objects and a set of edges connecting pairs of vertices to model relations between those objects.^[1] A graph G is formally defined as an ordered triple (V(G), E(G), \psi_G), where V(G) is a nonempty finite set of vertices, E(G) is a finite set of edges disjoint from V(G), and \psi_G is an incidence function mapping each edge to an unordered pair of vertices (which may be the same for loops).^[1] Graphs can be undirected (edges without direction), directed (digraphs with oriented edges), simple (no loops or multiple edges), or more general forms like multigraphs and pseudographs.^[2]^[3] The origins of graph theory trace back to 1736, when Leonhard Euler addressed the Seven Bridges of Königsberg problem, abstracting the city's bridge network into a graph to determine if a closed walk could traverse each bridge exactly once—an impossibility due to vertices of odd degree.^[3] Euler's paper, "Solutio problematis ad geometriam situs pertinentis," marked the field's birth, initially applied to recreational puzzles like map coloring and later formalized in the 19th century through works on electrical networks and chemical structures.^[3]^[4] Key early developments include the degree-sum formula, stating that the sum of all vertex degrees equals twice the number of edges, and characterizations of Eulerian circuits in connected graphs where all degrees are even.^[2] Graph theory has evolved into a cornerstone of modern mathematics and science, with profound applications across disciplines.^[5] In computer science, it enables algorithms for shortest paths (e.g., Dijkstra's), network optimization, and web ranking via Google's PageRank, which models the internet as a directed graph to assess page importance based on link structures.^[6] In biology and chemistry, graphs represent molecular bonds and genetic interactions; in transportation, they optimize routes and traffic flows; and in social sciences, they analyze networks of relationships.^[7]^[8] Notable theorems include the Four Color Theorem, proving that any planar graph (embeddable in a plane without edge crossings) is 4-colorable for vertex coloring without adjacent same-color vertices, and Kuratowski's theorem characterizing non-planar graphs.^[2] Spectral graph theory further extends applications to data mining, machine learning, and scientific computing through eigenvalue analysis of adjacency matrices.^[9]

Fundamentals

Undirected Graphs

An undirected graph is a fundamental structure in graph theory, modeling pairwise relations between objects without implying directionality. It consists of a set of vertices connected by edges that are bidirectional, representing symmetric relationships such as friendships in a social network or roads between cities. Unlike more specialized variants, undirected graphs form the basis for many theoretical and applied problems in combinatorics, computer science, and optimization.^[10] Formally, an undirected graph G is defined as an ordered pair G = (V, E), where V is a set of vertices (also called nodes) and E is a set of edges, with each edge being an unordered pair \{u, v\} where u, v \in V and typically u \neq v. A simple undirected graph restricts E to contain no loops (edges where u = v) and no multiple edges between the same pair of vertices, ensuring each possible connection appears at most once. In contrast, multigraphs allow multiple edges between the same pair, while pseudographs permit loops, which connect a vertex to itself and contribute twice to its degree in counting incidences. The degree d(v) of a vertex v is the number of edges incident to it, counting loops as two incidences. A key property is the handshaking lemma, which states that the sum of all vertex degrees equals twice the number of edges:

\sum_{v \in V} d(v) = 2|E|.

This lemma arises because each edge contributes to the degree of exactly two vertices (or twice to one in the case of a loop).^[11]^[12]^[13]^[14] Common examples illustrate these concepts. The complete graph K_n on n vertices connects every pair of distinct vertices with exactly one edge, resulting in \frac{n(n-1)}{2} edges and every vertex having degree n-1. The empty graph (also called the null or edgeless graph) on n vertices has |V| = n but |E| = 0, so all degrees are zero. The path graph P_n consists of n vertices arranged in a sequence with edges only between consecutive vertices, forming a chain of n-1 edges where the endpoints have degree 1 and internal vertices have degree 2. Graphs may be finite, with both V and E finite sets, or infinite, extending indefinitely in vertices or edges, which introduces complexities in analysis such as connectivity over unbounded structures. Additionally, graphs can be labeled, assigning distinct identifiers to vertices for explicit distinction, or unlabeled, treated up to isomorphism where only the structural relations matter. Directed graphs extend this model by orienting edges to indicate asymmetry, but undirected graphs remain central for symmetric interactions.^[15]^[16]^[17]^[18]^[19]

Directed Graphs

A directed graph, also known as a digraph, extends the concept of an undirected graph by assigning a direction to each edge, thereby modeling asymmetric relationships such as one-way streets or dependencies in a process.^[20]^[21] Formally, a directed graph G = (V, A) consists of a finite set V of vertices and a set A of ordered pairs (u, v) with u, v \in V, where each ordered pair is called an arc or directed edge from u to v.^[21]^[22] Unlike undirected graphs, arcs in a digraph are not symmetric, so (u, v) \in A does not imply (v, u) \in A, allowing for structures that capture oriented connections.^[20] In a directed graph, the degree of a vertex splits into the in-degree and out-degree: the in-degree of vertex v is the number of arcs entering v, denoted \deg^-(v), while the out-degree is the number of arcs leaving v, denoted \deg^+(v).^[12]^[23] An extension of the handshaking lemma applies here: the sum of all in-degrees equals the sum of all out-degrees, and both equal the number of arcs |A|, since each arc contributes one to an in-degree and one to an out-degree.^[23]^[24] Prominent examples of directed graphs include tournaments and directed acyclic graphs (DAGs). A tournament is a directed graph on a vertex set V where, for every pair of distinct vertices u, v \in V, exactly one of (u, v) or (v, u) is an arc, representing a complete orientation of the edges in a complete undirected graph.^[25]^[26] In contrast, a DAG is a directed graph containing no directed cycles, making it useful for modeling precedence relations, such as task scheduling where an arc (u, v) indicates that task u must precede task v.^[27]^[28] Connectivity in directed graphs is assessed in two ways: strong and weak. A digraph is strongly connected if, for every pair of vertices u, v \in V, there exists a directed path from u to v and from v to u.^[29]^[30] It is weakly connected if the underlying undirected graph—obtained by ignoring arc directions—is connected, allowing traversal between vertices regardless of direction.^[31]^[32] Any undirected graph can be converted to a directed graph through an orientation, which assigns a direction to each undirected edge, preserving the underlying structure while introducing asymmetry.^[33]^[34] This process is fundamental in studying properties like acyclicity or strong connectivity in oriented forms.^[35]

Graph Variants

Graph variants extend the basic models of undirected and directed graphs by incorporating additional structures such as weights, multiple connections, or generalized edges to model more complex relationships.^[36] Weighted graphs assign real numbers, known as weights, to the edges to represent quantities like distances, costs, or capacities in applications such as network routing. In a weighted graph, the adjacency matrix replaces binary entries with the corresponding edge weights, where the absence of an edge is typically denoted by zero or infinity depending on the context.^[36] This structure facilitates algorithms for optimization problems, such as finding minimum-cost paths. Multigraphs generalize simple graphs by permitting multiple edges between the same pair of vertices, allowing representation of parallel connections in systems like transportation networks.^[36] A pseudograph is a further extension that also allows loops, which are edges connecting a vertex to itself, useful for modeling self-referential relations.^[36] Hypergraphs extend the edge concept beyond pairs of vertices, where each hyperedge connects an arbitrary subset of vertices, enabling the modeling of multi-way relationships such as in database dependencies or combinatorial designs.^[37] Introduced formally in this framework, hypergraphs maintain the vertex set but replace pairwise edges with these generalized hyperedges.^[37] Bipartite graphs partition the vertex set into two disjoint subsets such that no edge connects vertices within the same subset, with all edges crossing between the subsets; this structure arises in matching problems like assignment tasks.^[38] A complete bipartite graph K_{m,n} connects every vertex in one subset of size m to every vertex in the other subset of size n, serving as a foundational example.^[38] Trees are connected graphs with no cycles, providing a minimal structure for connectivity with exactly n-1 edges for n vertices, essential in hierarchical data representations like file systems.^[39] Forests consist of disjoint unions of trees, representing collections of independent connected components without cycles.^[39] The number of distinct labeled trees on n vertices is given by Cayley's formula n^{n-2}.^[39]

History

Origins and Early Work

The origins of graph theory trace back to the 18th century, with Leonhard Euler's seminal work on a practical problem in the city of Königsberg (now Kaliningrad, Russia). In 1736, Euler addressed the Seven Bridges of Königsberg problem, which asked whether it was possible to traverse all seven bridges connecting four landmasses exactly once and return to the starting point. He modeled the landmasses as vertices and the bridges as edges in a multigraph, introducing the concepts of traversability and what would later be termed Eulerian paths and circuits. Euler proved that no such closed tour exists because the graph has four vertices of odd degree, establishing the foundational insight that connectivity alone is insufficient for traversability.^[1] Euler further defined an Eulerian circuit as a closed path that traverses each edge exactly once, occurring in a connected graph if and only if every vertex has even degree. An Eulerian path, which may start and end at different vertices, exists if exactly zero or two vertices have odd degree. These conditions, derived from parity arguments on edge incidences, marked the first systematic analysis of graph properties beyond mere connectivity and laid the groundwork for studying edge traversals. Euler's solution, published in the Commentarii Academiae Scientiarum Petropolitanae, is widely regarded as the birth of graph theory as a distinct mathematical discipline.^[1]^[40] In the 19th century, graph theory advanced through puzzle-based explorations and applications to counting and coloring. In 1847, Gustav Kirchhoff developed the matrix-tree theorem while studying electrical networks, providing a method to count the number of spanning trees in a connected graph by computing the determinant of a cofactor of its Laplacian matrix. This theorem equated the number of spanning trees to the value of any principal minor of the matrix formed by the degrees and adjacencies, bridging algebraic techniques with combinatorial enumeration. Meanwhile, in 1857, William Rowan Hamilton invented the Icosian game, a puzzle involving finding cycles that visit each vertex of a dodecahedral graph exactly once—now known as Hamiltonian cycles—popularizing the search for vertex-traversing tours distinct from Euler's edge-focused paths.^[1]^[41] Early applications extended to map coloring, with Francis Guthrie posing the four-color problem in 1852: whether any planar map could be colored using at most four colors such that adjacent regions receive different colors. This conjecture, communicated through Augustus De Morgan, translated to the chromatic number of planar graphs and spurred investigations by key figures like Peter Guthrie Tait, who in the 1880s attempted proofs by reducing it to edge-coloring cubic planar graphs, though his efforts revealed the problem's complexity without resolving it. These 19th-century contributions, centered on intuitive problems and manual verifications, emphasized graph theory's utility in geometry and puzzles before formal axiomatization.^[1]^[42]

20th-Century Developments

In the early 20th century, graph theory received a significant formalization through the works of Dénes Kőnig and Philip Hall on matchings in bipartite graphs. Kőnig's seminal book, Theorie der endlichen und unendlichen Graphen (1936), provided a comprehensive treatment of graph structures, including proofs of key results on bipartite matchings and vertex covers, establishing the equality between the size of a maximum matching and a minimum vertex cover in bipartite graphs. This built directly on Hall's earlier result, known as Hall's marriage theorem (1935), which states that in a bipartite graph with bipartition (X, Y), there exists a matching that covers all vertices in X if and only if for every subset S ⊆ X, the neighborhood N(S) satisfies |N(S)| ≥ |S|. These contributions formalized conditions for perfect matchings and laid foundational tools for combinatorial optimization. In 1930, Kazimierz Kuratowski characterized planar graphs, proving that a finite graph is planar if and only if it contains no subgraph homeomorphic to K_5 or K_{3,3}.^[1] A pivotal advancement in the mid-20th century was Ramsey's theorem (1930), which in its graph-theoretic form asserts that in any sufficiently large graph, or its complement, there exists a monochromatic clique of arbitrary size under edge colorings, guaranteeing the unavoidable emergence of ordered substructures in large systems. This theorem, initially motivated by logic, profoundly influenced graph theory by introducing ideas of unavoidable sets and sparking the field of Ramsey theory, which explores conditions for monochromatic subgraphs in colored graphs. Post-World War II, graph theory experienced explosive growth, particularly in extremal graph theory, driven by Paul Erdős and Pál Turán. Turán's theorem (1941) determines the maximum number of edges in an n-vertex graph without a complete subgraph K_{r+1}, achieved uniquely by the balanced complete r-partite graph T(n, r), with edge count (1 - 1/r) n^2 / 2. Erdős extended this framework through numerous papers starting in the late 1940s, introducing probabilistic methods to bound extremal functions and proving results like the Erdős–Stone theorem (1946), which generalizes Turán's result to arbitrary forbidden subgraphs by relating extremal numbers to chromatic numbers. These developments shifted focus toward asymptotic bounds and structural extremal problems, establishing extremal graph theory as a core subdiscipline. The 1950s marked an algorithmic turn, exemplified by the Ford–Fulkerson algorithm and the max-flow min-cut theorem (1956), which prove that in a flow network, the maximum flow value equals the minimum cut capacity, enabling efficient computation of flows via augmenting paths.^[43] By the 1960s, this algorithmic perspective permeated graph theory, integrating it with operations research and computer science, while combinatorial influences from Erdős and others fostered rapid institutional expansion. A major milestone came in 1976 with the proof of the four color theorem by Kenneth Appel and Wolfgang Haken, who used computer verification of reducible configurations to confirm that every planar graph is 4-colorable.^[1] The field's maturation culminated in the founding of dedicated journals, such as the Journal of Graph Theory in 1977, which provided a platform for publishing advances in combinatorial graph structures and algorithms. This institutional growth reflected graph theory's evolution from isolated theorems to a vibrant branch of mathematics, deeply intertwined with broader combinatorics.

Representations

Adjacency Structures

In graph theory, adjacency structures provide non-visual, computational representations that enable efficient storage, querying, and manipulation of graphs in algorithms and software implementations. These structures capture the connections between vertices without relying on geometric layouts, making them essential for processing large-scale graphs in fields like network analysis and optimization. Common variants include matrices and lists, each optimized for different graph densities and operations. The adjacency matrix is a square matrix A of size n \times n, where n is the number of vertices, and the entry A_{ij} is 1 if there is an edge between vertices i and j, and 0 otherwise; for undirected graphs, the matrix is symmetric.^[44] In directed graphs, A_{ij} = 1 indicates a directed edge from i to j, making the matrix potentially asymmetric.^[44] For weighted graphs, entries store the weight of the edge instead of 1, allowing representation of edge costs or capacities.^[45] This structure supports O(1) time for querying whether an edge exists between two vertices, though it requires \Theta(n^2) space regardless of the number of edges, which is inefficient for sparse graphs.^[46] The adjacency list represents a graph as an array of lists, where each index corresponds to a vertex and the list at that index contains its neighboring vertices.^[47] For undirected graphs, each edge appears in both endpoints' lists; in directed graphs, it appears only in the outgoing vertex's list. This structure achieves a space complexity of O(|V| + |E|), where |V| is the number of vertices and |E| is the number of edges, making it suitable for sparse graphs.^[46] Traversing the neighbors of a vertex v takes O(\deg(v)) time, where \deg(v) is the degree of v, which is advantageous for algorithms like breadth-first search that iterate over adjacent vertices.^[47] The incidence matrix is a |V| \times |E| matrix B where rows correspond to vertices and columns to edges, with B_{ve} = 1 if vertex v is incident to edge e, and 0 otherwise; for directed graphs, it distinguishes incoming and outgoing edges with signs or separate entries.^[48] This rectangular matrix is particularly useful in applications like network flows, where it models vertex-edge incidences for linear algebra-based computations such as solving flow conservation equations.^[48] Its space complexity is O(|V| \cdot |E|), which can be higher than adjacency lists for dense graphs but facilitates operations involving all edges simultaneously.^[46] An edge list is a simple collection of tuples or pairs, each specifying the endpoints of an edge, providing a compact representation without indexing by vertices.^[47] It uses O(|E|) space, ideal for sparse graphs where vertex degrees are low, and supports easy iteration over all edges for algorithms like Kruskal's for minimum spanning trees.^[47] However, checking for a specific edge requires linear time in |E|, limiting its use for frequent adjacency queries.^[47] These adjacency structures complement visual graph drawings by enabling algorithmic efficiency in computational settings.^[47]

Visualizations

Graph drawing methods aim to represent graphs in a visually intuitive manner, emphasizing structural properties such as connectivity and hierarchy. The most common approach uses node-link diagrams, in which vertices are positioned as points in the plane and edges are rendered as straight lines or curves connecting them, facilitating the perception of relationships and clusters within the graph.^[49] For planar graphs, which admit embeddings without edge crossings, Fáry's theorem guarantees the existence of a straight-line drawing that preserves planarity, using only straight segments for edges without intersections. This result, proved in 1948, ensures that curved edges in planar embeddings can always be replaced by straight ones while maintaining the crossing-free property.^[50] In non-planar graphs, edge crossings are inevitable, and the crossing number quantifies the minimum number of such crossings over all possible drawings. Computing the exact crossing number is NP-hard, even for restricted classes like cubic graphs, posing significant challenges for optimal layout algorithms.^[51] Force-directed algorithms address layout challenges by modeling graphs as physical systems, particularly through spring embedders. Eades' 1984 algorithm treats vertices as repelling particles connected by attractive springs along edges, applying iterative forces—repulsive via an inverse-square law and attractive logarithmically—to converge on balanced, symmetric positions suitable for small graphs up to about 30 vertices.^[52] For directed acyclic graphs (DAGs), layered or hierarchical drawings partition vertices into ordered horizontal layers based on topological levels, with edges directed downward to reveal precedence and flow. The Sugiyama framework, introduced in 1981, structures this process through cycle removal, layer assignment via longest paths, crossing minimization with barycenter heuristics, and coordinate refinement, producing clear visualizations of hierarchical structures like dependency networks.^[53]

Basic Structures and Operations

Subgraphs and Minors

In graph theory, a subgraph of a graph G = (V, E) is a graph H = (V', E') where V' \subseteq V and E' \subseteq E, with the edges in E' connecting vertices in V'.^[54] This relation allows for the deletion of vertices and edges from G to form H, preserving the structural properties of the original graph where applicable.^[54] A spanning subgraph of G retains all vertices in V but may delete some edges, resulting in a graph with vertex set V and a subset of E.^[55] An induced subgraph, also known as a vertex-induced subgraph, arises from selecting a subset S \subseteq V of vertices and including all edges from E that connect pairs of vertices in S; no edges are deleted between the chosen vertices.^[56] This construction ensures that the subgraph captures the complete neighborhood relations among the selected vertices as they exist in G.^[56] Induced subgraphs are crucial for studying hereditary properties, where the presence or absence of certain structures in subsets of vertices determines graph classes.^[56] A graph minor provides a coarser structural relation than subgraphs. A graph H is a minor of G if H can be obtained from G by a sequence of vertex deletions, edge deletions, and edge contractions, where contracting an edge merges its endpoints into a single vertex and removes any resulting loops or multiple edges.^[57] Edge contractions allow for the simplification of connected components, making minor containment a way to detect topological embeddings that are robust under local mergers.^[57] The concept of minors underpins forbidden minor characterizations of graph families. Wagner's theorem states that a graph is planar if and only if it contains neither the complete graph K_5 nor the complete bipartite graph K_{3,3} as a minor.^[57] This result, from Wagner's 1937 work, refines earlier characterizations by emphasizing contractions alongside deletions.^[57] Kuratowski's theorem complements this by characterizing non-planar graphs through forbidden subdivisions (topological minors) of K_5 or K_{3,3}, where subdivisions replace edges with paths; for planarity, these are equivalent to the minor conditions in Wagner's formulation.^[57] Graph isomorphism requires a bijective mapping between vertices that preserves adjacency exactly, meaning two graphs are identical up to relabeling. In contrast, minor containment is a weaker relation: H is a minor of G if G can be reduced to a graph isomorphic to H via deletions and contractions, allowing G to have additional structure beyond a mere copy of H.^[57] Subgraph containment sits between them, requiring an isomorphic copy of H as a subgraph of G without contractions, but permitting extra vertices and edges in G.^[54] These distinctions are fundamental in structural graph theory, where minors capture broad embeddability while isomorphisms demand precision.^[57]

Paths and Cycles

In graph theory, a walk is a sequence of vertices and edges alternately connected, where vertices and edges may repeat, formally defined as a finite non-empty sequence v_0, e_1, v_1, \dots, e_k, v_k such that each edge e_i is incident with vertices v_{i-1} and v_i. A trail is a walk with no repeated edges, and a path is a trail with no repeated vertices (except possibly the initial and terminal vertices coinciding). These structures form the basis for analyzing connectivity and traversals in graphs. A cycle is a closed path, meaning a path where the initial and terminal vertices are the same, with no other vertex repetitions, and at least three vertices. Paths and cycles induce subgraphs consisting of their vertices and edges, providing fundamental building blocks for more complex graph decompositions. A graph is connected if every pair of its vertices is joined by a path; otherwise, its connected components are the maximal connected subgraphs, partitioning the vertex set. An articulation point (or cut-vertex) is a vertex whose removal increases the number of connected components, while a bridge is an edge whose removal has the same effect. These elements identify critical points of vulnerability in graph connectivity. An Eulerian path (or trail) traverses each edge exactly once, existing in a connected graph if and only if exactly zero or two vertices have odd degree (the latter being the endpoints). An Eulerian circuit is a closed Eulerian path, requiring all vertices to have even degree in a connected graph; this characterization originates from Euler's solution to the Königsberg bridge problem.^[58] A Hamiltonian path visits each vertex exactly once, and a Hamiltonian cycle is a closed such path; unlike Eulerian structures, no simple degree conditions suffice for their existence, and deciding whether a graph contains one is NP-complete.^[59]

Key Problems and Algorithms

Connectivity and Flows

In graph theory, the vertex connectivity of a graph G, denoted \kappa(G), is the minimum number of vertices whose removal disconnects G or reduces it to a single vertex, provided G is not complete.^[60] Similarly, the edge connectivity \lambda(G) is the minimum number of edges whose removal disconnects G. These measures quantify the robustness of a graph against disconnection; for example, a graph is k-vertex-connected if \kappa(G) \geq k, meaning at least k vertices must be removed to separate it. By convention, the connectivity of a complete graph K_n is n-1, and isolated vertices have undefined connectivity.^[60] Menger's theorem provides a path-based characterization of connectivity, stating that in an undirected graph, the minimum number of vertices separating two non-adjacent vertices s and t equals the maximum number of vertex-disjoint paths from s to t.^[61] For edge connectivity, the edge version of Menger's theorem asserts that the minimum number of edges separating s and t equals the maximum number of edge-disjoint paths between them.^[61] These theorems, proved by Karl Menger in 1927, link structural separation to path multiplicity and underpin many connectivity algorithms.^[61] Network flows extend connectivity to capacitated directed graphs, where edges have non-negative capacities representing flow limits. A flow network includes a source vertex s and sink vertex t, with a feasible flow conserving flow at intermediate vertices and respecting capacities. The maximum flow problem seeks the highest total flow from s to t. The max-flow min-cut theorem, established by Ford and Fulkerson in 1956, equates this maximum flow value to the minimum capacity of an s-t cut—a partition of vertices into sets S (containing s) and T (containing t) where cut capacity is the sum of capacities of edges from S to T.^[43] The Ford-Fulkerson algorithm computes maximum flow by iteratively finding augmenting paths in the residual graph—directed edges reflecting remaining capacity—and augmenting flow along them until no such path exists.^[43] This method terminates for integer capacities but lacks polynomial time guarantees without specific path selection. The Edmonds-Karp variant, using breadth-first search for shortest augmenting paths, achieves O(VE^2) time complexity, where V is vertices and E is edges.^[62] Dinic's algorithm improves efficiency by building a level graph via BFS and finding blocking flows in phases, yielding O(V^2 E) time.^[63] Cuts formalize separation in flow networks: an s-t cut's capacity is the sum of forward capacities across the partition, and the min-cut equals the max-flow by the theorem.^[43] Algorithms like Edmonds-Karp identify the min-cut as saturated edges in the final residual graph from the source side.^[62] Maximum flows apply to bipartite matching by reducing the problem to a flow network: for bipartition U and W, add source edges of capacity 1 to U vertices and sink edges from W vertices, with unit capacities on original edges; the max-flow then equals the maximum matching size, as integer flows correspond to matchings.^[43] This reduction, leveraging the integrality of flows, enables efficient computation of maximum cardinalities in bipartite graphs.^[62]

Coloring and Partitioning

Graph coloring involves assigning colors to elements of a graph such that no two adjacent or incident elements receive the same color, serving as a fundamental tool for partitioning vertices or edges while respecting adjacency constraints. Vertex coloring specifically assigns colors to vertices so that adjacent vertices differ in color; the minimum number of colors required for such a proper coloring is the chromatic number, denoted \chi(G).^[64]^[65] This concept underpins many partitioning strategies, as a k-coloring partitions the vertex set into k independent sets, with the chromatic number providing a lower bound on the size of such partitions. Determining \chi(G) is NP-hard in general, but bounds and exact values exist for specific graph classes.^[65] A seminal result bounding the chromatic number is Brooks' theorem, established in 1941. For a connected graph G that is neither a complete graph nor an odd cycle, \chi(G) \leq \Delta(G), where \Delta(G) is the maximum degree of G.^[66] This theorem implies that most graphs can be colored with no more colors than their maximum degree, offering a tight upper bound except for the specified exceptions, where \chi(G) = \Delta(G) + 1. The proof relies on constructing a coloring by iteratively resolving conflicts in a greedy manner, highlighting the role of degree in limiting color requirements. Brooks' result has influenced subsequent work on coloring bounds and algorithmic approximations.^[66] Edge coloring extends these ideas to edges, assigning colors so that no two edges incident to the same vertex share a color; the minimum number of colors needed is the chromatic index \chi'(G). Vizing's theorem, proved in 1964, states that for any simple graph G, \chi'(G) is either \Delta(G) or \Delta(G) + 1, classifying graphs as Class 1 or Class 2 accordingly.^[67] The theorem's proof involves augmenting paths to resolve color conflicts, ensuring an edge coloring exists within the bound. This result is central to scheduling and resource allocation problems, where edges represent conflicts, and it remains a cornerstone for classifying edge-chromatic complexity.^[67] Graph partitioning often leverages coloring for balanced divisions, such as equitable coloring, where a proper k-coloring has color classes differing in size by at most one. The Hajnal–Szemerédi theorem asserts that every graph with maximum degree \Delta admits an equitable k-coloring for any k \geq \Delta + 1.^[68] This guarantees balanced partitions into independent sets, with applications in load balancing and fair division; the bound is sharp, as complete graphs K_{\Delta+1} require \Delta + 1 colors and equitable classes of size 1. Related partitioning problems, like minimum bisection—dividing vertices into two equal-sized sets while minimizing crossing edges—are NP-hard, even for planar graphs, underscoring the computational challenges beyond theoretical bounds.^[68] A landmark achievement in vertex coloring is the four color theorem, proved in 1976 by Kenneth Appel and Wolfgang Haken using computer-assisted methods. It states that every planar graph G satisfies \chi(G) \leq 4, resolving a conjecture dating to 1852.^[69] The proof reduces the problem to checking reducible configurations via discharging arguments, verifying over 1,900 cases computationally to ensure no counterexample exists. This theorem not only bounds coloring for planar graphs but also exemplifies the integration of theoretical combinatorics with computational verification, influencing map coloring and planar graph theory.^[69]

Enumeration and Optimization

Graph enumeration involves counting the number of subgraphs isomorphic to a given pattern within a host graph, a problem central to combinatorial graph theory. While enumerating arbitrary subgraphs is computationally challenging and often #P-complete, specific cases admit closed-form formulas. A seminal result is Cayley's formula, which states that the number of distinct spanning trees in the complete graph K_n on n labeled vertices is exactly n^{n-2}.^[70] This formula, proved using Prüfer codes or matrix-tree theorems, provides an exact count for tree subgraphs and has applications in network design and random graph analysis.^[71] Optimization problems in graph theory seek to find substructures of minimal or maximal weight under constraints, often solvable via efficient algorithms for special cases. Shortest path problems compute the minimum-weight path between vertices in weighted graphs. Dijkstra's algorithm, applicable to graphs with non-negative edge weights, uses a priority queue to greedily expand from the source, achieving O((V+E) \log V) time with a binary heap implementation.^[72] For graphs permitting negative weights (but without negative cycles), the Bellman-Ford algorithm relaxes all edges |V|-1 times, detecting negative cycles if further relaxation is possible, and runs in O(VE) time.^[73] Minimum spanning tree (MST) problems identify a tree of minimum total edge weight connecting all vertices in an undirected weighted graph. Kruskal's algorithm sorts edges by weight and adds them greedily if they connect disjoint components, using union-find for efficiency, yielding O(E \log E) time.^[74] Prim's algorithm grows the MST from an arbitrary vertex by repeatedly selecting the minimum-weight edge connecting a tree vertex to an outside one, also achieving O(E \log V) time with suitable data structures.^[75] Both algorithms guarantee an optimal MST via the cut property, ensuring greedy choices preserve optimality.^[76] Matching problems aim to pair vertices via edges without sharing endpoints, maximizing size or weight. In bipartite graphs, maximum matchings can be found in O(\sqrt{V} E) time using the Hopcroft-Karp algorithm, a refinement of the augmenting path method.^[77] König's theorem establishes that in bipartite graphs, the size of the maximum matching equals the size of the minimum vertex cover, enabling duality-based optimizations. For general graphs, Edmonds' blossom algorithm computes maximum matchings in O(V^4) time by contracting odd cycles. The traveling salesman problem (TSP) requires finding a minimum-weight Hamiltonian cycle visiting all vertices exactly once. TSP is NP-hard, as shown by reduction from the Hamiltonian cycle problem.^[59] For metric TSP (satisfying triangle inequality), Christofides' algorithm achieves a 1.5-approximation by combining an MST with a minimum-weight perfect matching on odd-degree vertices, then shortcutting to a tour. This remains the best known approximation ratio for general metric instances.

Applications

Computer Science and Networks

In computer science, graph theory underpins key data structures used in software systems. Call graphs, which model function calls as directed edges between nodes representing procedures, are essential in compilers for tasks such as optimization, inlining, and dead code elimination.^[78] These graphs enable analyses like interprocedural data flow, where vertices denote program points and edges capture control dependencies. In databases, graph representations facilitate query optimization by modeling join orders or execution plans as directed acyclic graphs (DAGs), allowing algorithms to select efficient evaluation strategies that minimize computational cost.^[79] Fundamental graph traversal algorithms, such as breadth-first search (BFS) and depth-first search (DFS), form the basis for many computational tasks. BFS explores graphs level by level from a starting node, using a queue to ensure shortest-path discovery in unweighted graphs, with a time complexity of O(V + E) where V is vertices and E is edges. DFS, conversely, delves deeply along branches using a stack or recursion, enabling applications like cycle detection and topological ordering, also in O(V + E) time.^[80] For directed acyclic graphs (DAGs), topological sort extends these traversals to linearize nodes respecting edge directions, as in Kahn's algorithm, which processes nodes with zero in-degree iteratively, achieving O(V + E) efficiency for scheduling dependencies in compilers or build systems. In network theory, graph algorithms optimize communication infrastructures. The Open Shortest Path First (OSPF) protocol, a link-state routing standard for IP networks, employs Dijkstra's algorithm on graph models of routers (nodes) and links (edges) to compute shortest-path trees, enabling dynamic route updates in response to topology changes.^[81] Social network analysis leverages centrality measures to quantify node influence; betweenness centrality, for instance, assesses a vertex's control over information flow by counting shortest paths passing through it, with applications in identifying key influencers or bottlenecks.^[82] Graph problems illuminate computational complexity boundaries. Many, like the Hamiltonian cycle—determining if a graph has a cycle visiting each vertex exactly once—are NP-complete, as proven by reduction from vertex cover, implying no known polynomial-time solution unless P = NP. This hardness underscores the challenge in exact optimization for large graphs, driving heuristic and approximation approaches in practice. Recent advances integrate graphs with machine learning via Graph Neural Networks (GNNs), which propagate node features across edges to learn representations for tasks like node classification or link prediction. The Graph Convolutional Network (GCN), a seminal GNN variant, approximates spectral convolutions on graph Laplacians for semi-supervised learning, scaling to large datasets with O(V + E) per layer.^[83]

Physical and Biological Sciences

In physics, graph theory provides a framework for modeling complex interactions, notably through Feynman diagrams, which represent particle interactions with vertices denoting interaction points and edges (lines) denoting particle propagators in quantum field theory calculations. Introduced by Richard Feynman in 1948, these diagrams simplify perturbative expansions by encoding mathematical amplitudes visually, enabling efficient computation of scattering processes in quantum electrodynamics. Percolation theory, another key application, uses random graphs to study phase transitions in disordered systems, such as the emergence of connected clusters in lattice graphs when edges are occupied with probability p. Pioneered by Broadbent and Hammersley in 1957, this model captures critical phenomena like fluid flow through porous media or conductivity thresholds, where a giant component forms at the percolation threshold p_c, marking a transition from isolated clusters to long-range connectivity.^[84] In chemistry, molecules are naturally modeled as undirected graphs, with vertices representing atoms and edges denoting chemical bonds, facilitating the analysis of structural properties and reactions. This representation, formalized in early graph-theoretic works on constitutional graphs, allows for the enumeration of isomers and prediction of molecular stability through topological indices like the Wiener index, which measures path lengths between atoms.^[85] Graph isomorphism algorithms further enable the assessment of chemical similarity by determining if two molecular graphs share identical connectivity, crucial for database searching and drug design; for instance, subgraph isomorphism identifies common motifs in analogous compounds, supporting virtual screening in cheminformatics.^[86] Biological systems leverage directed graphs to capture directional interactions, such as in metabolic pathways where vertices denote metabolites or enzymes and arcs represent biochemical reactions. These digraphs model flux directions and identify cycles in pathways like glycolysis, aiding in the discovery of regulatory bottlenecks through centrality measures.^[87] Protein interaction networks, represented as undirected or weighted graphs with proteins as nodes and interactions as edges, reveal modular structures like complexes via community detection, with degree distributions often following power laws indicative of hubs essential for cellular function.^[88] In ecology, food webs are modeled as bipartite graphs linking species (producers, consumers) via trophic edges, integrated with Lotka-Volterra equations to simulate predator-prey dynamics. Epidemiological models employ contact graphs to simulate disease spread, with the Susceptible-Infected-Recovered (SIR) framework propagating infections along edges in undirected networks. On scale-free graphs, characterized by hubs with high degrees, SIR dynamics exhibit no epidemic threshold, enabling rapid outbreaks even at low transmission rates, as observed in real-world pathogen transmissions.^[89] Flow models on biological transport graphs, such as vascular networks, briefly reference max-flow algorithms to quantify nutrient distribution limits. Emerging applications include quantum graphs in quantum computing, where vertices host qubits and edges define entanglement or walks, enabling scalable simulation of quantum states via graph neural networks for optimization problems.^[90] In social sciences, graph theory models interpersonal relationships, such as friendships, where individuals are represented as vertices and connections as edges, enabling analysis of network structures like centrality and clustering in social network analysis.^[91] A prominent example is the small-world network model, introduced by Watts and Strogatz, which interpolates between regular lattices and random graphs to capture high clustering and short path lengths observed in real-world social connections, such as acquaintance networks.^[92] Community detection algorithms, like the Louvain method developed by Blondel et al., optimize modularity to identify densely connected subgroups in large social graphs, revealing divisions such as interest-based clusters in online communities.^[93] In linguistics, graph theory underpins syntactic analysis through dependency trees, where words form a tree structure with directed edges indicating head-dependent relations, facilitating parsing algorithms that project dependencies without crossing arcs for languages like English.^[94] Semantic networks extend this by modeling lexical knowledge as graphs with nodes for concepts and labeled edges for relations like hypernymy or synonymy, supporting inference in natural language processing tasks such as word sense disambiguation.^[95] Economic applications leverage graph theory in modeling strategic interactions over networks, particularly through graphical games where payoffs depend on local neighborhoods, allowing computation of Nash equilibria—stable strategy profiles where no player benefits from unilateral deviation—in settings like market competition or resource allocation.^[96] Recent advancements in the 2020s apply graph neural networks to social media analytics, predicting user engagement by embedding interaction graphs with attention mechanisms to capture dynamic influences in platforms like Twitter.^[97] In pure mathematics, Ramsey theory, originating from Ramsey's foundational work on order in large structures, guarantees that sufficiently large graphs contain monochromatic cliques or independent sets under edge colorings, with implications for combinatorics in avoiding disorder. Spectral graph theory examines the eigenvalues of the adjacency matrix to infer global properties, such as the largest eigenvalue bounding the maximum degree and connectivity via spectral gaps in expander graphs.^[98] Algebraic graph theory integrates linear algebra and group theory to study graph invariants, like automorphism groups and spectrum, providing tools for isomorphism testing and expander constructions in combinatorial design.^[99] Graph coloring briefly relates to social grouping by partitioning networks into independent sets representing non-adjacent communities.

References

[1]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book is intended as an introduction to graph theory. Our aim has been to present what we consider to be the basic material, together with a wide.
[2]
[PDF] Introduction to Graph Theory - University of Utah Math Dept.
We will make the ideas of graphs and circuits from the Königsberg Bridge problem more precise by providing rigorous mathematical definitions. A graph G is a ...
[3]
[PDF] Graph Theory
As a matter of fact, we can just as easily define a graph to be a diagram consist- ing of small circles, called vertices, and curves, called edges, where each ...
[4]
[PDF] Graph Theory: Penn State Math 485 Lecture Notes
Introduction to Graph Theory. 1. An Overview of Graph Theory. Graph Theory began with Leonhard Euler in his study of the Bridges of Königsburg problem. Here's ...
[5]
[PDF] Introduction to Graph Theory
In recent years, graph theory has established itself as an important mathematical tool in a wide variety of subjects, ranging from operational research and ...
[6]
Spectral Graph Theory and Algorithmic Applications
Spectral methods have emerged as a powerful tool with applications in data mining, web search and ranking, computer vision, and scientific computing. They have ...
[7]
Combinatorics and Graph Theory | West Virginia University
Jan 28, 2025 · Both have applications in computer science, data science, biology, social network theory and neuroscience. They are closely related to many ...
[8]
Introduction to Graph Theory and Its Applications
Applications of Graph Theory: Network design, bioinformatics, machine learning, transportation systems, and more.
[9]
[PDF] Spectral Graph Theory and its Applications Daniel A. Spielman
Most of algebraic graph theory. Special graphs (e.g. Cayley graphs). Connections to codes and designs. Lots of work by theorists.
[10]
Undirected Graph -- from Wolfram MathWorld
A graph for which the relations between pairs of vertices are symmetric, so that each edge has no directional character (as opposed to a directed graph).
[11]
5.2. Background: basic concepts in graph theory — MMiDS Textbook
An undirected graph (or graph for short) is a pair where V is the set of vertices (or nodes) and is the set of edges.
[12]
GraphTheory
A simple undirected graph contains no duplicate edges and no loops (an edge from some vertex u back to itself). A graph with more than one edge between the same ...
[13]
[PDF] Chapter 8 Graphs: Definition, Applications, Representation
By this definition an undirected graph cannot have self loops since {v, v} = {v} 6∈. V. 2 . Undirected graphs represent symmetric relationships. Question 8.7 ...<|control11|><|separator|>
[14]
[PDF] Lecture 6: The degree of a vertex - Faculty Web Pages
The first tool we'll need to make use of degrees is the Handshake Lemma (also known as the degree sum formula). Lemma 1.1. In any graph G, the vertex degrees ...
[15]
Complete Graph -- from Wolfram MathWorld
A complete graph is a graph in which each pair of graph vertices is connected by an edge. The complete graph with n graph vertices is denoted K_n.
[16]
Empty Graph -- from Wolfram MathWorld
An empty graph on n nodes consists of n isolated nodes with no edges. Such graphs are sometimes also called edgeless graphs or null graphs.
[17]
Path Graph -- from Wolfram MathWorld
The path graph P_n is a tree with two nodes of vertex degree 1, and the other n-2 nodes of vertex degree 2. A path graph is therefore a graph that can be ...
[18]
[PDF] Graph.Theory
The study of infinite graphs is an attractive, but often neglected, part of graph theory. This chapter aims to give an introduction that starts gent-.
[19]
[PDF] Discrete Mathematics, Spring 2009 Graph theory notation
Mar 5, 2009 · An unlabeled graph is an equivalence class of graphs. We often represent an unlabeled graph by a single example or representative drawing.
[20]
4.2 Directed Graphs - Algorithms, 4th Edition
Jan 14, 2020 · A directed graph (or digraph) is a set of vertices and a collection of directed edges that each connects an ordered pair of vertices.
[21]
[PDF] 6.042J Chapter 6: Directed graphs - MIT OpenCourseWare
A graph with directed edges is called a directed graph or digraph. Definition 6.1.1. A directed graph G D .V;E/ consists of a nonempty set of nodes V and a set ...
[22]
[PDF] Diestel: Graph Theory - PRIP
Page 1. Reinhard Diestel. Graph Theory. Electronic Edition 2000 cс Springer-Verlag New York 1997, 2000. This is an electronic version of the second (2000) ...
[23]
[PDF] Graphs | CS@Cornell
Proof: For a directed graph: each edge contributes once to the indegree of some vertex, and once to the outdegree of some vertex. Thus |E| = sum of the ...
[24]
[PDF] Class Ten: Directed Graphs
Lemma. The sum of the in-degree of all the vertices in a directed graph is equal to the number of arcs. Similarly, the sum of the out-degree of all the.<|control11|><|separator|>
[25]
[PDF] Lecture 19: Tournaments 1 Definitions - Faculty Web Pages
A tournament is a special kind of directed graph. It has no loops, and for every pair of vertices v and w, exactly one of the possible arcs (v, w) or (v, ...
[26]
[PDF] Chapter 7: Digraphs Strong Digraphs - Gustavus Adolphus College
Dec 6, 2010 · A tournament is an orientation of a complete graph, i.e., it is a digraph such that for any distinct vertices u, v, exactly one of uv and vu is ...
[27]
[PDF] Directed Acyclic Graphs - Swarthmore College
DEFINITIONS. Dl. A digraph is acyclic if it has no directed cycles. D2: DAG is an acronym for directed acyclic graph. D3; a source in a digraph is a vertex of ...
[28]
[PDF] Directed Acyclic Graphs (DAGs) & Scheduling: Chapter 9.5
Definition 9.5. 1. A directed acyclic graph (DAG) is a directed graph with no cy- cles. DAGs have particular importance in computer science. They capture key ...
[29]
[PDF] 6 Graphs
Definition: A directed graph is strongly connected if there is a path from a to b and from b to a for any nodes a and b in the graph. A directed graph is weakly ...
[30]
https://courses.ics.hawaii.edu/ReviewICS241/morea/graphs/Graphs4-QA.pdf
[31]
[PDF] Connectivity - Computer Science - JMU
Definition: A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph, which is the undirected graph ...
[32]
ICS 46 Spring 2022, Notes and Examples: Graph Connectedness
Given this definition, we define weak connectedness as follows: We say that a directed graph is weakly connected if its underlying undirected graph is connected ...
[33]
[PDF] 5.1 Directed Graphs
An orientation of an undirected graph involves the selection of a direction for each edge, to create a directed graph. Like with our undirected graphs.
[34]
[PDF] A Graph Orientation Problem - Purdue e-Pubs
Graph orientation problems are usually of the following form: Given an undirected graph G, assign directions to its edges (Le. orient them) so that the.
[35]
Orientations - Graph Theory
An orientation of an undirected graph is a directed graph such that every edge is assigned a direction. ... A strong orientation of a graph is an orientation ...
[36]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book is intended as an introduction to graph theory. Our aim has been to present what we consider to be the basic material, together with a wide.
[37]
Graphs and hypergraphs : Berge, Claude - Internet Archive
Jan 30, 2023 · Publication date: 1973 ; Topics: Graph theory, Hypergraphs ; Publisher: Amsterdam, North-Holland Pub. Co.; New York, American Elsevier Pub. Co.Missing: paper | Show results with:paper
[38]
A translation of "Graphok és matrixok" by Dénes Kőnig (1931) - arXiv
Sep 5, 2020 · This paper, originally written in Hungarian by Dénes Kőnig in 1931, proves that in a bipartite graph, the minimum vertex cover and the maximum matching have ...
[39]
[PDF] 'COUNTING LABELLED TREES - UCLA Department of Mathematics
Let T(n) denote the number of trees Tn with n labelled nodes, for n = 1,2, .... The formula T(n) = nn-2 is usually attributed to Cayley (1889). Re pointed out, ...
[40]
[PDF] Early Writings on Graph Theory: Euler Circuits and The Königsberg ...
Dec 8, 2005 · In it, Euler undertakes a mathematical formulation of the now-famous Königsberg Bridge Problem: is it possible to plan a stroll through the town.
[41]
[PDF] The Origins of Graph Theory 1 Two problems - Jeremy Martin
Definition 1. A graph G consists of a set of vertices and a set of edges, where each edge connects two vertices. For example, the ...
[42]
[PDF] A Historical Overview of the Four-Color Theorem - Adelphi University
May 17, 2004 · Francis Guthrie (1831- 99), a student in London, first posed the conjecture in October, 1852, while he was coloring the regions on a map of ...
[43]
[PDF] maximal flow through a network - lr ford, jr. and dr fulkerson
THEOREM 1. (Minimal cut theorem). The maximal flow value obtainable in a network N is the minimum of v(D) taken over all disconnecting sets ...
[44]
Adjacency Matrix -- from Wolfram MathWorld
The adjacency matrix, sometimes also called the connection matrix, of a simple labeled graph is a matrix with rows and columns labeled by graph vertices.
[45]
Weighted Adjacency Matrix -- from Wolfram MathWorld
A weighted adjacency matrix A_f of a simple graph is defined for a real positive symmetric function f(d_i,d_j) on the vertex degrees d_i of a graph.
[46]
[PDF] Graph Representation - csail
Apr 12, 2011 · Graph Representation. The two main graph ... Thus, an adjacency list takes up Θ(V + E) space. Adjacency Matrix. An adjacency matrix ...
[47]
Representing graphs (article) | Algorithms - Khan Academy
Edge lists are simple, but if we want to find whether the graph contains a particular edge, we have to search through the edge list. If the edges appear in the ...
[48]
Incidence Matrix -- from Wolfram MathWorld
The incidence matrix of a graph gives the (0,1)-matrix which has a row for each vertex and column for each edge, and (v,e)=1 iff vertex v is incident upon edge ...
[49]
[PDF] Graph and Tree Layout - Stanford HCI Group - Stanford University
The primary concern of graph drawing is the spatial layout of nodes and edges. Often (but not always) the goal is to effectively depict the graph structure.
[50]
[PDF] On straight line representation of planar graphs.
In the present note I shall prove that if a finite graph can be represented on the plane at all, it can be represented with straight segments as edges too, ...
[51]
Crossing Number is NP-Complete | SIAM Journal on Matrix Analysis ...
We show that this problem is NP-complete, and hence there is not likely to be any efficient way to design an optimal embedding.Missing: original | Show results with:original
[52]
[PDF] A heuristic for graph drawing - UBC Computer Science
The mechanical system is simulated by the fo1lowing algorithm. C3/sqr(d) algorithm SPRING (G:graph); place vertices of G in ...Missing: directed | Show results with:directed
[53]
[PDF] Hierarchical Drawing Algorithms - Brown Computer Science
The easiest way to partition the vertex set of a DAG into layers is to take any spanning tree of the underlying undirected graph. It can be the depth first ...
[54]
Subgraph -- from Wolfram MathWorld
A subgraph of a graph is a graph whose vertex set and edge set are subsets of those of . If is a subgraph of , then is said to be a supergraph of. (Harary 1994 ...
[55]
[PDF] Section 2.2. Spanning and Induced Subgraphs
Sep 28, 2020 · Definition. A spanning subgraph of a graph G is a subgraph obtained by edge deletions only (so that a spanning subgraph is a subgraph of G ...
[56]
Induced Subgraph -- from Wolfram MathWorld
An induced subgraph is a subgraph obtained from an original graph by removing a subset of vertices and/or edges together with any edges whose endpoints are ...
[57]
[PDF] 12 Graph Minors - Jeff Erickson
Theorem 12.1 (Wagner [43]). A graph G is planar if and only if K5 and K3,3 are not minors of G. Wagner's thesis continued with a characterization of all ...
[58]
Leonhard Euler, “Solution of a problem in the geometry of position”
This famous paper on the bridges of Königsberg, in East Prussia, is generally considered to be the beginning of graph theory.
[59]
[PDF] REDUCIBILITY AMONG COMBINATORIAL PROBLEMS
REDUCIBILITY AMONG COMBINATORIAL PROBLEMS. +. Richard M. Karp. University of California at Berkeley. Abstract: A large class of computational problems involve ...
[60]
Vertex Connectivity -- from Wolfram MathWorld
The vertex connectivity kappa(G) of a graph G, also called point connectivity or simply connectivity, is the minimum size of a vertex cut.
[61]
[PDF] Zur allgemeinen Kurventheorie
Zur allgemeinen Kurventheorie. Von. Karl Menger (Amsterdam). I. Über die Bedeutung der Ordnungszahl von Kurvenpunkten. II. Über umfassendate Kurven. III ...Missing: 1927 original paper
[62]
[PDF] Theoretical Improvements in Algorithmic Efficiency for Network Flow ...
ABSTRACT. This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem, and the general minimum-cost flow problem.
[63]
Algorithm for Solution of a Problem of Maximum Flow in Networks ...
PDF | On Jan 1, 1970, E A Dinitz published Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation | Find, read and cite all ...
[64]
Vertex Coloring -- from Wolfram MathWorld
A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices.
[65]
Chromatic Number -- from Wolfram MathWorld
The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color.
[66]
On colouring the nodes of a network | Mathematical Proceedings of ...
Oct 24, 2008 · This research note, 'On colouring the nodes of a network', by R.L. Brooks, was published in Mathematical Proceedings of the Cambridge ...
[67]
Vizing's Theorem -- from Wolfram MathWorld
Vizing's theorem states that a graph can be edge-colored in either Delta or Delta+1 colors, where Delta is the maximum vertex degree of the graph.
[68]
A Short Proof of the Hajnal–Szemerédi Theorem on Equitable ...
Mar 1, 2008 · A proper vertex colouring of a graph is equitable if the sizes of colour classes differ by at most one. We present a new shorter proof of the ...<|separator|>
[69]
Every planar map is four colorable - Project Euclid
Every planar map is four colorable. K. Appel, W. Haken. DOWNLOAD PDF + SAVE TO MY LIBRARY. Bull. Amer. Math. Soc. 82(5): 711-712 (September 1976).
[70]
https://rcin.org.pl/impan/dlibra/publication/176630/edition/143722/content
[71]
A theorem on trees (Chapter 895) - The Collected Mathematical ...
Jul 5, 2011 · 895 - A theorem on trees. Published online by Cambridge University ... However, as you have access to this content, a full PDF is available via ...
[72]
[PDF] A Note on Two Problems in Connexion with Graphs
Numerische Mathematik 1, 269-271 (1959). A Note on Two Problems in Connexion with Graphs. By. E. W. DIJKSTRA. \Ve consider n points (nodes), some or all pairs ...
[73]
[PDF] richard bellman - on a routing problem
The purpose of this paper is to show that the functional equation technique of dynamic programming, [1, 2], combined with the concept of approximation in policy.Missing: shortest | Show results with:shortest
[74]
[PDF] On the Shortest Spanning Subtree of a Graph ... - Utah State University
On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Author(s): Joseph B. Kruskal, Jr. Source: Proceedings of the American ...
[75]
BSTJ 36: 6. November 1957: Shortest Connection Networks And ...
Jan 19, 2013 · November 1957: Shortest Connection Networks And Some Generalizations. (Prim, R.C.) ... PDF WITH TEXT download · download 1 file · SINGLE PAGE ...
[76]
[PDF] On the shortest spanning subtree of a graph and the traveling ...
On the shortest spanning subtree of a graph and the traveling salesman problem · 5,408 Citations · One Reference · Related Papers · What Is Semantic Scholar?
[77]
A framework for call graph construction algorithms
In this article we present a unifying framework for understanding call graph construction algorithms and an empirical comparison of a representative set of ...
[78]
[PDF] An Overview of Query Optimization in Relational Systems
Formulas to estimate the CPU and 110 costs of query execution for every operator. These formulas take into account the statistical properties of its input data ...
[79]
Depth-First Search and Linear Graph Algorithms | SIAM Journal on ...
The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples.
[80]
RFC 2328 - OSPF Version 2 - IETF Datatracker
OSPF is a link-state routing protocol, an Interior Gateway Protocol (IGP) for a single Autonomous System, using a shortest-path tree.Missing: theory | Show results with:theory
[81]
A Set of Measures of Centrality Based on Betweenness - jstor
1977, Vol. 40, No. 1, 35-41. A Set of Measures of Centrality. Based on Betweenness. LINTON C. FREEMAN. Lehigh University. A family of new measures of point and ...
[82]
Semi-Supervised Classification with Graph Convolutional Networks
Sep 9, 2016 · We present a scalable approach for semi-supervised learning on graph-structured data that is based on an efficient variant of convolutional neural networks.
[83]
Percolation processes | Mathematical Proceedings of the ...
Percolation studies how a medium's random properties influence a fluid's percolation, such as solute diffusing through solvent.
[84]
[PDF] Applications of Graph Theory in Chemistry
Con- stitutional (molecular) graphs have points (vertices) representing atoms and lines (edges) sym- bolizing malent bonds. This review deals with definition.
[85]
Kernel Approach to Molecular Similarity Based on Iterative Graph ...
We have introduced a molecular similarity measure defined directly on the annotated molecular graph, based on a recursive concept of graph similarity ...
[86]
Application of Graph Theory and Automata Modeling for the Study of ...
May 28, 2023 · In graph theory, it is usual to represent a metabolic pathway as a directed graph in which the nodes represent the metabolic substances and the ...
[87]
A Guide to Conquer the Biological Network Era Using Graph Theory
Jan 30, 2020 · In general, networks or graphs (mathematical way of representing a network) are used to capture relationships between entities or objects. In a ...General Network Properties · Network Centralities · Models · Network Alignment
[88]
Ecological graph theory: Simulating competition and coexistence on ...
Sep 18, 2025 · Our starting point is the classic Lotka-Volterra (LV) two-species competition model (Lotka, 1932; Volterra, 1931), which has been extensively ...1 Introduction · 2.1 Stochastic Lv... · 3 Results
[89]
Networks and epidemic models | Journal of The Royal Society ...
Here, we review the basis of epidemiological theory (based on random-mixing models) and network theory (based on work from the social sciences and graph theory ...
[90]
A Critical Review of Quantum Graph Neural Networks - arXiv
Aug 12, 2024 · This paper critically reviews the state-of-the-art in QGNNs, exploring various architectures. We discuss their applications across diverse fields.
[91]
Gene regulatory network inference from CRISPR perturbations in ...
Sep 17, 2023 · To model the effects of multiple upstream TFs at the same time, we developed a novel statistical estimator of the bipartite graph (BG), which ...
[92]
Chapter 3: Using Graphs to Represent Social Relations
Social network analysts use two kinds of tools from mathematics to represent information about patterns of ties among social actors: graphs and matrices.
[93]
Collective dynamics of 'small-world' networks - Nature
Jun 4, 1998 · Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability.
[94]
Fast unfolding of communities in large networks - IOPscience
We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization.Share This Article · Dates · Abstract
[95]
[PDF] Dependency Parsing - Stanford University
Graph-based methods for creating dependency structures are based on the use of maximum spanning tree methods from graph theory. • Both transition-based and ...
[96]
[PDF] Semantic Networks - John Sowa
A semantic network is a graph structure for representing knowledge in interconnected nodes and arcs, used for reasoning about knowledge.
[97]
[PDF] Graphical Models for Game Theory - UPenn CIS
In this work, we introduce graphical models for multi- player game theory, and give powerful algorithms for com- puting their Nash equilibria in certain cases.
[98]
Customer Engagement Prediction on Social Media: A Graph Neural ...
Sep 27, 2024 · We design a graph neural network model called the graph neural network with attention mechanism for customer engagement (GACE) to predict customer engagement.Missing: 2020s | Show results with:2020s
[99]
[PDF] an introduction to spectral graph theory
In this paper, we focus on the connection between the eigenvalues of the Laplacian matrix and graph connectivity. Also, we use the adjacency matrix of a graph ...
[100]
Algebraic Graph Theory - SpringerLink
Free delivery 14-day returnsAlgebraic Graph Theory ; Softcover Book USD 54.95. Price excludes VAT (USA) ; Hardcover Book USD 109.00 ; Explore related subjects. Discover the latest articles, ...