Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Специальные матрицы графов Беляевский, Владимир Васильевич

Данная диссертационная работа должна поступить в библиотеки в ближайшее время
Уведомить о поступлении

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Беляевский, Владимир Васильевич. Специальные матрицы графов : автореферат дис. ... кандидата физико-математических наук : 01.01.09 / АН Беларуси. Ин-т мат..- Минск, 1992.- 14 с.: ил. РГБ ОД, 9 92-2/3166-5

Введение к работе

*"'' ^1ї5ймость_проблеиьк Известно немало практических задач и еоретических проблем в математике, физике, химии, которые сводят-:я к изучению спектра матрицы специального вида. В теории графов »та проблематика активно изучается после появления работ Л.М.Лих--енбаума (1956), Л.Коллаца и У. Синоговица (1957). Одним из стиму-!ов ее развития является, в частности, постоянное совершенствова-ше и математизация теории молекулярных орбиталей в химии.

Привлечение в теорию графов мощных и хорошо разработанных ілгебраических методов обеспечило интенсивность развития спектра-іьной теории графов, а теоретические и практические приложения юзволили сформулировать основные вопросы этого раздела математи-си. Как отметил Д.Цветкович , среди них такие, как "...конструирование коспектральных графов, поведение собственных значений при треобразованиях графа, спектр и реконструкция графов...".

Значительный вклад в развитие спектральной теории графов внесли Л.Бабаи, Н.Бигс, Р. Боуз, Ф. Буссемакер, С. Годсил, И.Гутман, М. Дуб, Ю. Зайдель, X. Захс, Р.Камерон, Ю. Ван Линт, А. Мовшовиц, В. Хе~ мерс, Б. Татт, Д. Хигман, А. Хофмак, Д. Цветкович, А. Швенк и другие.

Большинство работ этих авторов связано с рассмотрением характеристического многочлена графа (т.е. характеристического многочлена его матрицы смежности), который является важным инвариантом для описания и исследования структурных свойств графов. Построение Л.Коллацем и У. Синоговицем в 1957 году неизоморфных коспектральных графов привело к изучению характеристических многочленов других матриц, однозначно задающих граф. К таким матрицам относятся матрицы Заяделя, Кирхгофа и другие. Естественно возникает вопрос о взаимосвязях различных спектров графов. Для его решения перспективным является исследование обобщенной матрицы смежности, введенной Х.Юбо (1975) под другим названием и которую использовали' для исследований другие авторы.

Важность конструирования коспектральных графов раскрыта

Cvetkovic D. Some possible directions In further investigations of graph spectra // Algebraic Methods in Graph Theory. - Vol I. Colloq. Math. Soc. - Amsterdam, 1981. - P. 47-67.

Д. Цветковичем, М. Дубом, X. Захсом . В контексте этого обоснована еше более значительный интерес представляют вопросы построения не изоморфных графов с одинаковыми обобщенными характеристическим; многочленами (такие графы будем называть бикоспектральными >. В литературе этот вопрос специально не рассматривался, хотя некоторьи известные .классы графов, как оказалось, таковыми являются. Сильні регулярные графы (Р. Боуз, 1963), полярные графы (Р. И. Тышкевич, 1980), а также операции прямой суммы и полного произведения гра фов, введенные А.А.Зыковым, являются перспективными объектами для построения семейств бикоспектральных графов.

Известная гипотеза Улама (точнее, гипотеза Келли-Улама) сост< ит в том, что граф с числом вершин п>3 может быть восстановлен по набору, состоящему из п его (п-1)-вершинных порожденных подграфов полученных из исходного удалением каждой его вершины. Эта гипотеза, как'известно, подтверждена только для отдельных классов графоі и тесно связана с одной из центральных проблем теории графов -изоморфизме. Сложность вопроса, поставленного в гипотезе Келли-Улама привела к рассмотрению ее спектрального варианта (И.Гутман, Д.Цветкович, 1975, А. Швенк, 1979) - по набору характеристических многочленов (п-1 )-вершнных порожденных подграфов восстановить характеристический многочлен графа, который в настоящее время также не подтвержден в общем случае.- Б связи с этим, определенный интерес представляет спектральный вариант гипотезы, сформулированный в терминах обобщенных характеристических многочленов.

ЦіЬ!5_Е52їїї является выявление взаимосвязей между обобщенны ми характеристическими многочленами и модифицированными (в том чи еле, иэвестньми) характеристическими многочленами графа; конструи рование бикоспектрапьных графов; реконструкция обобщенного характеристического многочлена n-вершинного граф- по набору обобщенных характеристических многочленов его (п-1)-вершинных порожденных подграфов.

11а^чная_новизча работы заключается в. следующем:

- исследован новый класс бикоспектральных графов, построены их бесконечные|серии;

цвегкович Д.,'Дуб М. , Захс X. Спектры графов. Теория и применени //Киев: Наукова думка, 1984. Пер. с англ.: D. Cvetkovlc, M.Daob H.Sachs. Spectra of Graph. Theory and Application. Berlin, 1980.

- положительно рекен один из спектральных аналогов гипотезы .{елли-Улама, сформулированный в терминах обобщенных характеристических многочленов n-аершинного графа и < h-1 )-вершинных порожден-* шх подграфов.

їейіїеїУЧЕЄ^е-й-ПЕ^ЇЙЇЕ^ЕЕ-Значение^ Работа носит теоретический характер. Основное ее значение состоит в развитии аппарата обобщенных характеристических многочленов графов и применении его для решения общетеоретических задач спектральной теории графов. Результаты и методы изложенные в диссертации могут быть применимы не только а спектральном, но и в других разделах теории графов.

П^бликацин^ По теме диссертации опубликовано 4 работы.

Апобация_боты^ Результаты диссертации докладывались на IV Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1989), научной конференции "Актуальные проблемы социально-гуманитарных и естественных наук", посвященной 70-летию университета (Минск, 1991), городском семинаре по теории графов под рук. Р.И.Тыяхевич (Минск, 1986-1990 ), семинаре лаборатории математической кибернетики ИМ АН Беларуси (Минск, 1991), семинаре "Кетоды и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1991).

Объем_|щботы^ Диссертация изложена на 111 страницах и состоит из введения, трех глав, списка цитируемой литературы, содержащего 94 наименования.