maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2012-4-144-153mais-48Research ArticleОригинальные статьиArticlesКонструктивная классификация графовA Constructive Classification of GraphsИорданскийМихаил АнатольевичIordanskiiM. A.

заведующий кафедрой информатики и информационных технологий, доктор физ.-мат. наук, профессор

заведующий кафедрой информатики и информационных технологий, доктор физ.-мат. наук, профессор

iordanski@mail.ruНижегородский государственный педагогический университетРоссияНижегородский государственный педагогический университетRussian Federation201228022015194144153Copyright © Иорданский М.А., 20152015Иорданский М.А.Iordanskii M.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/48

Рассматриваются классы графов, замкнутые относительно теоретико-множественных операций объединения и пересечения. Конструктивные описания замкнутых классов графов задаются порождающими элементными и операционными базисами. К настоящему времени они построены для многих классов графов. В данной работе решаются обратные задачи: по заданным порождающим базисам необходимо определить характеристические свойства соответствующих графов. В качестве порождающих базисов рассматриваются подмножества элементного и операционного базисов замкнутого класса всех графов.

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.

графоперация склейкизамкнутый классэлементный и операционный базисыконструктивное описаниехарактеристическое свойствоgraphsewing operationclosed classelement and operation basesconstructive descriptioncharacteristic propertyReferencesЕмеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384 с.Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384 с.Иорданский М.А. Конструктивные описания графов // Дискретный анализ и исследование операций. 1996. Т. 3, № 4. С. 35–63.Иорданский М.А. Конструктивные описания графов // Дискретный анализ и исследование операций. 1996. Т. 3, № 4. С. 35–63.Иорданский М.А. Функциональный подход к представлению графов // Доклады РАН. 1997. Т. 353, № 3. С. 303–305.Иорданский М.А. Функциональный подход к представлению графов // Доклады РАН. 1997. Т. 353, № 3. С. 303–305.Иорданский М.А.Сложность конструктивных описаний планарных графов // Материалы IX Межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 16–19 декабря 1998 г.). М.: Изд-во механико-математического факультета МГУ, 1999. С. 20–24.Иорданский М.А.Сложность конструктивных описаний планарных графов // Материалы IX Межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 16–19 декабря 1998 г.). М.: Изд-во механико-математического факультета МГУ, 1999. С. 20–24.Иорданский М.А. Конструктивные описания и экономное кодирование графов // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. 2000. Вып. 1(22). С. 88–93.Иорданский М.А. Конструктивные описания и экономное кодирование графов // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. 2000. Вып. 1(22). С. 88–93.Иорданский М.А. Оптимальные нумерации вершин графов // Математические вопросы кибернетики. 2001. Вып. 10. С. 83–102.Иорданский М.А. Оптимальные нумерации вершин графов // Математические вопросы кибернетики. 2001. Вып. 10. С. 83–102.Иорданский М.А. Структура и способы порождения замкнутых классов графов // Дискретная математика. 2003. Т. 15, вып. 3. С. 105–116.Иорданский М.А. Структура и способы порождения замкнутых классов графов // Дискретная математика. 2003. Т. 15, вып. 3. С. 105–116.Иорданский М.А. Базисы планарных графов // Труды V Международной конференции "Дискретные модели в теории управляющих систем" (Ратмино, 26–29 мая 2003 г.). М.: Издательский отдел факультета ВМиК МГУ им. М.В. Ломоносова, 2003. С. 36–38.Иорданский М.А. Базисы планарных графов // Труды V Международной конференции "Дискретные модели в теории управляющих систем" (Ратмино, 26–29 мая 2003 г.). М.: Издательский отдел факультета ВМиК МГУ им. М.В. Ломоносова, 2003. С. 36–38.Бурков Е.В. Операционные базисы замкнутых классов графов // Материалы IX международного семинара "Дискретная математика и её приложения", Москва, 18–23 июня 2007 г. М.: Изд-во мехмата МГУ. 2007. С. 105–116.Бурков Е.В. Операционные базисы замкнутых классов графов // Материалы IX международного семинара "Дискретная математика и её приложения", Москва, 18–23 июня 2007 г. М.: Изд-во мехмата МГУ. 2007. С. 105–116.Иорданский М.А. Конструктивные описания двудольных графов // Проблемы теоретической кибернетики. Тезисы докладов XV Международной конференции (Казань, 2–7 июня 2008 г.). Казань: Отечество, 2008. С. 44.Иорданский М.А. Конструктивные описания двудольных графов // Проблемы теоретической кибернетики. Тезисы докладов XV Международной конференции (Казань, 2–7 июня 2008 г.). Казань: Отечество, 2008. С. 44.Иорданский М.А. Конструктивные описания расщепляемых графов // Материалы X Международного семинара "Дискретная математика и её приложения"(Москва, МГУ, 1–6 февраля 2010 г.) М.: Изд-во механико-математического факультета МГУ. 2010. С. 306–308.Иорданский М.А. Конструктивные описания расщепляемых графов // Материалы X Международного семинара "Дискретная математика и её приложения"(Москва, МГУ, 1–6 февраля 2010 г.) М.: Изд-во механико-математического факультета МГУ. 2010. С. 306–308.Бурков Е.В. Конструктивные описания планарных и эйлеровых графов //Вестник Нижегородского государственного университета. Математика. 2010. № 5(1). С. 165–170.Бурков Е.В. Конструктивные описания планарных и эйлеровых графов //Вестник Нижегородского государственного университета. Математика. 2010. № 5(1). С. 165–170.Иорданский М.А. Функциональные построения в теории графов // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20–25 июня 2011 г.) / Под ред. Ю.И. Журавлева. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. С. 183–187.Иорданский М.А. Функциональные построения в теории графов // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20–25 июня 2011 г.) / Под ред. Ю.И. Журавлева. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. С. 183–187.Яблонский С.В. Введение в дискретную математику. М.: Наука,1979. 272 с.Яблонский С.В. Введение в дискретную математику. М.: Наука,1979. 272 с.

The authors declare that there are no conflicts of interest present.