Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Razumovsky P. V. The search for minimal edge 1-extension of an undirected colored graph [Разумовский П. В. О поиске минимальных реберных 1-расширений неориентированного цветного графа] // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2021. Т. 21, вып. 3. С. 400-407. DOI: 10.18500/1816-9791-2021-21-3-400-407


Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
31.08.2021
Полный текст:
(downloads: 64)
Язык публикации: 
английский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
517.98

The search for minimal edge 1-extension of an undirected colored graph
[О поиске минимальных реберных 1-расширений неориентированного цветного графа]

Авторы: 
Разумовский Петр Владимирович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Граф $G=(V, \alpha, f)$ — это цветной граф с определенной на множестве его вершин функцией раскраски $f$. Цветной граф $G^*$ называется реберным $1$-расширением цветного графа $G$, если граф $G$ можно вложить с учетом цветов в каждый граф, получающийся из графа $G^*$ удалением любого его ребра. Реберное $1$-расширение $G^*$ графа $G$ называется минимальным, если граф $G^*$ имеет столько же вершин, сколько содержит исходный граф $G$, а среди всех реберных $1$-расширений графа $G$ граф $G^*$ имеет минимальное число ребер. Рассматривается задача поиска минимальных реберных $1$-расширений цветного графа без проверки на изоморфизм. Предлагается алгоритм поиска множества всех неизоморфных минимальных 1-расширений для заданного цветного графа.

Список источников: 
  1. Avizienis A. Design of fault-tolerant computers. AFIPS ’67 (Fall): Proceedings of the November 14–16, 1967, fall joint computer conference. New York, ACM, 1967, pp. 733– 743. https://doi.org/10.1145/1465611.1465708
  2. Hayes J. P. A graph model for fault-tolerant computing system. IEEE Transactions on Computers, 1976, vol. C-25, iss. 9, pp. 875–884. https://doi.org/10.1109/TC.1976.1674712
  3. Harary F., Hayes J. P. Edge fault tolerance in graphs. Networks, 1993, vol. 23, pp. 135–142. https://doi.org/10.1002/net.3230230207
  4. Harary F., Hayes J. P. Node fault tolerance in graphs. Networks, 1996, vol. 27, pp. 19–23. https://doi.org/10.1002/(SICI)1097-0037(199601)27:1%3C19::AID-NET2%3E3.0.CO;2-H
  5. Abrosimov M. B. Grafovye modeli otkazoustoichivosti [Fault Tolerance Graph Models]. Saratov, Izd-vo Sarat. un-ta, 2012. 192 p. (in Russian).
  6. McKay B. D. Isomorphism-free exhaustive generation. Journal of Algorithms, 1998, vol. 26, iss. 2, pp. 306–324. https://doi.org/10.1006/jagm.1997.0898
  7. Brinkmann G. Isomorphism rejection in structure generation programs. Discrete Mathematical Chemistry (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 51). 2000, pp. 25–38. https://doi.org/10.1090/dimacs/051/03
  8. Abrosimov M. B., Sudani H. H. K., Lobov A. A. Construction of all minimal edge extensions of the graph with isomorphism rejection. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2020, vol. 20, iss. 1, pp. 105–115 (in Russian). https://doi.org/10.18500/1816-9791-2020-20-1-105-115
  9. Abrosimov M. B., Kamil I. A. K., Lobov A. A. Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2019, vol. 19, iss. 4, pp. 479– 486 (in Russian). https://doi.org/10.18500/1816-9791-2019-19-4-479-486
  10. Zykov A. A. Osnovy teorii grafov [The Basics of the Graph Theory]. Moscow, Vuzovskaya kniga, 2004. 664 p. (in Russian).
Поступила в редакцию: 
25.01.2021
Принята к публикации: 
29.04.2021
Опубликована: 
31.08.2021