WikiDer > Упорядоченный граф - Википедия

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Март 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

An упорядоченный граф это график с общий заказ над его узлами.

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

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

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

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

Исходный график.	Эдж добавил, учитывая родителей ${ displaystyle a}$	Эдж добавил, учитывая родителей ${ displaystyle b}$

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

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

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

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

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

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

Смотрите также

• Направленный граф
• Локальная согласованность

Рекомендации

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