En teoría de grafos , una rama de las matemáticas, el número de exclusión de coincidencia de un gráfico G (denotado mp( G )) es el número mínimo de aristas cuya eliminación da como resultado la eliminación de todas las coincidencias perfectas o casi perfectas (coincidencias que cubren todas pero un vértice en un gráfico con un número impar de vértices). [1] La exclusión de coincidencia mide la robustez 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 muchos gráficos, mp( G ) es igual al grado mínimo de cualquier vértice en el gráfico, porque eliminar todos los bordes incidentes en un solo vértice evita que ese vértice coincida. Este conjunto de aristas se denomina conjunto de exclusión de coincidencia trivial. [2] Una definición 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 ningún vértice aislado. [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] [6]
El número de exclusión coincidente fuerte (o simplemente, el número SMP) es una generalización del número de exclusión coincidente; 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. [7]
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.