Соответствие преклюзии - Matching preclusion

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

Во многих графиках mp (грамм) равна минимуму степень любой вершины в графе, потому что удаление всех ребер, инцидентных одной вершине, предотвращает ее сопоставление. Этот набор ребер называется тривиальным набором преклюзий для согласования.[2] Вариант определения, номер преклонения условного соответствия, запрашивает минимальное количество ребер, удаление которых приводит к графу, не имеющему ни идеального или почти идеального соответствия, ни каких-либо изолированных вершин.[3][4]

это НП-полный чтобы проверить, находится ли совпадающее число преклюзии данного графика ниже заданного порога.[5]

Число преклюзии со строгим соответствием (или просто номер SMP) является обобщением числа преклюзии совпадения; номер SMP графа грамм, smp (грамм) - минимальное количество вершин и / или ребер, удаление которых приводит к графу, не имеющему ни совершенного, ни почти идеального совпадения.[6]

Другие числа, определенные таким же образом путем удаления ребер в неориентированном графе, включают граничное соединение, минимальное количество ребер, которое нужно удалить, чтобы разъединить граф, и цикломатическое число, минимальное количество ребер для удаления, чтобы исключить все циклы.

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

  1. ^ Бригам, Роберт С.; Харари, Фрэнк; Скрипка, Elizabeth C .; Йеллен, Джей (2005), «Превращение с идеальным соответствием», Congressus Numerantium, Utilitas Mathematica Publishing, Inc., 174: 185–192.
  2. ^ а б Ченг, Эдди; Липтак, Ласло (2007), «Согласование запрета для некоторых сетей межсетевого взаимодействия», Сети, 50 (2): 173–180, Дои:10.1002 / нетто.20187.
  3. ^ Ченг, Эдди; Лесняк, Линда; Lipman, Marc J .; Lipták, László (2009), "Наборы преклюзий с условным соответствием", Информационные науки, 179 (8): 1092–1101, Дои:10.1016 / j.ins.2008.10.029.
  4. ^ Парк, Юнг-Хым; Сон, Сан Хёк (2009 г.), «Исключение условного соответствия для гиперкубоподобных сетей межсоединений», Теоретическая информатика, 410 (27–29): 2632–2640, Дои:10.1016 / j.tcs.2009.02.041.
  5. ^ Дорадо, Митре Коста; Майерлинг, Дирк; Penso, Lucia D .; Раутенбах, Дитер; Протти, Фабио; де Алмейда, Алин Рибейро (2015), «Надежные восстанавливаемые идеальные совпадения», Сети, 66 (3): 210–213, Дои:10.1002 / нетто.21624.
  6. ^ Мао, Япин; Ван, Чжао; Ченг, Эдди; Мелекян, Кристофер (2018), «Число графов с сильным совпадением с преклюзией», Теоретическая информатика, 713: 11–20, Дои:10.1016 / j.tcs.2017.12.035.