Оглавление
Обозначение LCF
-
Основы LCF-нотации
- LCF-нотация разработана для представления кубических графов с гамильтоновым циклом.
- Цикл включает две смежности для каждой вершины, а LCF-код указывает положение третьей смежности.
- Один граф может иметь несколько LCF-представлений, в зависимости от выбранного гамильтонова цикла и начальной вершины.
-
Описание LCF-кода
- В гамильтоновом графе вершины образуют цикл, каждая вершина имеет два ребра.
- Третье ребро от каждой вершины описывает положение по часовой или против часовой стрелки.
- Основная форма записи LCF – последовательность чисел позиций, начинающаяся с произвольной вершины.
- Числа в квадратных скобках интерпретируются по модулю количества вершин.
- Некоторые записи не отображаются, если они соответствуют циклу или множественной смежности.
-
Приложения LCF-кода
- LCF-код полезен для краткого описания гамильтоновых кубических графов.
- Некоторые программные пакеты используют LCF-код для создания графиков.
- LCF-код позволяет легко проверить, является ли граф двудольным.
-
Расширенная нотация LCF
- Кокстер, Фрухт и Пауэрс представили расширенную версию LCF-кода с “антипалиндромной” нотацией.
- В этой нотации вторая половина чисел между квадратными скобками заменяется точкой с запятой и тире, если она обратная первой половине.
- Пример графа Науру в расширенной нотации – [5, -9, 7; −]4.
Полный текст статьи: