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

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

Заказал график представляет собой график , с общим порядка над ее узлами.

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

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

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

В качестве примера вычисляется индуцированный граф упорядоченного графа. Порядок представлен положением его узлов на рисунках: 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