An ordered graph is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
with a
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
over its nodes.
In an ordered graph, the parents of a node are the nodes that are adjacent to it and precede it in the ordering. More precisely,
is a parent of
in the ordered graph
if
and
. The width of a node is the number of its parents, and the width of an ordered graph is the maximal width of its nodes.
The induced graph of an ordered graph is obtained by adding some edges to an ordering graph, using the method outlined below. The induced width of an ordered graph is the width of its induced graph.
[Page 87 Dechter. (2003). Constraint Processing]
Given an ordered graph, its induced graph is another ordered graph obtained by joining some pairs of nodes that are both parents of another node. In particular, nodes are considered in turn according to the ordering, from last to first. For each node, if two of its parents are not joined by an edge, that edge is added. In other words, when considering node
, if both
and
are parents of it and are not joined by an edge, the edge
is added to the graph. Since the parents of a node are always connected with each other, the induced graph is always
chordal.
As an example, the induced graph of an ordered graph is calculated. The ordering is represented by the position of its nodes in the figures: a is the last node and d is the first.
Node
is considered first. Its parents are
and
, as they are both joined to
and both precede
in the ordering. Since they are not joined by an edge, one is added.
Node
is considered second. While this node only has
as a parent in the original graph, it also has
as a parent in the partially built induced graph. Indeed,
is joined to
and also precede
in the ordering. As a result, an edge joining
and
is added.
Considering
does not produce any change, as this node has no parents.
Processing nodes in order matters, as the introduced edges may create new parents, which are then relevant to the introduction of new edges. The following example shows that a different ordering produces a different induced graph of the same original graph. The ordering is the same as above but
and
are swapped.
As in the previous case, both
and
are parents of
. Therefore, an edge between them is added. According to the new order, the second node that is considered is
. This node has only one parent (
). Therefore, no new edge is added. The third considered node is
. Its only parent is
. Indeed,
and
are not joined this time. As a result, no new edge is introduced. Since
has no parent as well, the final induced graph is the one above. This induced graph differs from the one produced by the previous ordering.
See also
*
Directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
*
Local consistency
In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier t ...
References
*
{{reflist
Constraint programming
Extensions and generalizations of graphs