ГлавнаяАрхивАльтернативные подходы к описанию классов изоморфных графов

Альтернативные подходы к описанию классов изоморфных графов | Прикладная дискретная математика. 2014. № 3 (25).

Предложен алгоритм естественной индексации для классов симметрии вершин и рёбер конечных графов. На основе этой индексации построено альтернативное описание для классов изоморфных графов. Продемонстрировано, что на классы изоморфных графов можно перенести такие классические понятия, как раскраски, подграфы, а также элементарные операции на графах.
  • Title Альтернативные подходы к описанию классов изоморфных графов
  • Headline Альтернативные подходы к описанию классов изоморфных графов
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3 (25)
  • Date:
  • DOI
Ключевые слова
инварианты графов, классы симметрии рёбер, классы симметрии вершин, изоморфизм графов
Авторы
Ссылки
Харари Ф. Теория графов. М.: КомКнига, 2006. 296 с.
Kobler J., Schoning U., and Toran J. The Graph Isomorphism Problem: its Structural Complexity. Berlin: Birkhauser, 1993. 160 p.
Harary F. A survey of the reconstruction conjecture // Graphs and Combinatorics. Lecture Notes in Mathematics. 1974. V. 406. P. 18-28.
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.
Katebi H., Sakallah K., and Markov I. L. Graph symmetry detection and canonical labelling: differences and synergies // Proc. Turing-100, EPIC 2012. V. 10. P. 181-195.
Sparrow M. K. A linear algorithm for computing automorphic equivalence classes: the numerical signatures approach // Social Networks. 1993. V. 15. P. 151-170.
Southwell R. Finding Symmetries in Graphs. Ph.D. thesis. University of York, UK, 2006. 109 p.
Кинг Р. Химические приложения топологии и теории графов. М.: Мир, 1987. 560 с.
Фларри Р. Группы симметрии. Теория и химические приложения. М.: Мир, 1983. 400 с.
Bonchev D. and Rouvray D. H. Chemical Graph Theory: Introduction and Fundamentals. N.Y.: Gordon and Breach science publishers, 1991. 300 p.
Darga P., Sakallah K., and Markov I. L. Faster symmetry discovery using sparsity of symmetries // Proc. 45st Design Automation Conference. N.Y.: ACM, 2008. P. 149-154.
Aloul F. A., Ramani A., Markov I. L., and Sakallah K. A. Solving difficult instances of Boolean satisfiability in the presence of symmetry // IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems. 2003. V.22. No. 9, P. 1117-1137.
Holmes M. R. Elementary Set Theory with a Universal Set. Louvain-la-Neuve: Academia, 1998. 241 p.
Зыков А. А. Основы теории графов. М.: Наука, 1987. 383с.
Diestel R. Graph Theory. 3rd edition. Heidelberg: Springer Verlag, 2005. 451 p.
Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. М.: Высшая школа, 1976. 391 с.
Альтернативные подходы к описанию классов изоморфных графов | Прикладная дискретная математика. 2014. № 3 (25).
Альтернативные подходы к описанию классов изоморфных графов | Прикладная дискретная математика. 2014. № 3 (25).