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

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

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

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

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

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

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

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

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

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

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

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

Розширення

Кількість ідеальних парувань в кубічному графі, який не містить мостів Ласло Ловасом і було висловлено припущення, що кількість ідеальних парувань, які містяться в кубічному графі без мостів — єекспоненціальною щодо кількості вершин графу .. Гіпотеза була вперше доведена для двочасткового, кубічного графу, що не містить мостів , пізніше для планарного, кубічного графу, що не містить мостів . Загальний випадок був вирішений , коли було показано, що кожен кубічний граф, що не містить мостів, містить принаймні ідеальних парувань.

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

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

Замітки

Посилання

.