Jump to content

Хорошее связующее дерево

Условия хорошего связующего дерева

В математической области теории графов хорошее остовное дерево [1] встроенного планарного графа корневое связующее дерево представляет собой чьи недревесные ребра удовлетворяют следующим условиям.

  • нет ребра, не являющегося деревом где и лежать на пути от корня к листу,
  • ребра, инцидентные вершине можно разделить на три комплекта и , где,
    • представляет собой набор недревесных ребер, они заканчиваются в красной зоне
    • представляет собой набор ребер дерева, они являются детьми
    • представляет собой набор недревесных ребер, оканчивающихся зеленой зоной

Формальное определение

[ редактировать ]

Источник: [1] [2]

Иллюстрация для и наборы ребер

Позволять быть плоским графом. Позволять быть корневым связующим деревом . Позволять быть путем в от корня в вершину . Путь разделяет детей , , кроме , на две группы; левая группа и правильная группа . Ребенок из находится в группе и обозначается если край появляется перед краем в порядке часовой стрелки ребер, инцидентных когда заказ начинается с края . Аналогично, ребенок из есть в группе и обозначается если край появляется после края по часовой стрелке от ребер, инцидентных когда заказ начинается с края . Дерево называется хорошим связующим деревом [1] из если каждая вершина из удовлетворяет следующим двум условиям относительно .

  • [Условие1] не имеет ребра, не являющегося деревом , ; и
  • [Cond2] края инцидентный вершине исключая можно разделить на три непересекающихся (возможно, пустых) множества. и удовлетворяющие следующим условиям (a)-(c)
    • (а) Каждый из и представляет собой набор последовательных недревесных ребер и представляет собой набор последовательных ребер дерева.
    • (б) Края множества , и появляются по часовой стрелке в этом порядке от края .
    • (c) Для каждого ребра , содержится в , , и для каждого ребра , содержится в , .
      Плоский граф (вверху), хорошее связующее дерево из (внизу) сплошные ребра являются частью хорошего остовного дерева, а пунктирные ребра - это ребра, не являющиеся деревьями в относительно .

Приложения

[ редактировать ]

При монотонном рисовании графиков [2] в 2-видимом представлении графов. [1]

Поиск хорошего связующего дерева

[ редактировать ]

Каждый планарный граф имеет вложение такой, что содержит хорошее связующее дерево. Хорошее остовное дерево и подходящее вложение можно найти из в линейном времени. [1] Не все вложения содержать хорошее связующее дерево.

См. также

[ редактировать ]
  1. ^ Jump up to: а б с д и Хоссейн, штат Мэриленд Икбал; Рахман, Мэриленд Саидур (23 ноября 2015 г.). «Хорошие связующие деревья в рисовании графов» . Теоретическая информатика . 607 : 149–165. дои : 10.1016/j.tcs.2015.09.004 .
  2. ^ Jump up to: а б Хоссейн, штат Мэриленд Икбал; Рахман, доктор Саидур (28 июня 2014 г.). «Монотонные сеточные рисунки плоских графов». Границы в алгоритмике . Конспекты лекций по информатике. Том. 8497. Спрингер, Чам. стр. 105–116. arXiv : 1310.6084 . дои : 10.1007/978-3-319-08016-1_10 . ISBN  978-3-319-08015-4 . S2CID   10852618 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 9afb00d8f1b9e5d12f1e89da6b82db52__1719613140
URL1:https://arc.ask3.ru/arc/aa/9a/52/9afb00d8f1b9e5d12f1e89da6b82db52.html
Заголовок, (Title) документа по адресу, URL1:
Good spanning tree - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)