Теорема Эрдёша — Галлаи (Mykjybg |j;~og — Igllgn)
Перейти к навигации
Перейти к поиску
Теорема Эрдёша — Галлаи (критерий Эрдёша — Галлаи) — утверждение в теории графов, задающее условие, при котором конечной последовательности натуральных чисел можно сопоставить степени вершин некоторого графа. Такие последовательности чисел называются графическими. Теорема доказана венгерскими математиками Палом Эрдёшем и Тибором Галлаи (венг. Gallai Tibor)[1] в 1960 году.
Формулировка
[править | править код]Для формулировки утверждения вводятся следующие определения:
- правильная последовательность — последовательность натуральных чисел длины , удовлетворяющая следующим условиям:
- ,
- — чётное число;
- графическая последовательность чисел — последовательность целых неотрицательных чисел такая, что существует граф, последовательность степеней вершин которого совпадает с ней.
Теорема утверждает, что правильная последовательность является графической тогда и только тогда, когда для каждого , , верно неравенство:
- .
Алгоритмизация
[править | править код]Построить граф по графической последовательности можно полиномиальным алгоритмом, который строится на основании критерия Гавела — Хакими[2].
Примечания
[править | править код]- ↑ Erdős, P.; Gallai, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF), Matematikai Lapok, 11: 264—274, Архивировано из оригинала (PDF) 20 января 2022, Дата обращения: 20 февраля 2013
- ↑ Hakimi, S. L. (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the Society for Industrial and Applied Mathematics, 10: 496—506, MR 0148049
Литература
[править | править код]- Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. — М.: Наука, 1990.
Для улучшения этой статьи желательно:
|