Рассматривается линейная нотация - полный инвариант графов, который позиционируется как альтернатива для описания конечных графов. Данный инвариант строится с помощью алгоритма, близкого к алгоритму поиска канонических форм графов. Хранение линейной нотации в памяти вместо обычного графа позволяет проще решать две основные задачи: построение иллюстраций для графов и сравнение графов на изоморфизм. Для полученного описания дополнительно демонстрируется переносимость таких понятий теории графов, как раскраски и пути, непосредственно на линейные нотации.
Скачать электронную версию публикации
Загружен, раз: 288
- Title Об альтернативном способе задания конечных графов
- Headline Об альтернативном способе задания конечных графов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 3(29)
- Date:
- DOI
Ключевые слова
изоморфизм графов, классы автоморфизма вершин и рёбер, инварианты графов, graph isomorphism, automorphism classes of vertices and edges, graph invariantsАвторы
Ссылки
Назаров М. Н. Альтернативные подходы к описанию классов изоморфных графов // Прикладная дискретная математика. 2014. №3. С. 86-97.
Зыков А. А. Основы теории графов. М.: Вузовская книга, 2004. 664с.
Weininger D., Weininger A., and Weininger J. SMILES. 2. Algorithm for generation of unique SMILES notation // J. Chem. Inf. Comput. Sci. 1989. V.29. No. 2. P. 97-101.
Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. М.: Высшая школа, 1976. 391 с.
Brecher J. Graphical representation of stereochemical configuration // Pure Appl. Chem. 2006. V. 78. No. 2. P. 1897-1970.
Харари Ф. Теория графов. М.: КомКнига, 2006. 296с.
Harary F. and Palmer E. M. Graphical Enumeration. N.Y.: Academic Press, 1973. 240 p.
Zykov A. A. Hypergraphs // Russian Mathematical Surveys. 1974. V.29. P.89-154.
Об альтернативном способе задания конечных графов | Прикладная дискретная математика. 2015. № 3(29).
Скачать полнотекстовую версию
Загружен, раз: 1000