Теорема Петерсена

Ідеальне парування (червоні ребра), в графі Петерсена. Оскільки граф Петерсена кубічний і в ньому відсутні мости, він задовольняє умовам теореми Петерсона.

Кубічний (але з мостами) граф з неідеальною відповідністю, демонструє, що умова відсутності мостів в теоремі Петерсена є необхідною.

У математичній дисципліні теорії графів, теорема Петерсена, названа на честь Юліуса Петерсена, є одним з найбільш ранніх результатів в теорії графів і може бути сформульована таким чином:

Теорема Петерсена. Кожен кубічний граф, який не містить мостів має ідеальне парування.

Іншими словами, якщо граф має рівно три ребра в кожній вершині, і кожне ребро належить до циклу, то він має набір ребер, який торкається кожної вершини рівно один раз.

Доведення

Ми показуємо, що для кожного кубічного графу який не містить мостів Шаблон:Math ми маємо, що для кожного набору Шаблон:Math кількість компонентів зв'язності в графі, індукованість Шаблон:Math з непарним числом вершин, не перевищує потужності Шаблон:Math. Тоді як згідно з теоремою Татта Шаблон:Math містить ідеальну відповідність.

Нехай Шаблон:Math буде компонентом з непарним числом вершин в графі, який індукований набором вершин Шаблон:Math. Нехай Шаблон:Math позначає вершини Шаблон:Math і нехай Шаблон:Math позначає кількість ребер Шаблон:Math з одною вершиною в Шаблон:Math та одною в Шаблон:Math. Простим подвійним підрахунком аргументів, маємо, що

$\sum _{v\in V_i}{\mathrm{deg}}_G(v)=2|E_i|+m_i,$

де Шаблон:Math — набір ребер Шаблон:Math з обома вершинами в Шаблон:Math. З огляду на те, що

$\sum _{v\in V_i}{\mathrm{deg}}_G(v)=3|V_i|$

є непарним числом, і Шаблон:Math — парне число, отже, Шаблон:Math повинно бути непарним числом. Більш того, так як Шаблон:Math не містить мостів, то Шаблон:Math.

Нехай Шаблон:Math буде кількістю ребер у Шаблон:Math з одною вершиною у Шаблон:Math та одною вершиною в графі, який індукований Шаблон:Math. Кожен компонент з непарним числом вершин вносить, принаймні 3 ребра до Шаблон:Math, і вони є унікальними, отже, число таких компонентів становить не більше Шаблон:Math. У гіршому випадку, кожне ребро з однією вершиною в Шаблон:Math входить до Шаблон:Math, і таким чином Шаблон:Math. Ми отримуємо

$|U|\ge \frac{1}{3}m\ge |\{\text{компоненти з непарною кількістю вершин}\}|,$

що показує, що умова теореми Татта зберігається.

Історія

Теорема належить Юліусу Петерсену, данському математику. Її можна розглядати як один з перших результатів в теорії графів. Теорема з'являється вперше в 1891 році у статті «Die Theorie der regulären graphs». За сьогоднішніми мірками доказ Петерсена цієї теореми складний. Ряд спрощень його доказу завершилися в доказах Шаблон:Harvtxt та Шаблон:Harvtxt.

У сучасних підручниках теорема Петерсена розглядається як додаток до теореми Татта.

Додатки

• У кубічному графі з ідеальним паруванням, ребра, які не є в ідеальному паруванні утворюють 2-фактор. При орієнтуванні 2-фактору, ребра з ідеальним паруванням можуть бути розширені до шляху довжини три, скажімо, приймаючи зовнішньо-орієнтовані ребра. Це показує, що кожен кубічний граф, який не містить мостів, розпадається на крайові непересічні шляхи довжини три.
• Теорема Петерсена також може бути застосована, щоб показати, що кожен планарний граф можна розкласти на безліч крайових непересічних шляхів довжини три. В цьому випадку, двоїстий граф є кубічним і не містить мостів, тому по теоремі Петерсена він має відповідність, що відповідає до спаровування суміжних граней трикутника в вихідному графі . Кожна пара трикутників дає шлях довжини три, який містить ребро, яке з'єднує трикутники разом з двома із чотирьох лишившихся ребер.
• Застосовуючи теорему Петерсена до двоїстого графу сітки з трикутників і з'єднуючи пари трикутників, що не поєднані, можна розкласти сітку в циклічну Шаблон:Не перекладено. З деяких подальших перетворень вона може бути перетворена в одну смугу, і, отже, дає спосіб для перетворення сітки з трикутників таким чином, що його двоїстий граф стає гамільтоновим шляхом.

Розширення

Кількість ідеальних парувань в кубічному графі, який не містить мостів

Ласло Ловасом і Шаблон:Не перекладено було висловлено припущення, що кількість ідеальних парувань, які містяться в кубічному графі без мостів — єекспоненціальною щодо кількості вершин графу Шаблон:Math. Гіпотеза була вперше доведена для двочасткового, кубічного графу, що не містить мостів Шаблон:Harvtxt, пізніше для планарного, кубічного графу, що не містить мостів Шаблон:Harvtxt. Загальний випадок був вирішений Шаблон:Harvtxt, коли було показано, що кожен кубічний граф, що не містить мостів, містить принаймні $2^{n/3656}$ ідеальних парувань.

Алгоритмічна версія

Шаблон:Harvtxt обговорює ефективні варіанти теореми Петерсена. На підставі доведення Фрінка вони отримують Шаблон:Math алгоритм для обчислення ідеальних парувань в кубічному графі, що не містить мостів з Шаблон:Math вершинами. Якщо граф, ще і планарний, то та ж стаття приводить алгоритм, який має швидкість Шаблон:Math. Їх час оцінки Шаблон:Math, може бути покращено на основі наступних удосконалень часу для підтримки набору мостів в динамічному графі.Шаблон:Sfnp Подальше скорочення часу до Шаблон:Math або (з додатковими випадковими структурами даних) до Шаблон:Math, було отримане Шаблон:Harvtxt.

Вищий ступінь

Якщо G є регулярним графом ступеня d, чия реберна зв'язність принаймні d − 1, та G має парне число вершин, то він має ідеальне парування. Більш того, кожне ребро G належить, що найменш, до одного ідеального парування. Умова на число вершин може бути опущена з цього результату, коли ступінь непарний, тому, що в цьому випадку (згідно з лемою про рукостискання) число вершин завжди парне.

Посилання

• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation.
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation