Презентация на тему Компьютерная генерация трехсвязных регулярных планарных графов без Гамильтонового контура

История вопроса 1

Ф.Харари → Тейта → каждый трехсвязный плоский граф содержит остовный простой цикл или ГК → справедливость гипотезы 4-х красок.
В дальнейшем Татт показал, что это неверно, т.е. указал трехсвязный, плоский граф с 46 вершинами, который не является гамильтоновым

Позднее был найден однородный кубический, трехсвязный, плоский граф с 42 вершинами [2].
В монографии Грюнбаума [3] приведен наименьший известный в настоящее время трехсвязный плоский граф с 38 вершинами, не имеющий ГК, который был открыт сразу тремя исследователями независимо друг от друга.

История вопроса 1

Постановка задачи

Следует предположить, что таких графов среди однородных степени 3 ( ) много. Как много и как их искать? А также поиску нового рекорда посвящена данная работа.
До настоящего времени все найденные графы представляли ручную работу отдельных исследователей. В настоящей работе изготавливается невод, которым будет просеяно все или почти все множество однородных графов и, надеемся, будут найдены требуемые объекты. Попробуем определиться, как глубоко озеро в которое нам необходимо будет закидывать наш невод.

История вопроса 2

Перечисление однородных графов
Однородные графы используются в проектировании вычислительных сетей, когда каждый компьютер сети соединен с равным числом компьютеров. Также используются в исследовании однородных вычислительных сред, в теле коммуникации и т.д.
Впервые полный набор из 19 графов , куда входит известный граф Петерсена был перечислен в 1900 году.

История вопроса 2

Дальнейшие перечисления , … были затруднены ростом числа таких графов.

Длительности генерации регулярных графов по М. Менергеру