In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
subfield of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
a level structure of an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
is a
partition of the
vertices into subsets that have the same
distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
from a given root vertex.
[.]
Definition and construction
Given a
connected graph ''G'' = (''V'', ''E'') with ''V'' the set of
vertices and ''E'' the set of
edges, and with a root vertex ''r'', the level structure is a partition of the vertices into subsets ''L
i'' called levels, consisting of the vertices at distance ''i'' from ''r''. Equivalently, this set may be defined by setting ''L''
0 = , and then, for ''i'' > 0, defining ''L
i'' to be the set of vertices that are neighbors to vertices in ''L''
''i'' − 1 but are not themselves in any earlier level.
The level structure of a graph can be computed by a variant of
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...
:
algorithm level-BFS(G, r):
Q ←
for ℓ from 0 to ∞:
process(Q, ℓ) ''// the set Q holds all vertices at level ℓ''
mark all vertices in Q as discovered
Q' ←
for u in Q:
for each edge (u, v):
if v is not yet marked:
add v to Q'
if Q' is empty:
return
Q ← Q'
Properties
In a level structure, each edge of ''G'' either has both of its endpoints within the same level, or its two endpoints are in consecutive levels.
Applications
The partition of a graph into its level structure may be used as a heuristic for graph layout problems such as
graph bandwidth.
The
Cuthill–McKee algorithm is a refinement of this idea, based on an additional sorting step within each level.
Level structures are also used in algorithms for
sparse matrices, and for constructing
separators of planar graphs.
[.]
References
{{reflist
Graph theory objects