ОДИНИЧНІ ТА ІЗОМЕТРИЧНІ ЦИКЛИ У ГРАФІ
Ключові слова:
неорієнтований граф, граф з циклічними фрагментами, ізометричні цикли, одиничні цикли
Анотація
У роботі розглядаються властивості ізометричних циклів у графі. У статті представлений алгоритм виділення множини ізометричних циклів у графі. Для графів з циклічними фрагментами вводиться поняття одиничного циклу. Представлений алгоритм виділення множини одиничних циклів у графі з циклічними фрагментами. Розглянуто основні властивості одиничних циклів. Обчислювальна складність представлених алгоритмів визначається як O(m).
Посилання
1. Tamassia R. Handbook of Graph Drawing and Visualization. CRC Press, 2014. 866 p.
2. Herman I., Melançon G., Marshall M. S. Graph Visualization and Navigation in Information Visualization: A Survey. IEEE Transactions on Visualization and Computer Graphics. 2000. №6(1). P. 24–43. doi: 10.1109/2945.841119.
3. Курапов С. В., Давидовский М. В. Два подхода к проведению соединений в плоских конструктивах. Компоненты и технологии. 2015. № 7. C. 142–147.
4. Курапов С. В., Толок А. В. Методы построения топологического рисунка графа. Автоматика и телемеханика. 2013. № 9. C. 78–97.
5. Рингель Г. Теорема о раскраске карт. Москва: Мир, 1977. 126 с.
6. Зыков А. А. Теория конечных графов. Новосибирск: ГРФМЛ, 1963. 542 с.
7. Kavitha Т., Liebchen Ch., Mehlhorn K., Michail D., Rizzi R., Ueckerdt T., Zweig K. A. Cycle bases in graphs characterization, algorithms, complexity, and applications. Computer Science Review. 2009. Vol. 3, Iss. 4. P. 199–243.
8. Беллерт С., Возняцки Г. Анализ и синтез электрических цепей методом структурных чисел. Москва: Мир, 1972. 332 с.
2. Herman I., Melançon G., Marshall M. S. Graph Visualization and Navigation in Information Visualization: A Survey. IEEE Transactions on Visualization and Computer Graphics. 2000. №6(1). P. 24–43. doi: 10.1109/2945.841119.
3. Курапов С. В., Давидовский М. В. Два подхода к проведению соединений в плоских конструктивах. Компоненты и технологии. 2015. № 7. C. 142–147.
4. Курапов С. В., Толок А. В. Методы построения топологического рисунка графа. Автоматика и телемеханика. 2013. № 9. C. 78–97.
5. Рингель Г. Теорема о раскраске карт. Москва: Мир, 1977. 126 с.
6. Зыков А. А. Теория конечных графов. Новосибирск: ГРФМЛ, 1963. 542 с.
7. Kavitha Т., Liebchen Ch., Mehlhorn K., Michail D., Rizzi R., Ueckerdt T., Zweig K. A. Cycle bases in graphs characterization, algorithms, complexity, and applications. Computer Science Review. 2009. Vol. 3, Iss. 4. P. 199–243.
8. Беллерт С., Возняцки Г. Анализ и синтез электрических цепей методом структурных чисел. Москва: Мир, 1972. 332 с.
Опубліковано
2017-12-18
Як цитувати
Курапов, С. В., & Давидовський, М. В. (2017). ОДИНИЧНІ ТА ІЗОМЕТРИЧНІ ЦИКЛИ У ГРАФІ. Computer Science and Applied Mathematics, (2), 116-131. вилучено із http://journalsofznu.zp.ua/index.php/comp-science/article/view/1312
Розділ
Articles
ISSN 
