Соответствующее исключение
В теории графов , разделе математики, число исключения совпадений графа G (обозначается mp( G )) — это минимальное количество ребер, удаление которых приводит к устранению всех идеальных паросочетаний или почти идеальных паросочетаний (паросочетаний, охватывающих все но одна вершина в графе с нечетным числом вершин). [1] Прекращение сопоставления измеряет надежность графа как топологии сети связи для распределенных алгоритмов , которые требуют, чтобы каждый узел распределенной системы был сопоставлен с соседним партнерским узлом. [2]
Во многих графах mp( G ) равна минимальной степени любой вершины в графе, поскольку удаление всех ребер, инцидентных одной вершине, предотвращает сопоставление этой вершины. Этот набор ребер называется тривиальным набором исключений совмещения. [2] Вариант определения, число исключений условного соответствия , запрашивает минимальное количество ребер, удаление которых приводит к тому, что граф не имеет ни идеального или почти идеального соответствия, ни каких-либо изолированных вершин. [3] [4]
является NP-полной проверка того, находится ли число совпадающих исключений данного графа ниже заданного порога. [5] [6]
Число исключения строгого соответствия (или просто число SMP) является обобщением числа исключения совпадения; число SMP графа G , smp( G ) — это минимальное количество вершин и/или ребер, удаление которых приводит к тому, что граф не имеет ни совершенных, ни почти совершенных паросочетаний. [7]
Другие числа, определяемые аналогичным образом путем удаления ребер в неориентированном графе, включают связность ребер (минимальное количество ребер, которые нужно удалить, чтобы отключить граф), и цикломатическое число (минимальное количество ребер, которые нужно удалить, чтобы исключить все циклы.
Ссылки
[ редактировать ]- ^ Бригам, Роберт С.; Харари, Фрэнк ; Скрипка, Элизабет К.; Йеллен, Джей (2005), «Преключение идеального соответствия», Congressus Numerantium , 174 , Utilitas Mathematica Publishing, Inc.: 185–192 .
- ↑ Перейти обратно: Перейти обратно: а б Ченг, Эдди; Липтак, Ласло (2007), «Препятствие сопоставления для некоторых межсетевых сетей», Networks , 50 (2): 173–180, doi : 10.1002/net.20187 .
- ^ Ченг, Эдди; Лесняк, Линда; Липман, Марк Дж.; Липтак, Ласло (2009), «Множества исключений условного соответствия», Information Sciences , 179 (8): 1092–1101, doi : 10.1016/j.ins.2008.10.029 .
- ^ Пак, Юнг-Хым; Сон, Сан Хёк (2009), «Исключение условного соответствия для гиперкубоподобных взаимосвязанных сетей», Theoretical Computer Science , 410 (27–29): 2632–2640, doi : 10.1016/j.tcs.2009.02.041 .
- ^ Лакруа, Матье; Рида Махджуб, А.; Мартин, Себастьян; Пикуло, Кристоф (март 2012 г.). «О NP-полноте проблемы идеального соответствия свободного подграфа». Теоретическая информатика . 423 : 25–29. дои : 10.1016/j.tcs.2011.12.065 .
- ^ Дурадо, Митре Коста; Мейерлинг, Дирк; Я думаю, Люсия Д.; Раутенбах, Дитер; Протти, Фабио; де Алмейда, Алин Рибейро (2015), «Надежные восстанавливаемые идеальные паросочетания», Networks , 66 (3): 210–213, doi : 10.1002/net.21624 .
- ^ Мао, Япин; Ван, Чжао; Ченг, Эдди; Мелекян, Кристофер (2018), «Число исключения строгого соответствия графов», Theoretical Computer Science , 713 : 11–20, doi : 10.1016/j.tcs.2017.12.035 .
 | Эта теории графов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |