Теорема Дирака за обеденным столом: как картофель доказывает гамильтонов цикл

Dirac's Theorem at a Dinner Party

Теорема Дирака за обеденным столом: как картофель доказывает гамильтонов цикл

Габриэль Дирак сформулировал теорему: если в графе с n вершинами каждая вершина смежна хотя бы с n/2 другими, то граф содержит гамильтонов цикл. Автор пересказывает остроумное доказательство через метафору званого ужина: гости — вершины, дружба — рёбра, а рассадка за круглым столом — искомый цикл. Алгоритм «музыкальных стульев» переворачивает отрезки, закрывая разрывы между незнакомцами, а мысленный эксперимент с красной и золотой картошкой доказывает, что каждый разрыв имеет соответствующее пересечение. В конце упоминается гипотеза Барнетта.

Если у каждого гостя не менее n/2 друзей, то для любых двух незнакомцев число друзей гарантирует пересечение, так что каждый разрыв можно закрыть.

Ещё за этот день

2026-11-22