Упорядоченный граф

Упорядоченный граф — это граф с полным порядком в узлах.

В упорядоченном графе родительскими узлами являются узлы, соседние с ним и предшествующие ему в порядке упорядочения. ^{[ 1 ]} Точнее, $n$ является родителем $m$ в упорядоченном графе $\langle N,E,<\rangle$ если $(n,m)\in E$ и $n<m$ . Ширина узла — это количество его родителей, а ширина упорядоченного графа — это максимальная ширина его узлов.

упорядоченного Индуцированный граф графа получается путем добавления некоторых ребер к графу упорядочения с использованием метода, описанного ниже. Индуцированная ширина упорядоченного графа — это ширина его индуцированного графа. ^{[ 2 ]}

Учитывая упорядоченный граф, его индуцированный граф — это еще один упорядоченный граф, полученный путем соединения некоторых пар узлов, которые являются родительскими для другого узла. В частности, узлы рассматриваются поочередно в порядке от последнего к первому. Для каждого узла, если два его родителя не соединены ребром, это ребро добавляется. Другими словами, при рассмотрении узла $n$ , если оба $m$ и $l$ являются его родителями и не соединены ребром, ребром $(m,l)$ добавляется на график. Поскольку родители узла всегда связаны друг с другом, индуцированный граф всегда хордальный .

В качестве примера вычисляется индуцированный граф упорядоченного графа. Порядок представлен положением его узлов на рисунках: a — последний узел, а d — первый.


Оригинальный график.	Эдж добавил, учитывая родителей $a$	Эдж добавил, учитывая родителей $b$

Узел $a$ рассматривается в первую очередь. Его родители $b$ и $c$ , поскольку они оба соединены с $a$ и оба предшествуют $a$ в заказе. Поскольку они не соединены ребром, добавляется единица.

Узел $b$ считается вторым. Хотя этот узел имеет только $d$ в качестве родителя в исходном графе он также имеет $c$ в качестве родителя в частично построенном индуцированном графе. Действительно, $c$ присоединяется к $b$ а также предшествовать $b$ в заказе. В результате соединение ребер $c$ и $d$ добавляется.

Учитывая $d$ не производит никаких изменений, поскольку у этого узла нет родителей.

Обработка узлов по порядку имеет значение, поскольку введенные ребра могут создавать новых родительских узлов, которые затем имеют отношение к введению новых ребер. Следующий пример показывает, что другой порядок создает другой индуцированный граф того же исходного графа. Порядок тот же, что и выше, но $b$ и $c$ поменяны местами.


Тот же график, но порядок $b$ и $c$ заменен	График после рассмотрения $a$

Как и в предыдущем случае, оба $b$ и $c$ являются родителями $a$ . Таким образом, добавляется ребро между ними. Согласно новому порядку, вторым узлом, который рассматривается, является $c$ . Этот узел имеет только одного родителя ( $b$ ). Таким образом, новое ребро не добавляется. Третий рассматриваемый узел – это $b$ . Его единственным родителем является $d$ . Действительно, $b$ и $c$ на этот раз не присоединились. В результате новое ребро не появляется. С $d$ также не имеет родителя, окончательный индуцированный граф показан выше. Этот индуцированный граф отличается от графа, созданного предыдущим упорядочением.

См. также

Ссылки

Дектер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN 1-55860-890-7

^ Страница 86 Дектер. (2003). Обработка ограничений
^ Страница 87 Дектер. (2003). Обработка ограничений

[1] Страница 86 Дектер. (2003). Обработка ограничений

[2] Страница 87 Дектер. (2003). Обработка ограничений

[ 1 ]

[ 2 ]