график Харриса

В теории графов граф Харриса определяется как эйлеров , жёсткий , негамильтонов граф . ^{[1] [2]} Графы Харриса были введены в 2013 году, когда в Мичиганском университете Харрис Спанджен предположил , что любой граф, который является одновременно жёстким и эйлеровым, является достаточно гамильтоновым. Однако Дуглас Шоу опроверг эту гипотезу , открыв контрпример с порядком 9 и размером 14. ^[1] В настоящее время известно 241 375 графов Харриса. ^{[2] [3]} Минимальный граф Харриса, граф Хиротаки, имеет порядок 7 и размер 12. ^{[1] [2]}

Графы Харриса могут быть построены путем добавления ракушек или прививки меньших графов Харриса , что позволяет создавать более крупные графы, сохраняя их свойства. Известные типы включают минимальный граф Хиротаки, граф Лопеса без ракушек и граф Шоу , каждый из которых демонстрирует уникальные структурные особенности в теории графов . Графы Харриса ценны для преподавания теории графов благодаря доступным методам их поиска и проверки. Они предлагают сбалансированную задачу, поощряя креативность, командную работу и решение проблем, поскольку студенты сотрудничают для поиска решений.

После того, как Харрис Спанджен высказал свою гипотезу в 2013 году, ^[4] Дуг Шоу вскоре обнаружил контрпример — граф Харриса. Джейна Фишман и Элизабет Петри нашли еще два графа Харриса в том же году. В течение следующих нескольких лет было обнаружено еще три графа Харриса, пока Хиротака Йонеда не обнаружил то, что считалось минимальным графом Харриса в 2018 году. ^[1]

В 2023 году Акшай Ананд реализовал средство проверки графов Харриса на Java . ^[5] В том же году было найдено 241 375 графов Харриса порядка 12 или меньше, и граф Хиротаки был признан уникальным с помощью кода, написанного Шубхрой Мишрой и Марко Тропером. ^[2] Количество графов Харриса с n вершинами также было преобразовано в последовательность OEIS . ^[3]

k-ракушка — это путь длиной k между двумя узлами , где каждый узел на пути имеет степень 2. Цветение — это процесс добавления 2-ракушки между двумя узлами на кратчайшем пути между двумя узлами нечетной степени.

Цветение жесткого , негамильтонова графа , имеющего четное число узлов с нечетными степенями, дает граф Харриса. ^[2] Добавление 2-ракушки к графу сохраняет его жесткость, но при этом затрудняет его гамильтоновость. Кроме того, поскольку граф не может иметь нечетного числа вершин с нечетными степенями, процесс цветения может преобразовать любой негамильтонов, жесткий граф в эйлеров .

5- колесо добавляется между одним ребром в одном графе Харриса и другим ребром в другом графе Харриса, и два узла из каждого 5-колеса соединяются друг с другом, которые не были соединены с исходным графом. Поскольку добавление соединений и 5-колеса не делает граф гамильтоновым, неэйлеровым или нежестким, если он уже удовлетворяет этим условиям, результатом будет один граф Харриса. ^[2]

Замена ребра из существующего графа Харриса на 2-ракушку создает граф Харриса, поскольку все старые степени будут сохранены, в то время как ракушка имеет степень 2 по определению, поэтому граф по-прежнему является эйлеровым. Поскольку теперь графу стало еще сложнее быть гамильтоновым, и поскольку жесткость графа осталась прежней, добавление ракушки в любом месте сохраняет граф эйлеровым, жестким и негамильтоновым. ^[2]

Граф Хиротаки с 7 и размером 12 является графом Харриса с наименьшим порядком. ^{[1] [2]} Дуглас Шоу доказал, что он минимален, показав, что все эйлеровы графы порядка 6 или ниже не являются гамильтоновыми и жесткими. Код Java, написанный Шубхрой Мишрой и Марко Тропером, доказал его уникальность. ^[2]

Первым открытым графом Харриса был граф Шоу, имеющий порядок 9 и размер 14. ^{[1] [2] [4]} Этот граф послужил контрпримером к гипотезе Харриса Спанджена 2013 года.

Минимальный граф Харриса без ракушек, или граф Лопеса, имеет порядок 13 и размер 33. Он был построен для проверки гипотезы о том, что графов Харриса без ракушек не существует. ^[2]

Графы Харриса особенно ценны в преподавании теории графов, поскольку они обладают легко понимаемыми свойствами и методами их поиска и проверки. ^{[1] [2]} Они предлагают идеальный баланс между сложностью и доступностью, что делает их увлекательной задачей для студентов разного уровня. ^[4]

Работа с графиками Харриса побуждает студентов экспериментировать с различными концепциями и решениями, способствуя развитию креативности и математического мышления. Этот процесс поддерживает вовлеченность студентов и их сотрудничество друг с другом, поскольку они часто работают вместе, чтобы проверить потенциальные решения, улучшая навыки командной работы и коллективного решения проблем. ^[4]