O wykresach, których zestaw krawędzi rozkłada się w idealne dopasowania

9

Czy istnieje charakterystyka wykresów, których zestaw krawędzi rozkłada się w rozłączny związek idealnych dopasowań?


Jedną trywialną klasą takich grafów są d-nieregularne -obustronne wykresy. Ich zestaw krawędzi rozpadnie się na rozłączne idealne dopasowania. (n,n)re

użytkownik6818
źródło

Odpowiedzi:

6

Tak: nazywamy takie wykresy 1-czynnikowym (1-czynnik jest również znany jako idealne dopasowanie). Wszystkie takie wykresy są regularne, ale odwrotność nie jest prawdziwa. W rzeczywistości are-regularny wykres sol jest 1-czynnikowy tylko wtedy, gdy jest pierwszej klasy, to znaczy χ(sol)=re, gdzie χ(sol) jest indeksem chromatycznym sol.

Decydowanie, czy re- nieregularny wykres klasy 1 jest NP-kompletny (patrz np. [1]), więc prawdopodobnie nie można tego skutecznie przetestować.


[1] Leven, Daniel i Zvi Galil. „Kompletność NP znalezienia wskaźnika chromatycznego zwykłych wykresów”. Journal of Algorithms 4.1 (1983): 35-44.

Juho
źródło
Dziękuję za odpowiedź! (1) Czy masz referencje na potwierdzenie kompletności NP? (2) Wydaje się, że istnieją również inne klasy? Jakieś odniesienia pedagogiczne? (3) Czy wiesz, czy wiadomo coś specjalnego na temat idealnego pasującego polytopu takich 1-czynnikowych wykresów?
user6818,
Nie, to jest charakterystyka. Oznacza to, że nie ma innych klas grafów. Klasa grafów 1-czynnikowych jest dokładnie klasąre-Kolorowy re-regularne wykresy. Nie sądzę, żebym wiedział coś lepszego niż to, co oferuje Wikipedia, patrz na przykład tutaj .
Juho,