Введение к работе
Актуальность темы. В большинстве приложений теории графов возникает необходимость вводить показатели, выражающие силу связи любых двух вершин друг с другом. К моделируемым понятиям относятся "доступность" одной вершины из другой, "надежность" их соединения, "интенсивность взаимодействия", "передаваемый поток", наконец, просто близость вершин.
В качестве обобщающего будем в основном использовать наиболее простой термин "показатель близости", отдавая себе отчет в нетождественности понятия "близость" и понятий "связанность", "доступность" и т.д. Эти и другие понятия также будут использоваться там, где это уместно.
Приложениями являются, по-существу, все приложения теории графов: транспорт, передача информации, структурное моделирование, химия, молекулярная биология, анализ социальных сетей, эпидемиология и другие.
Введение структурных индексов графов в этих областях в основном продиктовало конкретными прикладными потребностями и, как правило, опирается не на точные математические модели, адекватность которых труднопроверяема, а на эвристики. Поэтому первостепенную важность приобретает сравнительный анализ свойств этих показателей. В условиях отсутствия точных моделей он может являться основой установления адекватности использования тех или иных индексов: можпо из предлагаемого набора исследованных свойств выбрать наиболее желательные и найти индексы, обладающие именно этими свойствами.
Показатели связанности вершин графов вводились в основном в следующих областях: социологии, химической информатике, управлении транспортом и нелокальном агрегировании парных сравнений. Несмотря на большие содержательные различия этих областей,
работы велись практически параллельно, но серьезный сравнительный анализ свойств нигде не проводипся. Очень мало работ на эту тему и в теории графов.
Таким образом, проблема разработки теории структурных индексов графов и сетей актуальна с точки зрения практики; возникающие здесь задачи интересны и чисто математически.
Цель работы. Целью работы является разработка элементов теории показателей близости вершин графов.
На этом пути можно выделить следующие этапы.
-
Изучить разные показатели близости, предложенные в литературе по теории графов и ее приложениям.
-
Выделить те свойства, которые характерны для большинства показателей близости, а также особенности каждого показателя. Типичные свойства должны послужить формализации понятия "показатель близости", особенности — определению областей применения разных показателей.
-
Изучить взаимосвязи показателей близости вершин графов с другими (в особенности — топологическими: пути, маршруты, деревья, леса) понятиями теории графов.
-
Построить новые показатели близости, обладающие требуемыми свойствами.
5. Анализ показателей близости вершин графов может под
сказать аксиомы, задающие пространство функций близости, опре
деленных на декартовом квадрате произвольного множества (не обя
зательно множества вершин графа). Если такое понятие будет введе
но, представляет интерес его соотношение с понятием метрического
пространства.
Полное решение всех этих задач не может быть получено в рамках кандидатской диссертации. Кратко задача диссертации ставится так: провести первый этап исследований по всем этим направлениям, и в рамках этого этапа получить глубокие, насколько воз-
можно, результаты, создав тем самым первый эскиз предполагаемой теории.
Методы исследования. В диссертации используются методы теории графов и линейной алгебры.
Научная новизна и практическая значимость работы.
Впервые проводится систематический анализ свойств различных показателей связанности вершин графов, предложенных в различных прикладных областях. Получена матричная теорема о лесах, обобщающая классическую матричную теорему о деревьях. На ее основе построено новое семейство структурных индексов графов. Получена топологическая интерпретация обобщенно-обратной ла-пласовской матрицы взвешенного мультиграфа по Муру-Пенроузу. Введен класс функций Е-блпзости па произвольных конечных множествах и установлена их двойственность метрикам. Результаты могут быть использованы в приложениях теории графов и сетей: при анализе транспортных и социальных сетей, в химической информатике, агрегировании предпочтений и других.
Апробация работы. Результаты работы докладывались на научных семинарах в Институте проблем управления, общемосковском семинаре "Математические методы в экспертных оценках и анализ данных" па Международных конференциях Общества по Лилейной Алгебре (ILAS) (Атланта, США, 1995), "Эконометрические модели принятия решений" (Хаген, Германия, 1995), "Управление большими системами" (Москва, 1997), на Российско-испанском семинаре по групповому выбору (Барселона, Испания, 1995), па Международной школе по прогнозированию (Звенигород, 1997), в Университете г.Таампере (Финляндия, 1997).
Публикации. По теме диссертации автором опубликовано 9 работ.
Объем и структура работы. Диссертация изложена на 115 страницах машинописного текста и состоит из введения, трех глав и