Binaargraafiku

Binaargraafiku is a term used in graph theory to describe a class of graphs whose vertices are labeled by binary strings and whose edges reflect binary relations among those strings. In many contexts, the vertex set consists of all binary strings of a fixed length n, and adjacency is defined by a rule based on bit differences, shifts, or other binary operations. These graphs are studied for their regular structure, symmetry, and applications in computing and coding theory.

A canonical example is the n-dimensional hypercube, denoted Qn. Its vertices correspond to binary strings of length n, and two vertices are adjacent if they differ in exactly one bit. The hypercube is 2^n-vertex and n-regular, with a diameter of n and a total of n·2^(n−1) edges. The vertex set can be arranged in Gray code order so that successive vertices differ by a single bit, which has practical importance in minimizing bit changes in digital circuits.

Another important family is the binary De Bruijn graph B(2, n). It is a directed graph with 2^n vertices representing binary strings of length n; from each vertex there are two outgoing edges (and two incoming edges), corresponding to appending 0 or 1 and shifting. De Bruijn graphs are widely used in sequencing, shift-register design, networking, and combinatorial constructions due to their compact state space and dense connectivity.

Related notions include Hamming graphs over binary alphabets and other state-space graphs built from binary representations. Binaargraafikud are relevant in areas such as network topology design for parallel computing, error-correcting codes, and digital circuit optimization, where binary state spaces and efficient routing or traversal are important.