Пролог
Существует классическая задача:
Каждый гость на встрече обменивается рукопожатием с другим. Всего было 78 рукопожатий. Сколько гостей пришло на встречу?
Эта задача представляет интерес только лишь потому, что её нынче задают при трудоустройстве на работу. Поэтому надо уметь её решить и главное доходчиво объяснить решение.
Определения
Для начала микро ликбез.
Граф - множество вершин и рёбер (палочки и кружочки).
Неориентированный графЧитать полностью »
8 января трое математиков опубликовали доказательство теоремы из комбинаторики, сформулированной почти 60 лет назад, известной, как гипотеза Рингеля. Грубо говоря, она предсказывает, что графы – конструкции, состоящие из точек и линий – можно идеально сложить из одинаковых частей меньшего размера.
Математики с восторгом приняли подтверждение этой гипотезы.
«Счастье в том, что эта работа решает очень старую гипотезу, которую невозможно было проверить другими методами», — сказал Гил Калай, математик из Еврейского университета в Иерусалиме, не связанный с этой работой.
Гипотеза Рингеля предсказывает, что особые типы сложных графов – с триллионами вершин и рёбер – можно «замостить», т.е. полностью покрыть, отдельными копиями меньших графов определённого типа. С концептуальной точки зрения этот вопрос похож на следующий: могу ли я полностью замостить пол на кухне одинаковыми копиями какой-либо плитки, имеющейся в магазине? В реальной жизни большинство типов плитки не подойдёт для вашей кухни – чтобы полностью покрыть пол, придётся комбинировать их разные формы. Но в мире теории графов гипотеза предсказывает, что замостить граф можно всегда.
Читать полностью »
