Конструктивная классификация графов
https://doi.org/10.18255/1818-1015-2012-4-144-153
Аннотация
Рассматриваются классы графов, замкнутые относительно теоретико-множественных операций объединения и пересечения. Конструктивные описания замкнутых классов графов задаются порождающими элементными и операционными базисами. К настоящему времени они построены для многих классов графов. В данной работе решаются обратные задачи: по заданным порождающим базисам необходимо определить характеристические свойства соответствующих графов. В качестве порождающих базисов рассматриваются подмножества элементного и операционного базисов замкнутого класса всех графов.
Об авторе
Михаил Анатольевич Иорданский
Нижегородский государственный педагогический университет
Россия
заведующий кафедрой информатики и информационных технологий, доктор физ.-мат. наук, профессор
Россия
заведующий кафедрой информатики и информационных технологий, доктор физ.-мат. наук, профессор
Список литературы
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 с.
Рецензия
Для цитирования:
Иорданский М.А. Конструктивная классификация графов. Моделирование и анализ информационных систем. 2012;19(4):144-153. https://doi.org/10.18255/1818-1015-2012-4-144-153
For citation:
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
Просмотров: 772
Послать статью по эл. почте 