У теорії графів досконале парування у графі — це парування, що охоплює кожну вершину графа. Формальніше, якщо дано граф з ребрами і вершинами , досконалим паруванням у є підмножина із , така, що кожна вершина з суміжна рівно з одним ребром із . Матриця суміжності точного парування — це симетрична матриця перестановки.
Досконале парування також називають 1-фактором; див. пояснення в статті Факторизація графів.
Кожне досконале парування є , але не навпаки. Наприклад, розглянемо такі графи:
У графі (b) спостерігається досконале парування (розміру 3), оскільки воно охоплює всі 6 вершин; у графах (a) та (c) спостерігається парування максимальної потужності (розміру 2), яке не є досконалим, оскільки деякі вершини не охоплено.
Досконале парування також є найменшим реберним покриттям. Якщо існує досконале парування, то і число парування, і число реберного покриття дорівнюють .
Досконале парування може виникнути лише тоді, коли граф має парну кількість вершин. Майже досконале парування — це парування, за якого рівно одна вершина не має пари. Воно можливе лише в графі, який має непарну кількість вершин, і таке парування має бути максимальним. На наведеному вище рисунку, частина (c) показує майже досконале парування. Якщо для кожної вершини графа існує майже досконале парування, в якому пропущено лише цю вершину, граф також називають .
Характеризація Теорема Холла про одруження дає характеризацію двочасткових графів, які мають досконале парування.
Теорема Татта про досконале парування дає характеризацію довільним графам.
Досконале парування — це кістяковий 1-регулярний підграф, також відомий як 1-фактор. Загалом, кістяковий k-регулярний підграф — це k-фактор.
Хассані Монфаред та Маллік надали спектральну характеризацію графа, щоб він мав досконале парування: Нехай — граф на парній кількості вершин та — різних ненульових чисто уявних чисел. Тоді має досконале парування тоді й лише тоді, коли існує дійсна кососиметрична матриця з графом та власні значення . Зауважте, що (простий) граф дійсної симетричної або кососиметричної матриці порядку має вершини та ребра, задані ненульовими позадіагональними елементами .
Обчислення Визначити, чи допускає граф досконале парування, можна за поліноміальний час, використовуючи будь-який алгоритм для знаходження .
Однак, задача підрахунку кількості досконалих парувань, навіть у двочасткових графах, є . Це пояснюється тим, що обчислення перманента довільної матриці 0–1 (ще одна #P-повна задача) це те саме, що й обчислення кількості досконалих парувань у двочастковому графі, для якого ця матриця є матрицею бісуміжності.
Теорема стверджує, що кількість досконалих парувань у планарному графі можна обчислити точно за поліноміальний час за допомогою .
Кількість досконалих парувань у повному графі Kn (де n парне) дорівнює подвійному факторіалу: .
Зв'язок із розфарбовуванням графів Граф із розфарбованими ребрами може індукувати кількість (не обов'язково правильних) розфарбувань вершин, що дорівнює кількості досконалих парувань, оскільки кожна вершина покривається рівно один раз у кожному паруванні. Ця властивість досліджувалася в квантовій фізиці та теорії обчислювальної складності.
Політоп досконалого парування Політоп досконалого парування графа — це політоп в R|E|, в якому кожен кут є вектором інцидентності досконалого парування.
Примітки