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

Original title: Dirac's Theorem at a Dinner Party

> Hacker News story 50602660 · language: ru · submitted 2026-11-22
> Web version: https://zeli.app/ru/story/50602660
> About this feed: https://zeli.app/llms.txt · Agent guide: https://zeli.app/skill.md

▲ 3 · by [prideout](<https://news.ycombinator.com/user?id=prideout>) · 💬 0
[original](<https://prideout.net/blog/dirac-dinner-party/>) · [HN discussion](<https://news.ycombinator.com/item?id=50602660>)

## Summary

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

## Key quote

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

---

## Cite

- Page: https://zeli.app/ru/story/50602660
- Date: 2026-11-22
- Source: prideout.net (https://prideout.net/blog/dirac-dinner-party/)
- Hacker News: https://news.ycombinator.com/item?id=50602660

## Other languages

- en: https://zeli.app/story/50602660 · markdown: https://zeli.app/story/50602660.md
- zh: https://zeli.app/zh/story/50602660 · markdown: https://zeli.app/zh/story/50602660.md
- ja: https://zeli.app/ja/story/50602660 · markdown: https://zeli.app/ja/story/50602660.md
- ko: https://zeli.app/ko/story/50602660 · markdown: https://zeli.app/ko/story/50602660.md
- de: https://zeli.app/de/story/50602660 · markdown: https://zeli.app/de/story/50602660.md
- es: https://zeli.app/es/story/50602660 · markdown: https://zeli.app/es/story/50602660.md
