Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов , в связном множестве доминирующего и максимальным лист остове две тесно связанные структуры , определенные на неориентированном графе .

Определения [ править ]

Связное доминирующее множество графа G - это множество вершин D с двумя свойствами:

  1. Любой узел в D может достигнуть любой другой узел в D по пути , который остается полностью в пределах D . То есть, D индуцирует связный подграф G .
  2. Каждая вершина в G либо принадлежит D или находится рядом с вершиной D . То есть, D является доминирующим набором из G .

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

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

Дополнительность [ править ]

Если d - это число связного доминирования графа G с n вершинами , где n> 2 , а l - его максимальное число листьев, то три величины d , l и n подчиняются простому уравнению

[3]

Если D - связное доминирующее множество, то существует остовное дерево в G , листья которого включают все вершины, не принадлежащие D : сформируйте остовное дерево подграфа, индуцированного D , вместе с ребрами, соединяющими каждую оставшуюся вершину v , не входящую в D ближнего V в D . Это показывает, что l ≥ n - d .

В другом направлении, если T является любым остовным деревом в G , то вершины T , которые не являются листами образуют связное доминирующее множество G . Это показывает, что n - l ≥ d . Объединение этих двух неравенств доказывает равенство n = d + l .

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

Алгоритмы [ править ]

Это NP-полно для тестирования , существует ли связное множество доминирующего размера меньше заданного порогового значения, или , что эквивалентно испытание существует ли остов с по крайней мере , заданному количеству листьев. Поэтому считается, что задача о минимальном связном доминирующем множестве и задача о максимальном листовом остовном дереве не могут быть решены за полиномиальное время.

Если рассматривать с точки зрения алгоритмов аппроксимации, связанное доминирование и максимальное листовое остовное дерево не одно и то же: приближение одного к заданному коэффициенту приближения не то же самое, что приближение другого к тому же соотношению. Существует аппроксимация минимального связного доминирующего множества, которая достигает множителя 2 ln Δ + O (1) , где Δ - максимальная степень вершины в G. [4] Задача максимального листового остовного дерева сложна с помощью MAX-SNP. , подразумевая, что никакая схема аппроксимации полиномиального времени не вероятна. [5] Однако его можно аппроксимировать с точностью до коэффициента 2 за полиномиальное время. [6]

Обе задачи могут быть решены на графах с n вершинами за время O (1,9 n ) . [7] Задача о максимальном листе решаема с фиксированными параметрами , что означает, что она может быть решена во времени, экспоненциально по количеству листьев, но только полиномиально по размеру входного графа. Значение клама этих алгоритмов (интуитивно понятно , что количество этапов, до которых проблема может быть решена за разумный промежуток времени) постепенно увеличивалось по мере улучшения алгоритмов решения проблемы примерно до 37, [8] и Было высказано предположение, что должно быть достигнуто не менее 50. [9]

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

Приложения [ править ]

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

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

См. Также [ править ]

  • Универсальная вершина , вершина, которая (если она существует) дает минимальное связное доминирующее множество размера один.

Ссылки [ править ]

  1. ^ Sampathkumar, E .; Валикар, HB (1979), "Связное число доминирования графа", J. Math. Phys. Sci. , 13 (6): 607–613..
  2. ^ a b Товарищи, Майкл; Локштанов Даниил; Мишра, Нилдхара; Мних, Матиас; Розамонд, Фрэнсис; Саураая, Сакет (2009), "Сложность экология параметров: иллюстрация используя ограниченного максимального числа листьев", Теория вычислительных систем , 45 (4): 822-848, DOI : 10.1007 / s00224-009-9167-9.
  3. ^ Дуглас, Роберт Дж. (1992), «NP-полнота и остовные деревья с ограничением степени», Дискретная математика , 105 (1–3): 41–47, DOI : 10.1016 / 0012-365X (92) 90130-8.
  4. ^ Гуха, S .; Khuller, С. (1998), "Приближенные алгоритмы для множеств , связанных доминирующих", Algorithmica , 20 (4): 374-387, DOI : 10.1007 / PL00009201 , ЛВП : 1903/830.
  5. ^ Galbiati, G .; Maffioli, F .; Морзенти, А. (1994), "Краткое примечание об аппроксимируемости задачи о максимальном остовном дереве листьев", Информационные письма , 52 (1): 45–49, DOI : 10.1016 / 0020-0190 (94) 90139-2.
  6. ^ Солис-Оба, Роберто (1998), «2-приближенный алгоритм для поиска остовного дерева с максимальным числом листьев», Proc. Шестой Европейский симпозиум по алгоритмам (ESA'98) , Lecture Notes в области компьютерных наук, 1461 , Springer-Verlag, стр 441-452,. Дои : 10.1007 / 3-540-68530-8_37 , ЛВП : 11858 / 00-001M-0000 -0014-7BD6-0.
  7. ^ Фернау, Хеннинг; Кнейс, Иоахим; Крач, Дитер; Лангер, Александр; Лидлофф, Матье; Райбл, Дэниел; Rossmanith, Питер (2011), "Точный алгоритм максимального листа остовном дерева", Теоретическая информатика , 412 (45): 6290-6302, DOI : 10.1016 / j.tcs.2011.07.011 , MR 2883043 .
  8. ^ Бинкеле-Райбл, Даниэль; Фернау, Хеннинг (2014), «Параметризованный анализ меры и преодоления для поиска остовного дерева с k- листом в неориентированном графе», Дискретная математика и теоретическая информатика , 16 (1): 179–200, MR 3188035 .
  9. ^ Товарищи, Майкл Р .; Маккартин, Кэтрин; Розамонд, Фрэнсис А .; Стеге, Ульрике (2000), «Координированные ядра и каталитическое восстановление: улучшенный алгоритм FPT для максимального листового покрывающего дерева и других проблем», FST-TCS 2000: Основы программных технологий и теоретической информатики , Лекционные заметки в вычислительной технике . Sci . , 1974 ., Springer, Berlin, С. 240-251, DOI : 10.1007 / 3-540-44450-5_19 , MR 1850108 .
  10. ^ Уэно, Шуичи; Кадзитани, Йоджи; Гото, Шинья (1988), "О неразрывной задаче о независимом множестве и задаче о множестве обратной связи для графов, у которых степень вершин не превышает трех", Труды Первой японской конференции по теории графов и приложениям (Хаконэ, 1986), Дискретная математика , 72 (1–3): 355–360, DOI : 10.1016 / 0012-365X (88) 90226-9 , MR 0975556 
  11. ^ Wu, J .; Ли, Х. (1999), «О вычислении связного доминирующего множества для эффективной маршрутизации в специальных беспроводных сетях», Труды 3-го Международного семинара по дискретным алгоритмам и методам для мобильных вычислений и коммуникаций , ACM, стр. 7–14, doi : 10.1145 / 313239.313261.