Ordered graph

Ordered graph: An ordered graph is a graph with a total order over its nodes.

In an ordered graph, the parents of a node are the nodes that are joined to it and precede it in the ordering. More precisely, $n$ is a parent of $m$ in the ordered graph $\langle N,E,< \rangle$ if $(n,m) \in E$ and $n < m$ . 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.

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 $n$ , if both $m$ and $l$ are parents of it and are not joined by an edge, the edge $(m, l)$ 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.

The original graph. Edge added considering the parents of $a$ Edge added considering the parents of $b$

Node $a$ is considered first. Its parents are $b$ and $c$ , as they are both joined to $a$ and both precede $a$ in the ordering. Since they are not joined by an edge, one is added.

Node $b$ is considered second. While this node only has $d$ as a parent in the original graph, it also has $c$ as a parent in the partially built induced graph. Indeed, $c$ is joined to $b$ and also precede $b$ in the ordering. As a result, an edge joining $c$ and $d$ is added.

Considering $d$ 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 $b$ and $c$ are swapped.

Same graph, but the order of $b$ and $c$ is swapped Graph after considering $a$

As in the previous case, both $b$ and $c$ are parents of $a$ . Therefore, an edge between them is added. According to the new order, the second node that is considered is $c$ . This node has only one parent ( $b$ ). Therefore, no new edge is added. The third considered node is $b$ . Its only parent is $d$ . Indeed, $b$ and $c$ are not joined this time. As a result, no new edge is introduced. Since $d$ 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

Local consistency

References

Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. http://www.ics.uci.edu/~dechter/books/index.html. ISBN 1-55860-890-7

Categories:
Constraint programming
Extensions and generalizations of graphs

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

Interval chromatic number of an ordered graph — In mathematics, the interval chromatic number X … Wikipedia
Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges … Wikipedia
Graph of a function — In mathematics, the graph of a function f is the collection of all ordered pairs ( x , f ( x )). In particular, if x is a real number, graph means the graphical representation of this collection, in the form of a curve on a Cartesian plane,… … Wikipedia
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia
Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
Graph property — In graph theory a graph property is any inherently graph theoretical property of graphs (formal definitions follow), distinguished from properties of graphs described in terms of various graph representations: graph drawings, data structures for… … Wikipedia
Graph (data structure) — In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes (also called vertices) and a set of edges that establish relationships (connections) between the nodes. The graph… … Wikipedia
graph theory — A branch of mathematics used to represent relations and networks. A graph consists of a set of points (nodes or vertices) and the pairwise links between them (arcs or lines). In sociological applications, the nodes are typically individuals,… … Dictionary of sociology
Graph product — A graph product is a binary operation on graphs. There are several similarly defined operations on graphs, called product . Given two graphs G1 and G2 , their product H is a graph such that * the vertex set of H is the Cartesian product V(G 1)… … Wikipedia
graph theory — noun The study of the properties of graphs (in the sense of sets of vertices and sets of ordered or unordered pairs of vertices) … Wiktionary

Academic Dictionaries and Encyclopedias

Ordered graph

See also

References

Look at other dictionaries:

Share the article and excerpts


The original graph.	Edge added considering the parents of $a$	Edge added considering the parents of $b$


Same graph, but the order of $b$ and $c$ is swapped	Graph after considering $a$

Academic Dictionaries and Encyclopedias

Wikipedia

Ordered graph

See also

References

Look at other dictionaries:

Share the article and excerpts

Direct link