ІЗОМЕТРИЧНІ ЦИКЛИ ГРАФА
Ключові слова:
граф, базис циклів, фундаментальні цикли графа, ізометричні цикли
Анотація
У роботі для формування базисів підпростору циклів простору суграфів графа вводяться поняття ізометричних циклів на відміну від фундаментальних циклів графа. Розглядаються основні властивості нововведеної структури. Представлена теорема про існування в простому несепарабельному графі базису підпростору циклів, який складається з ізометричних циклів. А також, розглянуто питання про представлення границь граней у плоскому графі ізометричними циклами.
Посилання
1. Мак-Лейн С. Комбинаторное условие для плоских графов / С. Мак-Лейн // В кн. : Кибернетический сборник. Новая серия. – 1970. – Вып. 7. – С. 68-77.
2. Емеличев В. А. Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. – М. : Наука, 1990. – 384 с.
3. Kolasinska E. On a Minimum Cycle Bases of a Graph / E. Kolasinska // Zastosowania Matematyki. – 1980. – Р. 631-639.
4. Зыков А. А. Основы теории графов / А. А. Зыков. – М. : Наука, 1987. – 384 с.
5. Kavitha T. Cycle spaces in graphs: characterization, algorithms, complexity, and applications / T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt, K. Zweig // Comput. Sci. Rev. 3. – 2009. – P. 199-243.
6. Харари Ф. Теория графов / [Пер. с англ. Козырева В.П. под ред. Гаврилова В.Г.]. – М. : Мир, 1973. – 300 с.
7. Курапов С. В. Методы построения топологического рисунка графа / С. В. Курапов, А. В. Толок // Автоматика и телемеханика. – 2013. – № 9. – С. 78-97.
8. Хопкрофт Дж. Е. Изоморфизм планарных графов / Дж. Е. Хопкрофт, Р. Е. Тарьян // В кн. : Кибернетический сборник. Новая серия. – 1975. – Вып. 12. – С. 39-61.
9. Свами М. Графы, сети и алгоритмы : Пер. с англ. / М. Свами, К. Тхуласираман. – М. : Мир, 1984. – 455 с.
2. Емеличев В. А. Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. – М. : Наука, 1990. – 384 с.
3. Kolasinska E. On a Minimum Cycle Bases of a Graph / E. Kolasinska // Zastosowania Matematyki. – 1980. – Р. 631-639.
4. Зыков А. А. Основы теории графов / А. А. Зыков. – М. : Наука, 1987. – 384 с.
5. Kavitha T. Cycle spaces in graphs: characterization, algorithms, complexity, and applications / T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt, K. Zweig // Comput. Sci. Rev. 3. – 2009. – P. 199-243.
6. Харари Ф. Теория графов / [Пер. с англ. Козырева В.П. под ред. Гаврилова В.Г.]. – М. : Мир, 1973. – 300 с.
7. Курапов С. В. Методы построения топологического рисунка графа / С. В. Курапов, А. В. Толок // Автоматика и телемеханика. – 2013. – № 9. – С. 78-97.
8. Хопкрофт Дж. Е. Изоморфизм планарных графов / Дж. Е. Хопкрофт, Р. Е. Тарьян // В кн. : Кибернетический сборник. Новая серия. – 1975. – Вып. 12. – С. 39-61.
9. Свами М. Графы, сети и алгоритмы : Пер. с англ. / М. Свами, К. Тхуласираман. – М. : Мир, 1984. – 455 с.
Опубліковано
2016-10-13
Як цитувати
Курапов, С. В., Давидовський, М. В., & Кліценко, Г. А. (2016). ІЗОМЕТРИЧНІ ЦИКЛИ ГРАФА. Computer Science and Applied Mathematics, (1), 121-137. вилучено із http://journalsofznu.zp.ua/index.php/comp-science/article/view/1350
Розділ
Articles
ISSN 
