Введение к работе
*"'' ^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 наименования.