Перечислены связные 3-регулярные (кубические) простые графы с малым числом вершин.
Связность Число простых кубических графов с числом вершин 4, 6, 8, 10,… равно 1, 2, 5, 19,…. Классификация по 1- и 2-связности рёбер сделана, как обычно принято. Остальные кубические графы, вообще говоря, все трёхсвязны, поскольку удаление всех рёбер, смежных какой-либо вершине, приведёт к потере связности. Если использовать определение в свете алгебры (смотрите ниже), дополнительное подразделение 3-связных графов может быть полезным. Выделим следующие подклассы Нетривиально 3-связные графы могут быть разделены путём удаления 3 рёбер на два подграфа, каждый из которых содержит по меньшей мере две вершины. Циклически 4-связные — все оставшиеся, то есть не 1-связные, не 2-связные и не тривиально 3-связные. В таблице эти два случая обозначаются цифрами 3 и 4 в четвёртом столбце.
Рисунок Модели из шаров и стержней показывают граф в стиле изображений молекулярных связей. Комментарии к индивидуальным рисункам содержат обхват, диаметр, индекс Винера, и . Гамильтонов цикл (где существует) показан путём нумерации вершин, начиная с 1. (Положение вершин определено, исходя из евклидова и расстояния из теории графов, которые помещены в , а затем обработаны программой Jmol.)
LCF-нотация LCF-нотация — система обозначений, разработанная Ледербергом, Коксетером и Фрухтом для представления кубических графов, являющихся гамильтоновыми.
Рёбра цикла в нотацию не включаются. Поскольку граф кубический, в каждой вершине имеется смежное ребро, не принадлежащее циклу. Эти рёбра можно описать, указав, на сколько вершин удалена вторая вершина от первой (со знаком плюс по часовой стрелке и со знаком минус против часовой стрелки). Часто такое представление даёт повторяющиеся последовательности, в этом случае выписывают только такую последовательность, а количество последовательностей показывают индексом.
Пусть — вершины графа, и — гамильтонов цикл из вершин. Если фиксировать вершину , существует единственная вершина на расстоянии , связанная хордой с ,
Вектор из целых является удобным, хотя и не единственным, представлением гамильтонова кубического графа. Применяются два дополнительных правила: Если элемент , заменяем его на ; Избегаем повторения последовательности , если она периодична, и заменяем повторение степенью. Поскольку начальная вершина пути несущественна, числа в представлении можно циклически сдвигать. Если граф содержит различные гамильтоновы циклы, можно выбрать один из них для LCF-нотации. Один и тот же граф может иметь различные LCF-нотации, в зависимости от того, каким образом были выстроены вершины.
Часто антипалидромическое представление
предпочтительно (если таковое существует), и в этом случае вторая часть заменяется на «;-». LCF-нотация , например, может быть сокращена до .
Таблица
4 вершины диаметробхватАвтАвтоморфизмовсвязность LCF рисунок1 3 24 4 4
6 вершин диаметробхватАвтсвязность LCF рисунок23123 [2,3,-2]2 , граф призмы 24724 6
8 вершин диаметробхватАвтсвязность LCF рисунок3316 2 [2,2,-2,-2]2 3343 [4,-2,4,2]2 или [2,3,-2,3;-] 23123 [2,4,-2,3,3,4,-3,-3] 34484 [-3,-1,-1,-1,1,1,1,3] граф куба 24164 8 или [4,-3,3,4]2 Граф Вагнера
10 вершин диаметробхватАвтсвязность LCF рисунок53321 Список рёбер list 0-1,0-6,0-9,1-2,1-5,2-3,2-4,3-4, 3-5,4-5,6-7,6-8,7-8,7-9,8-9 4342 [4,2,3,-2,-4,-3,2,2,-2,-2] 3382 [2,-3,-2,2,2;-] 33162 [-2,-2,3,3,3;-] 43162 [2,2,-2,-2,5] 2 3323 [2,3,-2,5,-3] 2 [3,-2,4,-3,4,2,-4,-2,-4,2] 33123 [2,-4,-2,5,2,4,-2,4,5,-4] 3323 [5,3,5,-4,-3,5,2,5,-2,4] [-4,2,5,-2,4,4,4,5,-4,-4] [-3,2,4,-2,4,4,-4,3,-4,-4] 3343 [-4,3,3,5,-3,-3,4,2,5,-2] [3,-4,-3,-3,2,3,-2,4,-3,3] 3363 [3,-3,5,-3,2,4,-2,5,3,-4] 3343 [2,3,-2,3,-3;-] [-4,4,2,5,-2]2 3363 [5,-2,2,4,-2,5,2,-4,-2,2] 3383 [2,5,-2,5,5]2 [2,4,-2,3,4;-] 34483 [5,-3,-3,3,3]2 3484 [5,-4,4,-4,4]2 [5,-4,-3,3,4,5,-3,4,-4,3] 3444 [5,-4,4,5,5]2 [-3,4,-3,3,4;-] [4,-3,4,4,-4;-] [-4,3,5,5,-3,4,4,5,5,-4] 34204 10 [-3,3]5 [5,5,-3,5,3]2 34204 [-4,4,-3,5,3]2 251204 Граф Петерсена
12 вершин диаметробхватАвтсвязность LCF рисунок6 3 16 1 Список рёбер 0-1,0-2,0-11,1-2,1-6, 2-3,3-4,3-5,4-5,4-6, 5-6,7-8,7-9,7-11,8-9, 8-10,9-10,10-11 53161 Список рёбер 0-1,0-6,0-11,1-2,1-3, 2-3,2-5,3-4,4-5,4-6, 5-6,7-8,7-9,7-11, 8-9,8-10,9-10,10-11 6381 Список рёбер 0-1,0-3,0-11,1-2,1-6, 2-3,2-5,3-4,4-5,4-6, 5-6,7-8,7-9,7-11,8-9, 8-10,9-10,10-11 53321 Список рёбер 0-1,0-6,0-11,1-2,1-4, 2-3,2-5,3-4,3-6,4-5, 5-6,7-8,7-9,7-11,8-9, 8-10,9-10,10-11 5342 [3,-2,-4,-3,4,2]2 [4,2,3,-2,-4,-3;-] 4382 [3,-2,-4,-3,3,3,3,-3,-3,-3,4,2] 4342 [4,2,3,-2,-4,-3,2,3,-2,2,-3,-2] 44642 [3,3,3,-3,-3,-3]2 43162 [2,-3,-2,3,3,3;-] 43162 [2,3,-2,2,-3,-2]2 43 22 [-2,3,6,3,-3,2,-3,-2,6,2,2,-2] [4,2,-4,-2,-4,6,2,2,-2,-2,4,6] 4382 [6,3,3,4,-3,-3,6,-4,2,2,-2,-2] 5342 [4,2,3,-2,-4,-3,5,2,2,-2,-2,-5] 4 3 162 [-3,-3,-3,5,2,2;-] 4 3 82 [2,-3,-2,5,2,2;-] 4 3 42 [2,4,-2,3,-5,-4,-3,2,2,-2,-2,5] [5,2,-4,-2,-5,-5,2,2,-2,-2,4,5] 4 3 42 [-2,-2,4,4,4,4;-] [3,-4,-4,-3,2,2;-] [5,3,4,4,-3,-5,-4,-4,2,2,-2,-2] 4 3 22 [4,-2,4,2,-4,-2,-4,2,2,-2,-2,2] [5,-2,2,3,-2,-5,-3,2,2,-2,-2,2] 5 3 162 [2,2,-2,-2,-5,5]2 4 3 82 [-2,-2,4,5,3,4;-] 4 3 42 [5,2,-3,-2,6,-5,2,2,-2,-2,6,3] 4 3 82 [4,-2,3,3,-4,-3,-3,2,2,-2,-2,2] 4 3 82 [-2,-2,5,3,5,3;-] [-2,-2,3,5,3,-3;-] 5 3 322 [2,2,-2,-2,6,6]2 4 3 82 [-3,2,-3,-2,2,2;-] 4 3 82 [-2,-2,5,2,5,-2;-] 4 3 82 [6,-2,2,2,-2,-2,6,2,2,-2,-2,2] 4 3 482 [-2,-2,2,2]3 4 3 43 [2,3,-2,3,-3,3;-] [-4,6,4,2,6,-2]2 4 3 43 [-4,6,3,3,6,-3,-3,6,4,2,6,-2] [-2,3,-3,4,-3,3,3,-4,-3,-3,2,3] 4 3 13 [-5,2,-3,-2,6,4,2,5,-2,-4,6,3] [-2,3,-3,4,-3,4,2,-4,-2,-4,2,3] [3,-2,3,-3,5,-3,2,3,-2,-5,-3,2] 3 3 43 [-5,-5,4,2,6,-2,-4,5,5,2,6,-2] [4,-2,3,4,-4,-3,3,-4,2,-3,-2,2] 3 3 83 [-5,-5,3,3,6,-3,-3,5,5,2,6,-2] [2,4,-2,3,5,-4,-3,3,3,-5,-3,-3] 4 3 23 [2,4,-2,3,6,-4,-3,2,3,-2,6,-3] [2,4,-2,3,5,-4,-3,4,2,-5,-2,-4] [-5,2,-3,-2,5,5,2,5,-2,-5,-5,3] 4 3 23 [-5,2,-3,-2,6,3,3,5,-3,-3,6,3] [4,-2,-4,4,-4,3,3,-4,-3,-3,4,2] [-3,3,3,4,-3,-3,5,-4,2,3,-2,-5] 4 3 23 [2,3,-2,4,-3,6,3,-4,2,-3,-2,6] [-4,5,-4,2,3,-2,-5,-3,4,2,4,-2] 43 13 [6,3,-4,-4,-3,3,6,2,-3,-2,4,4] [-5,-4,4,2,6,-2,-4,5,3,4,6,-3] [3,4,4,-3,4,-4,-4,3,-4,2,-3,-2] [4,5,-4,-4,-4,3,-5,2,-3,-2,4,4] [4,5,-3,-5,-4,3,-5,2,-3,-2,5,3] 3 4 43 [4,6,-4,-4,-4,3,3,6,-3,-3,4,4] [-5,-4,3,3,6,-3,-3,5,3,4,6,-3] [4,-3,5,-4,-4,3,3,-5,-3,-3,3,4] 3 4 163 [3,3,4,-3,-3,4;-] [3,6,-3,-3,6,3]2 4 3 13 [4,-2,5,2,-4,-2,3,-5,2,-3,-2,2] [5,-2,2,4,-2,-5,3,-4,2,-3,-2,2] [2,-5,-2,-4,2,5,-2,2,5,-2,-5,4] Граф Фрухта 4 3 43 [-2,6,2,-4,-2,3,3,6,-3,-3,2,4] [-2,2,5,-2,-5,3,3,-5,-3,-3,2,5] 4 3 23 [2,4,-2,6,2,-4,-2,4,2,6,-2,-4] [2,5,-2,2,6,-2,-5,2,3,-2,6,-3] 4 32 3 [6,3,-3,-5,-3,3,6,2,-3,-2,5,3] [3,5,3,-3,4,-3,-5,3,-4,2,-3,-2] [-5,-3,4,2,5,-2,-4,5,3,-5,3,-3] 4 4 123 [3,-3,5,-3,-5,3,3,-5,-3,-3,3,5] 4 3 23 [4,2,4,-2,-4,4;-] [3,5,2,-3,-2,5;-] [6,2,-3,-2,6,3]2 4 3 23 [3,6,4,-3,6,3,-4,6,-3,2,6,-2] [4,-4,5,3,-4,6,-3,-5,2,4,-2,6] [-5,5,3,-5,4,-3,-5,5,-4,2,5,-2] 3 3 13 [6,-5,2,6,-2,6,6,3,5,6,-3,6] [6,2,-5,-2,4,6,6,3,-4,5,-3,6] [5,5,6,4,6,-5,-5,-4,6,2,6,-2] [-4,4,-3,3,6,-4,-3,2,4,-2,6,3] [6,2,-4,-2,4,4,6,4,-4,-4,4,-4] [-3,2,5,-2,-5,3,4,-5,-3,3,-4,5] [-5,2,-4,-2,4,4,5,5,-4,-4,4,-5] 3 3 23 [2,6,-2,5,6,4,5,6,-5,-4,6,-5] [5,6,-4,-4,5,-5,2,6,-2,-5,4,4] [2,4,-2,-5,4,-4,3,4,-4,-3,5,-4] [2,-5,-2,4,-5,4,4,-4,5,-4,-4,5] 4 3 43 [2,4,-2,-5,5]2 [-5,2,4,-2,6,3,-4,5,-3,2,6,-2] 4 3 23 [-4,-4,4,2,6,-2,-4,4,4,4,6,-4] [-4,-3,4,2,5,-2,-4,4,4,-5,3,-4] [-3,5,3,4,-5,-3,-5,-4,2,3,-2,5] 3 3 23 [2,5,-2,4,4,5;-] [2,4,-2,4,4,-4;-] [-5,5,6,2,6,-2] 2 [5,-2,4,6,3,-5,-4,-3,2,6,-2,2] 3 3 23 [3,6,-4,-3,5,6,2,6,-2,-5,4,6] [2,-5,-2,4,5,6,4,-4,5,-5,-4,6] [5,-4,4,-4,3,-5,-4,-3,2,4,-2,4] 4 3 23 [6,-5,2,4,-2,5,6,-4,5,2,-5,-2] [-2,4,5,6,-5,-4,2,-5,-2,6,2,5] [5,-2,4,-5,4,-5,-4,2,-4,-2,5,2] 4 3 13 [2,-5,-2,6,3,6,4,-3,5,6,-4,6] [6,3,-3,4,-3,4,6,-4,2,-4,-2,3] [5,-4,6,-4,2,-5,-2,3,6,4,-3,4] [5,-3,5,6,2,-5,-2,-5,3,6,3,-3] [-5,2,-5,-2,6,3,5,5,-3,5,6,-5] [-3,4,5,-5,-5,-4,2,-5,-2,3,5,5] [5,5,5,-5,4,-5,-5,-5,-4,2,5,-2] 3 3 23 [5,-3,6,3,-5,-5,-3,2,6,-2,3,5] [2,6,-2,-5,5,3,5,6,-3,-5,5,-5] [5,5,5,6,-5,-5,-5,-5,2,6,-2,5] [4,-3,5,2,-4,-2,3,-5,3,-3,3,-3] [5,5,-3,-5,4,-5,-5,2,-4,-2,5,3] 4 3 43 [2,4,-2,5,3,-4;-] [5,-3,2,5,-2,-5;-] [3,6,3,-3,6,-3,2,6,-2,2,6,-2] 4 3 23 [6,2,-4,-2,-5,3,6,2,-3,-2,4,5] [2,3,-2,4,-3,4,5,-4,2,-4,-2,-5] [-5,2,-4,-2,-5,4,2,5,-2,-4,4,5] 33 23 [5,2,5,-2,5,-5;-] [6,2,-4,-2,4,6]2 [2,-5,-2,6,2,6,-2,3,5,6,-3,6] [-5,-2,6,6,2,5,-2,5,6,6,-5,2] 3 3 123 [-5,3,3,5,-3,-3,4,5,-5,2,-4,-2] 33 23 [6,-4,3,4,-5,-3,6,-4,2,4,-2,5] [-4,6,-4,2,5,-2,5,6,4,-5,4,-5] [5,-5,4,-5,3,-5,-4,-3,5,2,5,-2] 4 312 3 [-4,5,2,-4,-2,5;-] Граф Дюрера 3 3 43 [2,5,-2,5,3,5;-] [6,-2,6,6,6,2]2 [5,-2,6,6,2,-5,-2,3,6,6,-3,2] 3 3 43 [6,-2,6,4,6,4,6,-4,6,-4,6,2] [5,6,-3,3,5,-5,-3,6,2,-5,-2,3] 3 3 43 [4,-2,4,6,-4,2,-4,-2,2,6,-2,2] [5,-2,5,6,2,-5,-2,-5,2,6,-2,2] 33 24 3 [6,-2,2]4 Усечённый тетраэдр 3 312 3 Граф Титце 3 336 3 [2,6,-2,6] 3 4 4 244 [-3,3]6 [3,-5,5,-3,-5,5] 2 , 3 44 4 [6,-3,6,6,3,6]2 [6,6,-5,5,6,6]2 [3,-3,4,-3,3,4;-] [5,-3,6,6,3,-5]2 [5,-3,-5,4,4,-5;-] [6,6,-3,-5,4,4,6,6,-4,-4,5,3] 3 4 8 4 [-4,4,4,6,6,-4]2 [6,-5,5,-5,5,6]2 [4,-3,3,5,-4,-3;-] [-4,-4,4,4,-5,5]2 3 4 24 [-4,6,3,6,6,-3,5,6,4,6,6,-5] [-5,4,6,6,6,-4,5,5,6,6,6,-5] [5,-3,4,6,3,-5,-4,-3,3,6,3,-3] [4,-4,6,4,-4,5,5,-4,6,4,-5,-5] [4,-5,-3,4,-4,5,3,-4,5,-3,-5,3] 34 2 4 [3,4,5,-3,5,-4;-] [3,6,-4,-3,4,6]2 [-4,5,5,-4,5,5;-] [3,6,-4,-3,4,4,5,6,-4,-4,4,-5] [4,-5,5,6,-4,5,5,-5,5,6,-5,-5] [4,-4,5,-4,-4,3,4,-5,-3,4,-4,4] 3 4 84 [4,-4,6]4 [3,6,3,-3,6,-3]2 [-3,6,4,-4,6,3,-4,6,-3,3,6,4] Бидиакис-куб 3 4 164 [6,-5,5]4 [3,4,-4,-3,4,-4] 2 3 4 24 [-3,5,-3,4,4,5;-] [4,-5,5,6,-4,6]2 [-3,4,-3,4,4,-4;-] [5,6,-3,-5,4,-5,3,6,-4,-3,5,3] [5,6,4,-5,5,-5,-4,6,3,-5,5,-3] 34 4 4 [4,-3,4,5,-4,4;-] [4,5,-5,5,-4,5;-] [-5,-3,4,5,-5,4;-] 3 4 24 [6,-4,6,-4,3,5,6,-3,6,4,-5,4] [6,-4,3,-4,4,-3,6,3,-4,4,-3,4] [5,6,-4,3,5,-5,-3,6,3,-5,4,-3] [5,-5,4,6,-5,-5,-4,3,5,6,-3,5] [5,5,-4,4,5,-5,-5,-4,3,-5,4,-3] 3 44 4 [6,-3,5,6,-5,3,6,-5,-3,6,3,5] [3,-4,5,-3,4,6,4,-5,-4,4,-4,6] 3 48 4 [5,6,6,-4,5,-5,4,6,6,-5,-4,4] 3 516 4 [4,-5,4,-5,-4,4;-] 3 4 44 [6,4,6,6,6,-4]2 [-3,4,-3,5,3,-4;-] [-5,3,6,6,-3,5,5,5,6,6,-5,-5] [-3,3,6,4,-3,5,5,-4,6,3,-5,-5] 4 4 8 4 [3,5,5,-3,5,5;-] [-3,5,-3,5,3,5;-] [5,-3,5,5,5,-5;-] 3 4 48 4 [5,-5,-3,3]3 [-5,5]6 Граф Франклина 3 424 4 12 [6,6,-3,-5,5,3]2 3 5 18 4 [6,-5,-4,4,-5,4,6,-4,5,-4,4,5]
Колонка LCF пуста, если у графа нет гамильтонова цикла, что наблюдается довольно редко (гипотеза Тэйта). В этом случае список рёбер между парами вершин с индексами от 0 до n-1 в третьем столбце используется как идентификатор.
Вектор коэффициентов взаимодействия Каждый 4-связный (в выше определённом смысле) простой кубический граф с 2n вершинами определяет класс квантовой механики 3n-j символов. Грубо говоря, каждая вершина представляет 3jm-символ, граф превращается в орграф путём назначения знаков моментам инерции квантовых чисел , вершины помечаются согласно направленности в дереве (дерево вершин) 3-jm символов, а граф представляет сумму произведений всех этих чисел, присвоенных вершинам.
Имеется 1 (6j), 1 (), 2 (12j), 5 (15j), 18 (18j), 84 (21j), 607 (24j), 6100 (27j), 78824 (30j), 1195280 (33j), 20297600 (36j), 376940415 (39j) и т. д. таких символов.
Если они эквивалентны некоторому порождённому вершинами бинарному дереву (вырезается одно ребро и находится сечение, которое разрезает граф на два дерева), они представляют коэффициенты вторичного взаимодействия, и тоже известны как графы Ютсиса.
Примечания
Ссылки
Категория:Граф (математика) Категория:Регулярные графы Категория:Семейства графов