Нові інваріанти встановлення ізоморфізму графів

2008;
: ст. 90 – 93
Authors: 

Білаль Раді А’Ґґель Аль-Забі, Керницький А. Б., Лобур М. В., Ткаченко С. П.

Національний університет «Львівська політехніка», кафедра систем автоматизованого проектування

Розглянуто питання встановлення ізоморфізму графів на основі побудови і дослідження бінарних дерев їхньої редукції.

1. Татт У. Теория графов. – М.: Мир, 1988. – 424 с. 2. Berge C. Isomorphism problems for hypergraphs // Mathematical centre tracts. – 1974. – 56. – Р. 3–12. 3. Corneil D.B., Gotlieb C.C. An efficient algorithm for Graph isomorphism // J. of A.C.M. – 1970. – Vol. 17, No. 1. Р. 51–74. 4. Курейчик В.М., Королев А.Г. Об одном алгоритме распознавания изоморфных ориентированных графов. – В кн.: Однородные цифровые вычислительные и интегрирующие структуры, VI, Таганрог, ТРТИ, 1976. – С. 94–102. 5. Харари Ф. Теория графов. – М.: Мир, 1973. – 302 с. 6. Земляченко В.Н., Корниенко Н.М., Тышкевич Р.И. Проблема изоморфизма графов // Теория сложности вычислений, I. Записки научных семинаров ЛОМИ. – 1982. – Т. 118. – С. 83–158. 7. Кани К., Оцуки Т. Применение теории графов и комбинаторных алгоритмов в автоматизации проектирования // Дзехо сери. – 1975. – Т. 16, № 17. – С. 581–590. (яп.) 8. Proskurowski A. Automatic generation of graphs and graphs identification problem // Technical Report. – april 1974. – N 16. 9. McCarthy M.K., Davida G.J. Invariant features and the graph isomorphism problem // IEEE Syst. Man and Cybern. Soc. Proc. Int. Conf. Cybern and Soc. – Boston, Mass., 1973. – Р. 81–85. 10. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 476 с. 11. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981. – 368 с. 12. A’Ggel B.R. Al-Zabi, Kernytskyy A., Lobur M., Tkachenko S. On Graph Isomorphism Determining Problem // IEEE MEMSTECH’2008. – Polyana, 2008. – Р. 84. 13. Базилевич Р.П., Ткаченко С.П. Решение задачи разбиения методом параллельного свертывания: В кн.: Вычислительная техника, VI. – Каунас: КПИ, 1975. – С. 295–298. 14. Аль-Забі Б., Керницький А.Б., Ткаченко С.П. Встановлення існування необхідних умов еквівалентності схем // Вісн. Нац. ун-ту “Львівська політехніка”. – 2007. – № 591: Комп’ютерні системи проектування. Теорія і практика. – С. 87–90.