Що таке пружинна теорема Тутте?
Тутте (1963), стверджує, що це унікальне рішення завжди є вільним від перехрещень, і що більш сильно, що кожна грань результату
вкладення опукле. Її називають теоремою пружини, оскільки таке вкладення можна знайти як положення рівноваги для системи пружин, що представляють ребра графа.
Теорема Тутте Граф G = (V, E) має ідеальний збіг тоді і тільки тоді, коли для кожної підмножини U у V підграф G − U має щонайбільше |U| непарні компоненти (компоненти зв'язку, що мають непарну кількість вершин).
Теорема Тутте дає гарну характеристику графів, що містять ідеальні відповідності. Розглянемо простий неорієнтований граф G(V,E). Пароподібність на G — це непересічна підмножина ребер, тобто множина M ⊆ E така, що ніякі два ребра в M не мають спільної вершини. Паросочетание називається ідеальним, якщо воно охоплює всі вершини G.
Сильна теорема Ханані–Тутте стверджує, що граф можна намалювати без перетинів на S тоді і тільки тоді, коли його можна намалювати таким чином, щоб усі незалежні пари ребер перетиналися парну кількість разів без урахування кількості перетинів між ребра, які мають спільну кінцеву точку; ця сильна версія не діє для…
Теорема Ділворта стверджує, що у будь-якому скінченному частково впорядкованому наборі найбільший антиланцюг має той самий розмір, що й найменший розклад ланцюга. Тут розмір антиланцюга — це кількість його елементів, а розмір розкладання ланцюга — це кількість його ланцюгів.
Поліном Тутта, також званий дихроматом або поліномом Тутта–Уітні, є поліном графа. Це поліном від двох змінних, який відіграє важливу роль у теорії графів. Він визначений для кожного неорієнтованого графа та містить інформацію про зв’язок графа.