MKLab - GRAPHS AND NETWORKS

Component

Tue, 08 Sep 2026 02:28:22 +0300

Component

A component, or connected component, of an undirected graph is a maximal connected subgraph: a collection of vertices in which every pair can be joined by a path, and which cannot be enlarged while remaining connected. Thus, the connected components partition the vertex set of a graph into disjoint subsets. A connected graph has exactly one component, while each isolated vertex forms its own component. Equivalently, define two vertices $u$ and $v$ to be related when there is a path from $u$ to $v$; this is an equivalence relation, and its equivalence classes are precisely the vertex sets of the connected components.

The number of components $c$ is an important invariant of a graph. For a graph with $n$ vertices, every spanning forest contains exactly $n-c$ edges. If the graph additionally has $m$ edges, its circuit rank is
m−n+c.m-n+c.
The number of components also appears in algebraic graph theory: it equals the multiplicity of the eigenvalue $0$ of the graph's Laplacian matrix. Components can be found efficiently using breadth-first search (BFS) or depth-first search (DFS) in linear time $O(n+m)$. When edges are progressively added, a disjoint-set (union–find) structure can maintain the components very efficiently. Connected-component algorithms also have practical applications in areas such as image analysis, where groups of adjoining pixels can be identified as separate objects.

Connected components become especially interesting in random graph theory. In the Erdős–Rényi model $G(n,p)$, the structure changes sharply as the edge probability $p$ increases. For $p<(1-\varepsilon)/n$, components are generally small; around the critical threshold $p\approx1/n$, components of order $n^{2/3}$ appear; and for $p>(1+\varepsilon)/n$, a single giant component containing a positive fraction of all vertices emerges. A still higher threshold around $p\sim(\log n)/n$ marks the transition from several components to a graph that is connected with high probability.

Key takeaways

A connected component is a maximal connected part of a graph.
Components partition all vertices into disjoint groups.
They can be computed in $O(n+m)$ time using BFS or DFS.
They connect graph theory with linear algebra, topology, algorithms, image processing, and random graphs.

ARTICLE

Clique problem

Tue, 08 Sep 2026 02:25:33 +0300

Summary

The clique problem is a fundamental problem in graph theory and theoretical computer science. Given an undirected graph $G=(V,E)$, a clique is a subset of vertices in which every pair of vertices is connected by an edge—in other words, the vertices form a complete subgraph. Several related computational problems arise: finding a maximum clique (the clique containing the largest possible number of vertices), finding all maximal cliques (cliques that cannot be enlarged), or deciding whether a graph contains a clique of size at least $k$. The size of a maximum clique is called the clique number, usually denoted $\omega(G)$. A useful duality is that a clique in $G$ corresponds exactly to an independent set in the complement graph $\overline{G}$.

Computationally, the problem is famous for its difficulty. The decision version—determining whether $G$ contains a $k$-clique—is NP-complete, while finding a maximum clique is NP-hard and is also exceptionally difficult to approximate efficiently. A straightforward brute-force method checks the $\binom{n}{k}$ possible sets of $k$ vertices, requiring roughly $O(n^k k^2)$ time when $k$ is variable. By contrast, finding just one maximal clique can be done greedily in linear time. For enumerating all maximal cliques, the classical Bron–Kerbosch algorithm is widely used; optimized versions achieve worst-case time $O(3^{n/3})$, which is essentially optimal because an $n$-vertex graph can itself contain as many as $3^{n/3}$ maximal cliques.

The clique problem has important applications beyond pure graph theory. In a social network, for example, vertices can represent people and edges mutual acquaintances, so a clique represents a group in which everyone knows everyone else. Similar clique-search techniques appear in bioinformatics, protein-interaction analysis, computational chemistry, molecular matching, evolutionary-tree reconstruction, automatic test generation, and even mathematical research. Much of modern research therefore focuses either on faster algorithms for special graph classes or on proving precisely why the general clique problem cannot be solved efficiently under standard complexity assumptions such as $P\ne NP$.

Key takeaways

Area: Graph Theory, Combinatorics, Algorithms, Computational Complexity.
Clique: a complete subgraph; every pair of its vertices is adjacent.
Maximum clique: largest clique; its size is $\omega(G)$.
Complexity: the $k$-clique decision problem is NP-complete, making the clique problem one of the classical examples of computational intractability.

ARTICLE

Arc diagram

Tue, 08 Sep 2026 01:55:35 +0300

Arc Diagram

An arc diagram is a method of drawing a graph in which all vertices are placed along a straight line and the edges are represented by semicircles or other convex curves drawn above or below that line. For directed graphs, a common convention is to use arcs above the line for one direction and below it for the opposite direction. Although the term arc diagram became popular through Martin Wattenberg’s 2002 work on visualizing repeated patterns in strings, similar graph representations date back at least to the 1960s.

Mathematically, arc diagrams are closely related to graph theory, graph drawing, planar graphs, Hamiltonian graphs, book embeddings, and crossing-number problems. Every planar graph can be represented as a crossing-free arc diagram if edges are allowed to consist of more than one semicircle. However, requiring each edge to be represented by a single semicircle imposes much stronger restrictions: such crossing-free drawings correspond to two-page book embeddings, and deciding whether a graph admits one is NP-complete. Minimizing the number of crossings is also NP-hard.

Arc diagrams also have applications well beyond pure graph drawing. They are used in information visualization, in the Farey diagram of rational numbers—where fractions $p/q$ and $r/s$ are connected when $|ps-rq|=1$—and in molecular biology for visualizing RNA, DNA, and protein structures. In RNA diagrams, for example, crossing arcs can represent pseudoknots and other aspects of molecular topology.

Key takeaways

Main mathematical area: Graph Theory / Discrete Mathematics.
Closely related fields: Computational Geometry, Graph Algorithms and Combinatorics.
Vertices lie on a line; edges are represented by arcs.
Arc diagrams are useful for studying planarity, crossings, Hamiltonian cycles and book embeddings.
Some optimization problems involving arc diagrams are NP-hard or NP-complete.
Applications include data visualization, number theory and computational biology.

ARTICLE

A Beginner’s Guide to Graphs

Mon, 07 Sep 2026 20:30:37 +0300

The freeCodeCamp article “A Beginner’s Guide to Graphs — From Google Maps to Chessboards” introduces graphs as data structures made of vertices (nodes) and edges (connections), showing how they model real-world systems such as Google Maps routes, social networks, web links, Git histories, dependencies, and chess moves. It explains major graph types—including directed, undirected, weighted, unweighted, cyclic, acyclic, and directed acyclic graphs (DAGs)—and compares two common ways to store them in programs: adjacency lists, which are memory-efficient for sparse graphs, and adjacency matrices, which provide fast edge lookups but require $O(V^2)$ memory.
The article then introduces the two fundamental traversal algorithms, Breadth-First Search (BFS), which explores nodes level by level and is especially useful for finding shortest paths in unweighted graphs, and Depth-First Search (DFS), which explores one branch deeply before backtracking and is useful for tasks such as cycle detection, topological sorting, and maze solving. Finally, it demonstrates these ideas through the Knight’s Travails chess problem, where each chessboard square becomes a node and legal knight moves become edges, illustrating how graph theory turns seemingly different practical problems into variations of the same underlying structure.

ARTICLE