En la teoría de grafos , una rama de las matemáticas, el número de preclusión coincidente de un gráfico G (denotado mp ( G )) es el número mínimo de aristas cuya eliminación da como resultado la destrucción de una coincidencia perfecta o casi perfecta (una coincidencia que cubre todos menos un vértice en un gráfico con un número impar de vértices). [1] La exclusión de coincidencia mide la solidez de un gráfico como topología de red de comunicaciones para algoritmos distribuidos que requieren que cada nodo del sistema distribuido coincida con un nodo asociado vecino. [2]
En muchas gráficas, mp ( G ) es igual al grado mínimo de cualquier vértice en la gráfica, porque eliminar todos los bordes incidentes a un solo vértice evita que coincida. Este conjunto de aristas se denomina conjunto de exclusión de coincidencia trivial. [2] Una definición de variante, el número de exclusión de coincidencia condicional , solicita el número mínimo de aristas cuya eliminación da como resultado un gráfico que no tiene una coincidencia perfecta o casi perfecta ni vértices aislados. [3] [4]
Es NP-completo probar si el número de exclusión coincidente de un gráfico determinado está por debajo de un umbral determinado. [5]
El número de exclusión de coincidencia fuerte (o simplemente, el número SMP) es una generalización del número de exclusión de coincidencia; el número SMP de un gráfico G , smp ( G ) es el número mínimo de vértices y / o aristas cuya eliminación da como resultado un gráfico que no tiene coincidencias perfectas ni coincidencias casi perfectas. [6]
Otros números definidos de manera similar por eliminación de bordes en un gráfico no dirigido incluyen la conectividad de bordes , el número mínimo de bordes a eliminar para desconectar el gráfico, y el número ciclomático , el número mínimo de bordes a eliminar para eliminar todos. ciclos.
Referencias
- ^ Brigham, Robert C .; Harary, Frank ; Violín, Elizabeth C .; Yellen, Jay (2005), " Preclusión de coincidencia perfecta", Congressus Numerantium , Utilitas Mathematica Publishing, Inc., 174 : 185-192.
- ^ a b Cheng, Eddie; Lipták, László (2007), "Preclusión de coincidencia para algunas redes de interconexión", Redes , 50 (2): 173–180, doi : 10.1002 / net.20187.
- ^ Cheng, Eddie; Lesniak, Linda; Lipman, Marc J .; Lipták, László (2009), "Conjuntos de preclusión de coincidencia condicional", Ciencias de la información , 179 (8): 1092-1101, doi : 10.1016 / j.ins.2008.10.029.
- ^ Park, Jung-Heum; Son, Sang Hyuk (2009), "Preclusión de coincidencia condicional para redes de interconexión tipo hipercubo", Informática teórica , 410 (27-29): 2632-2640, doi : 10.1016 / j.tcs.2009.02.041.
- ^ Dourado, Mitre Costa; Meierling, Dirk; Penso, Lucia D .; Rautenbach, Dieter; Protti, Fabio; de Almeida, Aline Ribeiro (2015), "Combinaciones perfectas recuperables robustas", Networks , 66 (3): 210-213, doi : 10.1002 / net.21624.
- ^ Mao, Yaping; Wang, Zhao; Cheng, Eddie; Melekian, Christopher (2018), "Número de gráficos de exclusión de coincidencia fuerte", Informática teórica , 713 : 11-20, doi : 10.1016 / j.tcs.2017.12.035.