Dopasowanie wykluczenia

W teorii grafów , gałęzi matematyki, liczba prekluzji dopasowania grafu G (oznaczana jako mp( G )) to minimalna liczba krawędzi, których usunięcie skutkuje zniszczeniem idealnego dopasowania lub prawie idealnego dopasowania (dopasowanie, które obejmuje wszystkie oprócz jednego wierzchołka w grafie o nieparzystej liczbie wierzchołków). Wykluczenie dopasowania mierzy solidność grafu jako sieci komunikacyjnej dla algorytmów rozproszonych które wymagają, aby każdy węzeł systemu rozproszonego był dopasowany do sąsiedniego węzła partnerskiego.

W wielu grafach mp( G ) jest równe minimalnemu stopniowi dowolnego wierzchołka w grafie, ponieważ usunięcie wszystkich krawędzi przylegających do pojedynczego wierzchołka uniemożliwia jego dopasowanie. Ten zestaw krawędzi nazywany jest trywialnym zbiorem prekluzji pasujących. Definicja wariantu, numer prekluzji dopasowania warunkowego , wymaga minimalnej liczby krawędzi, których usunięcie skutkuje grafem, który nie ma ani idealnego lub prawie idealnego dopasowania, ani żadnych izolowanych wierzchołków.

Sprawdzanie, czy pasujący numer wykluczenia danego wykresu jest poniżej zadanego progu, jest NP-zupełne .

Mocno dopasowany numer wykluczenia (lub po prostu numer SMP) jest uogólnieniem pasującego numeru wykluczenia; liczba SMP grafu G , smp( G ) to minimalna liczba wierzchołków i/lub krawędzi, których usunięcie skutkuje grafem, który nie ma ani idealnych, ani prawie idealnych dopasowań.

Inne liczby zdefiniowane w podobny sposób przez usuwanie krawędzi w grafie nieskierowanym obejmują łączność krawędzi , minimalną liczbę krawędzi do usunięcia w celu odłączenia grafu oraz liczbę cyklomatyczną , minimalną liczbę krawędzi do usunięcia w celu wyeliminowania wszystkich cykle.