A Constructive Classification of Graphs
https://doi.org/10.18255/1818-1015-2012-4-144-153
Abstract
The classes of graphs closed regarding the set-theoretical operations of union and intersection are considered. Some constructive descriptions of the closed graph classes are set by the element and operational generating basses. Such bases have been constructed for many classes of graphs. The backward problems (when the generating bases are given and it is necessary to define the characteristic properties of corresponding graphs) are solved in the paper. Subsets of element and operational bases of the closed class of all graphs are considered as generating bases.
About the Author
M. A. Iordanskii
Нижегородский государственный педагогический университет
Russian Federation
заведующий кафедрой информатики и информационных технологий, доктор физ.-мат. наук, профессор
Russian Federation
заведующий кафедрой информатики и информационных технологий, доктор физ.-мат. наук, профессор
References
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384 с.
2. Иорданский М.А. Конструктивные описания графов // Дискретный анализ и исследование операций. 1996. Т. 3, № 4. С. 35–63.
3. Иорданский М.А. Функциональный подход к представлению графов // Доклады РАН. 1997. Т. 353, № 3. С. 303–305.
4. Иорданский М.А.Сложность конструктивных описаний планарных графов // Материалы IX Межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 16–19 декабря 1998 г.). М.: Изд-во механико-математического факультета МГУ, 1999. С. 20–24.
5. Иорданский М.А. Конструктивные описания и экономное кодирование графов // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. 2000. Вып. 1(22). С. 88–93.
6. Иорданский М.А. Оптимальные нумерации вершин графов // Математические вопросы кибернетики. 2001. Вып. 10. С. 83–102.
7. Иорданский М.А. Структура и способы порождения замкнутых классов графов // Дискретная математика. 2003. Т. 15, вып. 3. С. 105–116.
8. Иорданский М.А. Базисы планарных графов // Труды V Международной конференции "Дискретные модели в теории управляющих систем" (Ратмино, 26–29 мая 2003 г.). М.: Издательский отдел факультета ВМиК МГУ им. М.В. Ломоносова, 2003. С. 36–38.
9. Бурков Е.В. Операционные базисы замкнутых классов графов // Материалы IX международного семинара "Дискретная математика и её приложения", Москва, 18–23 июня 2007 г. М.: Изд-во мехмата МГУ. 2007. С. 105–116.
10. Иорданский М.А. Конструктивные описания двудольных графов // Проблемы теоретической кибернетики. Тезисы докладов XV Международной конференции (Казань, 2–7 июня 2008 г.). Казань: Отечество, 2008. С. 44.
11. Иорданский М.А. Конструктивные описания расщепляемых графов // Материалы X Международного семинара "Дискретная математика и её приложения"(Москва, МГУ, 1–6 февраля 2010 г.) М.: Изд-во механико-математического факультета МГУ. 2010. С. 306–308.
12. Бурков Е.В. Конструктивные описания планарных и эйлеровых графов //Вестник Нижегородского государственного университета. Математика. 2010. № 5(1). С. 165–170.
13. Иорданский М.А. Функциональные построения в теории графов // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20–25 июня 2011 г.) / Под ред. Ю.И. Журавлева. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. С. 183–187.
14. Яблонский С.В. Введение в дискретную математику. М.: Наука,1979. 272 с.
Review
For citations:
Iordanskii M.A. A Constructive Classification of Graphs. Modeling and Analysis of Information Systems. 2012;19(4):144-153. (In Russ.) https://doi.org/10.18255/1818-1015-2012-4-144-153
Views:
945
Email this article 