Bandwidth of undirected graphs¶
Definition¶
The bandwidth of a matrix
is the smallest integer
such that all
non-zero entries of
are at distance
from the diagonal. The bandwidth
of an undirected graph
is the minimum bandwidth of the adjacency
matrix of
, over all possible relabellings of its vertices.
Path spanner: alternatively, the bandwidth measures how tightly a path
represents the distance of a graph . Indeed, if the vertices of
can be
ordered as
in such a way that
then
.
Proof: for all
(i.e.
), the constraint ensures that
, meaning that adjacent vertices are at distance at most
in the path ordering. That alone is sufficient to ensure that
.
As a byproduct, we obtain that
in general: let
be the vertices of a shortest
-path. We have:
Satisfiability of a partial assignment¶
Let us suppose that the first vertices
of
have already
been assigned positions
in an ordering of
of bandwidth
. Where can
appear ?
Because of the previous definition, must be at distance at most
from
, and in general at distance at most
from
. Each range is an interval of
, and because the intersection of two
intervals is again an interval we deduce that in order to satisfy all these
constraints simultaneously
must belong to an interval defined from this
partial assignment.
Applying this rule to all non-assigned vertices, we deduce that each of them
must be assigned to a given interval of . Note that this can also
be extended to the already assigned vertices, by saying that
with
must be assigned within the interval
.
This problem is not always satisfiable, e.g. 5 vertices cannot all be assigned
to the elements of . This is a matching problem which, because all
admissible sets are intervals, can be solved quickly.
Solving the matching problem¶
Let points
be given, along with two functions
. Is there an ordering
of them such that
? This is equivalent to Hall’s bipartite matching theorem, and can in
this specific case be solved by the following algorithm:
- Consider all vertices
sorted increasingly according to
- For each of them, assign to
the smallest position in
which has not been assigned yet. If there is none, the assignment problem is not satisfiable.
Note that the latest operation can be performed with very few bitset operations
(provided that ).
The algorithm¶
This section contains totally subjective choices, that may be changed in the hope to get better performances.
- Try to find a satisfiable ordering by filling positions, one after the other (and not by trying to find each vertex’ position)
- Fill the positions in this order:
Note
There is some symmetry to break as the reverse of a satisfiable ordering is also a satisfiable ordering.
This module contains the following methods¶
bandwidth() |
Compute the bandwidth of an undirected graph |
bandwidth_heuristics() |
Uses Boost heuristics to approximate the bandwidth of the input graph |
Functions¶
-
sage.graphs.graph_decompositions.bandwidth.
bandwidth
(G, k=None)¶ Compute the bandwidth of an undirected graph.
For a definition of the bandwidth of a graph, see the documentation of the
bandwidth
module.INPUT:
G
(a graph)k
– set to an integer value to test whether, or to
None
(default) to compute.
OUTPUT:
When
is an integer value, the function returns either
False
or an ordering of cost.
When
is equal to
None
, the function returns a pair(bw, ordering)
.See also
sage.graphs.generic_graph.GenericGraph.adjacency_matrix()
– return the adjacency matrix from an ordering of the vertices.EXAMPLES:
sage: from sage.graphs.graph_decompositions.bandwidth import bandwidth sage: G = graphs.PetersenGraph() sage: bandwidth(G,3) False sage: bandwidth(G) (5, [0, 4, 5, 8, 1, 9, 3, 7, 6, 2]) sage: G.adjacency_matrix(vertices=[0, 4, 5, 8, 1, 9, 3, 7, 6, 2]) [0 1 1 0 1 0 0 0 0 0] [1 0 0 0 0 1 1 0 0 0] [1 0 0 1 0 0 0 1 0 0] [0 0 1 0 0 0 1 0 1 0] [1 0 0 0 0 0 0 0 1 1] [0 1 0 0 0 0 0 1 1 0] [0 1 0 1 0 0 0 0 0 1] [0 0 1 0 0 1 0 0 0 1] [0 0 0 1 1 1 0 0 0 0] [0 0 0 0 1 0 1 1 0 0] sage: G = graphs.ChvatalGraph() sage: bandwidth(G) (6, [0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2]) sage: G.adjacency_matrix(vertices=[0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2]) [0 0 1 1 0 1 1 0 0 0 0 0] [0 0 0 1 1 1 0 1 0 0 0 0] [1 0 0 0 1 0 0 1 1 0 0 0] [1 1 0 0 0 0 0 0 1 1 0 0] [0 1 1 0 0 0 1 0 0 1 0 0] [1 1 0 0 0 0 0 0 0 0 1 1] [1 0 0 0 1 0 0 1 0 0 0 1] [0 1 1 0 0 0 1 0 0 0 1 0] [0 0 1 1 0 0 0 0 0 0 1 1] [0 0 0 1 1 0 0 0 0 0 1 1] [0 0 0 0 0 1 0 1 1 1 0 0] [0 0 0 0 0 1 1 0 1 1 0 0]