автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Показатели близости вершин графов, их свойства и применение

Российская Академия наук Институт проблем управления

На правах рукописи

Шамис Елена Валерьевна

УДК 519.173:512.643.8

ПОКАЗАТЕЛИ БЛИЗОСТИ ВЕРШИН ГРАФОВ, ИХ СВОЙСТВА И

ПРИМЕНЕНИЕ

05.13.01 - Управление в технических системах

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1998

Работа выполнена в Институте проблем управления Российской Академии Наук.

Научный руководитель - доктор физико-математических наук,

1А.И. МА.НИШКЖ 1КИЙ1

Официальные оппоненты - доктор технических наук

А. С. Манде ль,

кандидат физико-математических наук С. И. Травкин

Ведущая организация - Вычислительный центр РАН

Защита диссертации состоится 25 июня 1998 г. в 14 ч. на заседании диссертационного совета Д 002.68.03 Института проблем управления по адресу: 117806, Москва, ул. Профсоюзная 65.

С диссертацией можно ознакомиться в библиотеке ИПУ.

Автореферат разослан 25 мая 1998 г.

Ученый секретарь диссертационного совета кандидат технических наук

С.А. Власов

Общая характеристика работы

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

В качестве обобщающего будем в основном использовать наиболее простой термин "показатель близости", отдавая себе отчет в нетождественности понятия "близость" и понятий "связанность", "доступность" и т.д. Эти и другие понятия также будут использоваться там, где это уместно.

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

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

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

работы велись практически параллельно, но серьезный сравнительный анализ свойств нигде не проводился. Очень мало работ на эту тему и в теории графов.

Ткким образом, проблема разработки теории структурных индексов графов и сетей актуальна с точки зрения практики; возникающие здесь задачи интересны и чисто математически.

Цель работы. Целью работы является разработка элементов теории показателей близости вершин графов.

На этом пути можно выделить следующие этапы.

1. Изучить разные показатели близости, предложенные в литературе по теории графов и ее приложениям.

2. Выделить те свойства, которые характерны для большинства показателей близости, а также особенности каждого показателя. Типичные свойства должны послужить формализации понятия "показатель близости", особенности — определению областей применения разных показателей.

3. Изучить взаимосвязи показателей близости вершин графов с другими (в особенности — топологическими: пути, маршруты, деревья, леса) понятиями теории графов.

4. Построить новые показатели близости, обладающие требуемыми свойствами.

5. Анализ показателей близости вершин графов может подсказать аксиомы, задающие пространство функций близости, определенных на декартовом квадрате произвольного множества (не обязательно множества вершин графа). Если такое понятие будет введено, представляет интерес его соотношение с понятием метрического пространства.

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

можно, результаты, создав тем самым первый эскиз предполагаемой теории.

Методы исследования. В диссертации используются методы теории графов и линейной алгебры.

Научная новизна и практическая значимость работы.

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

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

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

Объем и структура работы. Диссертация изложена на 115 страницах машинописного текста и состоит из введения, трех глав и

списка литературы, включающего 138 названий.

Содержание диссертации

Во введении обосновывается актуальность темы диссертации, определяется цель исследования, приводится краткое содержание работы, формулируются основные результаты.

В первой главе описываются некоторые задачи, требующие введения показателей связанности вершин и других структурных индексов графов и сетей. Вводятся необходимые понятия теории графов и приводятся формулировки матричной теоремы о деревьях для взвешенных мультиграфов и взвешенных мультиорграфов.

В качестве областей приложения структурных индексов графов и сетей рассматриваются транспортные сети, химическая информатика и паукометрия, социометрия и агрегирование предпочтений.

Пусть О — взвешенный мультиграф с множеством вершин К(б') = {1,..., п} и множеством ребер Е(0), Г — взвешенный муль-тиорграф с множеством вершин У (Г) = {1,... ,п} и множеством дуг £(Г), веса ребер и дуг обозначаются (р-е ребро или дуга из г в ]) и строго положительны. Корневое дерево — это дерево с одной отмеченной вершиной, называемой корнем. Корневой лес определяется как лес с одпой отмеченной вершиной в каждой компоненте. Исходящее дерево есть ориентированное корневое дерево, содержащее направленные пути из корня во все другие вершины. Исходящий лес есть ориентированный корневой -лес, все компоненты которого — исходящие деревья.

Пусть Е = (£у) — матрица суммарных весов ребер (дуг) для пар вершин:

Р=1

где а¡; — число ребер (дуг), соединяющих г п j. Произведение весов всех ребер подграфа Н мультиграфа б будем называть весом (проводимостью) Н и обозначать е(Н). Вес (проводимость) подграфа, не имеющего ребер, считается равным 1. Для любого непустого мпожества подграфов 0 его вес есть

е(д) = £ е(Я). (1)

вед

Вес пустого множества полагается равным нулю.

Через Р — (ру) обозначаются различные матрицы, интерпретируемые как матрицы близости (доступности, связанности) вершин О или Г.

Ряд результатов диссертации связан с понятием лапласовской матрицы (матрицы Кпрхгофа) графа. Пусть А(С!) — (а1;) — матрица смежности графа б. Матрицей Кирхгофа (лапласовской матрицей, матрицей проводимостей) мультиграфа С? называют п X п-матрпцу Ь = 1>(С1) = (1^) с элементами аи

1ц = - Е 4" = О «>3 = • • •! п> (2)

Р= 1

4 = -Е^Ц=£й| ¿=1,...,п. (3)

№

Согласно матричной теореме о деревьях, полученной еще в прошлом веке Кирхгофом, алгебраическое дополнение любого элемента матрицы Ь(0) равно числу остовных деревьев мультиграфа С. Татт предложил теоремы, обобщающие матричную теорему о деревьях на взвешенные мультпграфы и мультиорграфы. В первой главе диссертации приводятся формулировки этих теорем и обзор других исследований, связанных с матрицами графов.

Во второй главе диссертации, являющейся основной, вводятся нормативные свойства показателей связанности вершин графов и рассматриваются некоторые естественные показатели, разрабатывается одна из возможных формализаций понятия близости, вводится показатель близости, соответствующий простейшей графовой

метрике, доказывается матричная теорема о лесах и вводится определяемый ей новый показатель связанности, и предлагается топологическая интерпретация матрицы, обобщенно-обратной по Муру-Пенроузу к лапласовской матрице графа; для всех рассматриваемых показателей проверяется выполнение нормативных свойств.

В качестве нормативных свойств показателей связанности предлагаются следующие условия:

Симметричность. Для любого мультиграфа матрица Р симметрична.

Неотрицательность. Для любого мультиграфа (мультиоргра-фа) р^ > 0, = 1,...,п.

Обратимость. Для любого мультиорграфа обращение всех его дуг (при сохранении их весов) приводит к транспонированию матрицы близости.

Диагональное превосходство. Для любого мультиграфа (мультиорграфа) и любых г, ^ — 1,..., гг, i ф j имеет место рй > ри Ра >

Неравенство треугольника для близостей. Для любого мультиграфа и для любых г,_7, к = 1,...,гг имеет место р^+рц—р^ < Ра -Если, к тому же, ] = к и{ф то неравенство строгое.

Условие несвязности. Для любого мультиграфа (мультиорграфа) и любых ¿,,7 = 1,..., п р^ — 0 если и только если о мультиграфе (мулътиорграфе) пет путей из г в $.

Условие связности (следствие из условия несвязности). 1) Для любого мультиграфа матрица Р приводима к блочно-диагональному виду, где все элементы блоков строго положительны, а все элементы вне блоков — нули. Матрица Р строго положительна тогда и только тогда, когда С? связен.

2) Для любых г, к Е У {О), если р^ > 0 и р^к > 0, то р{к > 0.

Транзитность. Для любого мультиграфа G и любых i,k,t £ V(G), если в G есть путь от г до к, г ф к ф t, и каждый путь от г до t включает к, то pik > pü .

Монотонность. Пусть вес некоторого ребра (дуги) в мулътиграфе G (мулътиорграфе Г) увеличился или к нему было добавлено новое ребро (дуга) между к и t. Тогда:

1) Дрл.* > 0, и для любых i,j — 1,... ,п, если {i,j} ф i}, то АрИ > APij]

2) для любых г = 1,..., п, если существует путь от i до к, и каждый путь от i до t включает к, то Аpit > Дpile;

3) для любых ¿j,i2= 1,...,п, еслигх иг2 могут быть подставлены на место i в посылку пункта 2, то р^ не увеличивается.

Далее во второй главе изучаются свойства следующих показателей связанности вершин мультиграфов (мультиорграфов).

1) Путевая доступность — простейший среди показателей близости вершин графа, учитывающих не только кратчайший путь между ними. Путевая доступность вершины j из вершины i определяется как суммарный вес всех путей из i в j. При j = i путями из г в г можно считать все простые циклы из г в г плюс путь длины О, вес которого принимается равным 1.

2) Надежность связи inj — вероятность наличия хотя бы одного исправного пути, при интерпретации весов как вероятностей исправности ребер (дут);

3) Величина максимального потока между парой вершин при интерпретации весов Kai: пропускных способностей ребер;

4) Маршрутная доступность. Рассмотрим матрицу Р — (I — Е)~1. Пользуясь, при ограничении, полученном из анализа спектрального радиуса матрицы Е,

^<(т(п-1)Г\ (4)

формулой бесконечно убывающей геометрической прогрессии, запи-

шем

Р= {1-Е)-1 = 1 + Е + Е2 + ... (5)

Пусть Л^' — множество маршрутов между г и j. Тогда

Лу= Е (6)

яелГц

т.е. р{] — суммарный вес маршрутов из г в ] (при ] = г учитывается и маршрут длины 0, имеющий вес 1), а Р — матрица маршрутных доступностей в мультиграфе (мультиорграфе).

В доказанных теоремах 3-7 говорится о свойствах рассмотренных показателей близости; результаты теорем приведены в таблице 1.

Введен показатель

¿гз = Ра +Рц -Рц ~Рц, ¿,3 = 1,...,П (7)

и следующее нормативное свойство.

Метрическая представимость близости. Показатель ¿^ есть расстояние между вершинами мультиграфа, т.е. удовлетворяет аксиомам метрики.

Данное свойство всегда выполняется при выполнении симметричности и неравенства треугольника для близостей; последнее оказывается при этом тесно связанным с обычным неравенством треугольника для расстояний <1у. Более того, как показано во второй главе диссертации, между метриками, заданными на произвольном множестве, и функциями, удовлетворяющими неравенству треугольника для близостей и дополнительному условию нормировки, обнаруживается своеобразная двойственность.

Определение. Пусть А - непустое конечное множество, Е -действительное число. Функцию а : А2 —» я назовем ^-близостью на А, если для любых х,у,г £ А выполняются

Свойство Пути Надежн. Маршр. Леса (неор.) Леса (ор.) "Густые" леса

Симметричность + + + + X +

Неотрицательность + . + + + + +

Обратимость + + + X + X

Диагональное превосходство +* + + + +

Нер-во тр-ка для близостей +* + + +

Несвязность + + + + +

Транзитность +* + + + +

Монотонность 1 +* +* + + + -

Монотонность 2 + + + + -

Монотонность 3 + + - + + -

* выполняется при дополнительном ограничении и/или в нестрогой версии ** доказано при дополнительном ограничении х свойство неприменимо

Таблица 1. Некоторые свойства показателей близости вершин графов

1) условие нормировки:

5>(M) = s; (8)

t€A

2) неравенство треугольника для близостей: а(х,у) + a{x,z) — cr(y,z) ¡s ст(х, х), причем если z — у и х ф у, то неравенство строгое.

Предложение 1. Пусть ег есть Е-близость на А. Тогда для любых х,у € А

а(х,у) = а(у,х) (симметричность);

если х ф у, то ст(х,х) > сг(х,у) (диагональное превосходство). Далее использованы обозначения:

= (9)

п teA

= h Е d(,,t). (10)

п s,teA

Предложение 2. Для любой метрики d на конечном множестве А функция

<т(х, у) = d{x, •) + <%, •) - d{x, у) - d(; •) + 5 (11)

является Е-близостью на А.

Предложение 3. Для любой Е-близости а на А функция

= + °{У>У)) - (12)

является метрикой па А.

Отображения, задаваемые (11) и (12), обозначим соответственно <p(d) и У>(сг).

Теорема 8. Отображения <р ж ip = ip-1 задают взаимно-однозначное соответствие множества метрик на А и множества Е-близо-стей на А.

Из этой теоремы выводится простое следствие, характеризующее равновесие расстояний в А.

Следствие 1. Для любого конечного множества А, любых метрики в. £ В2 и х Е Л

(13)

Как пример £ -близости во второй главе рассматривается показатель, двойственный классическому расстоянию на графе.

Далее во второй главе сформулирована матричная теорема о лесах, являющаяся одним из основных результатов диссертации. Она может рассматриваться как обобщение матричной теоремы о деревьях.

Рассмотрим матрицы

= ! + £((?), Т7(Г) = 1 + ЦТ),

где I — единичная матрица.

Пусть Т{С) = Т — множество всех остовных корневых лесов мультпграфа б, а ^(в) = — множество тех остовных корневых лесов в С, в которых ¡и; принадлежат одному дереву с корнем г. Пусть \У = IV(в).

Если существует матрица пусть

<? = (д0.) = Т= + (14)

(как для взвешенного мультиграфа С, так и для взвешенного муль-тиорграфа Г).

Теорема 10 (матричная теорема о лесах).

1. Для любого взвешенного мультиграфа (3 существует матрица <5 = Ж"1, и = £(Я*)/е(Я» *>3 = 1, • • • ,п.

2. Для любого взвешенного мультпорграфа Г существует матрица <2 = И^1, и = г'>3 = • • • >п-

При единичных весах всех ребер (дуг) веса множеств остовных лесов в матричной теореме о лесах равны количествам этих лесов.

В диссертации приведено четыре различных доказательства матричной теоремы о лесах.

Матричная теорема о лесах позволяет рассматривать С} = Ц?'1 как матрицу "относительных лесных доступностей" вершин С? (или Г). Эти величины могут использоваться в качестве меры близости (чем "дальше" г от тем меньше д^) вершин, что подтверждается их свойствами.

Согласно теореме 13, относительная лесная доступность для мультиграфов без каких-либо ограничений на веса ребер обладает всеми введенными нормативными свойствам (см. таблицу 1).

Специфическими свойствами относительной лесной доступности являются двойная стохастичность (точнее, второе ее условие) и независимость от макровершины.

Двойная стохастичность. Для любого мультиграфа б имеет

место

1) Рц > 0, г,^ = 1,...,п,

п п

2) Еру = ЕР,4 = 1, « = 1,...,п.

»=1 г=1

Согласно свойству стохастичности, в терминах Е-близости, относительная лесная доступность является 1-близостью, а р^ можно интерпретировать как долю связанности (соединенности) вершин г к j в суммарной связанности г (или у) со всеми вершинами.

Пусть Л) — подмножество множества вершин У (О). Назовем И макровершиной, если для всех г,€ -О и к ^ И имеет место е{к =

Следующее свойство — достаточное условие равенства и постоянства близостей.

Независимость от макроверпшны. Пусть I) — макровершина в мультиграфе (2 и г,£ Л, к £ Ю. Тогда р^ = р^к и р{к не меняется при добавлении новых или изменении весов имеющихся дуг внутри И.

Еще одно полезное (как для вычислений, так и для доказательства других свойств) свойство данного показателя близости — следующая теорема (в автореферате приводится только ее первый пункт).

Теорема 13 (об одношаговом изменении относительной лесной доступности в мультиграфе). Пусть в мультиграфе (? вес некоторого ребра ери увеличился на Аеи > 0 или к С? было добавлено новое ребро между к и £ с весом Аеы > 0. Пусть С — полученный мультиграф и \У = №(0), Я' = Тогда

1) дд = НЕ, где дд = д' - О, н = =

(с1ы +1/Де^) Я — (гу) — п х п-матрица с элементами г- =

(Яи~Ча)(Яц~Язк)-

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

Пусть а* = шах а-- — максимальное число кратных ребер, уеУ(с) 4 г г г,

инцидентных какой-либо паре вершин в (7.

Теорема 14. Для любого мультиграфа С? с весами ребер, принадлежащими интервалу (0, (2а*(п — I))-1), и для любых г, ] = 1,..., л

<=0

где [/¡р и — соответственно, веса маршрутов со стоками длины I с четным и нечетным числом стоков между вершинами г и ] в (?.

Аналогичные свойства и теоремы доказаны и для ориентированного случая.

Далее во второй главе получено разложение относительной лесной доступности в мультиграфе на составляющие, которые соответствуют лесам с различным числом компонент-деревьев и рассмотрены понятия близости вершин мультиграфа, соответствующие

каждой из составляющих. Пусть v — количество связных компонент в (?, ^ — множество вершин компоненты, содержащей вершину г (г = 1,... ,п).

Теорема 18 (параметрическая версия матричной теоремы о лесах для мультитрафов). Для любого взвешенного мультиграфа О и любого г ^ 0 обозначим через Я(т) = (д^-(т)) матрицу (I + тЬ)"1. Тогда Я(т) существует и

9а(т) = и = (15)

Ь=0 к-0

где Я — множество остовных корневых лесов в (?, содержащих к ребер, ^к — множество остовных корневых лесов в (?, содержащих к ребер, где ] принадлежит корневому дереву с корнем г.

Показано, что для коэффициентов при каждой степени г в (15) выполняется стохастичность.

Предложение 4. Для всех г = 1,..., п, к = 0,..., п — V

= (16)

¿=1

Матрицы {Я(т) | г > 0} определяют параметрическое семейство относительных лесных доступностей, обладающих, очевидно, теми же свойствами, что Я = Я{ 1). Согласно (15), Я{т) можно представить в виде

Я(т) = -Ц- (т°Яо + т'Яг + ... + , (17)

где «(г) = П±\ке{П), Як = (д*,0-), = к = 0,...,п-у, г, з =

1,...,п.

Каждая из матриц Як (к = 0,... ,п — у) задает своеобразную близость вершин графа.

Для описания близости, задаваемой матрицей <5п_г,, введем матрицу /(С) = 3 = (4):

0 иначе.

Лемма 13.

= (18)

Далее рассмотрена матрица

+ (19)

Предложение 5. При любом а ф 0 матрица (Ь + а 1) обратима, И §=(£ + а1)-1 -а~Ч.

Согласно предложению, матрицы С} и (Ь + а 7)-1 отличаются на матрицу, элементы которой постоянны в каждой компоненте б.

Теорема 19. Для любого взвешенного мультиграфа С? матрица <2 является обобщенно обратной к матрице Ь по Муру-Пенроузу: Я = Ь\

Теорема 20 (топологическая интерпретация матрицы Ь+, обобщенно обратной к Ь по Муру-Пепроузу).

-- при з € Ц, (20)

0 иначе.

Из предложений 7-9 вытекают следующие тождества:

(Ь + а!)'1 = Ь++а~Ч= (21)

= Нт т{${т)-1)+аГЧ = (22)

- ^ (24)

Таким образом, при 0 < а < (Ь + а /)-1 есть сумма

и с положительными коэффициентами. Если "густы-

ми" лесами пазвать остовные корневые леса вСсп-« или п — у — 1 ребрами, то показатель близости (23) при 0 < а < может

быть назван доступностью по "густым" лесам, результаты о свойствах которой отражены в таблице 1.

Последний раздел главы 2 посвящен особенностям рассмотренных показателей связанности, где в частности показано, что для маршрутной и лесной доступностей выполняется следующее свойство.

Транзитность 2. Для любого мулътпиграфа G и любых i, к, t £ V(G) если pik > pit и i ф к, то в G есть путь от г до к, такой что разность {jp^k ~Pjt) строго возрастает, когда j последовательно пробегает все вершины от i до к в этом пути.

Рассмотренные показатели близости вершин имеют существенно различные свойства. Вместе с тем, почти все они обладают основными нормативными свойствами.

Третья глава посвящена применению показателей связанности. В частности показатели связанности вершин графов, изученные ранее, рассматриваются в прикладном контексте агрегирования предпочтений и для них проверяется выполнение аксиомы самосогласованной монотонности. В ее формулировке используется термин "мультимножество", отличие которого от множества в возможности содержать один и тот же элемент в нескольких копиях.

Самосогласованная монотонность. Процедура оценивания S самосогласованно монотонна, если для любого множества альтернатив J, любого профиля А и любых альтернатив i,j £ J она удовлетворяет следующему условию.

Пусть Ui — (apik | к,р) и Uj = (а^ \ l,q) - мультимножества результатов сравнений альтернатив i и j соответственно. Предположим, что Ui может быть разделено на U- и Uf1, a Uj может быть разделено на Uj и Uj1 таким образом, что

(1) если apik G 17/, то a?ik = 1; если a4je G Uj, то aqjt — 0;

(2) существует взаимно-однозначное соответствие ж из U?1 на Uj1 такое, что 7г(а^) = сф влечет aFik ^ a4-t и sk > se.

Тогда s- > Sj.

Кроме того, если £// непусто, и.ти 11- непусто пли хотя бы одно неравенство в (2) хотя бы для одного набора индексов является

СТРОГИМ, ТО Si > Яу.

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

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

В заключительной части третьей главы для иллюстрации результатов диссертационной работы проведен анализ фрагмента реальной транспортной сети (сеть автодорог юго-востока США), которая изучалась в классической работе Гаррисона и в ряде более поздних работ.

Основные результаты диссертационной работы

1. Разработана система нормативных требований к показателям связанности вершин графов. Доказаны теоремы о свойствах известных показателей связанности.

2. Доказана матричная теорема о лесах — новый результат в алгебраической теории графов и на ее основе введен новый показатель связанности — относительная лесная доступность. Исследованы топологические свойства этого показателя.

3. Аксиоматически введено понятие функций Е-близости — одна из возможных формализаций понятия "близость". Доказана

теорема о двойствепности понятий "Е-близость" и "метрика" па конечных множествах.

4. Получена топологическая интерпретация матрицы, обобщенно-обратной по Муру-Пенроузу к лаппасовской матрице графа.

5. Исследованы свойства мер связанности вершин графов в контексте задач агрегирования неполных парных сравнений, математической социологии и анализа транспортных сетей.

Таким образом, впервые проведено систематическое исследование показателей связанности вершин графов. Полученные результаты показывают, что структурные индексы графов представляют интерес как предмет математического исследования. Эти результаты могут быть использованы в приложениях теории графов и сетей, в частности, при анализе транспортных, информационных и социальных сетей, в химической информатике и агрегировании парных сравнений.

Основные результаты диссертации опубликованы в работах:

1. Shamis Е. Graph-theoretic interpretation of the generalized row siim method // Math. Soc. Sci.- 1994.- V.27.- P.321-333.

2. Shamis E. Counting spanning converging forests // Abstracts of Papers Presented to the American Mathematical Society.- 1994.- V.15.-P.412-413.

3. Chebotarev P.Yu., Shamis E. On the proximity measure for graph vertices provided by the inverse Laplacian characteristic matrix //5 Conference of the International Linear Algebra Society, Atlanta: Georgia State University, 1995.- P.30-31.

4. Chebotarev P.Yu., Shamis E. On optimization models for aggregating incomplete preferences // E.Diday, Y.LechevaOier, O.Opitz, eds. Ordinal and Symbolic Data Analysis. Studies in Classification, Data Analysis and Knowledge Organization, Berlin: Springer-Verlag,- 1996.-P.328-338.

5. Chebotarev P. Yu., Shamis E. Preference fusion when the number of alternatives exceeds two: Indirect scoring procedures // Proceedings of Workshop on Foundations of Information / Decision Fusion, N.S.V.Rao, V.Protopopescu, J.Bernen and G.Seetharaman, eds., Lafayette, LA: Acadiana,- 1996.- P.20-32.

6. Чеботарев П.Ю., Шамис E.B. Характеризации очковых процедур агрегирования предпочтений // Материалы Межд. Научно-практпч. Конф. "Управление большими системами", Москва: СИНТЕГ, 1997.- С.241.

7. Чеботарев П.Ю., Шамис Е.В. Матричная теорема о лесах и измерение связей в малых социальных группах // Автоматика и Телемеханика.- 1997.- N9.- С.124-136.

8. Chebotarev Р. Yu., Shamis Е. Incomplete preferences and indirect scores / Working paper No. 365.97 of Departament d'Economia i d'Historia Economica, Barcelona: Universität Autonoma de Barcelona and Institut d'Analisi Economica, 1997.

9. Chebotarev P.Yu., Shamis E. Constructing an objective function for aggregating incomplete preferences // J.Gruber and A.Tangian, eds. Econometric Decision Models: Constructing Scalar-Valued Objective Functions. Lecture Notes in Economics and Mathematical Systems, Berlin: Springer-Verlag, 1997,- P.100-124.

10. Чеботарев П.Ю., Шамис E.B. О двойственности метрик и Е-близостей // АпТ.- 1998.- N4.- С.204-209.

В совместных публикациях соискательнице принадлежат следующие результаты. В [3,7] - доказательство матричной теоремы о лесах и свойств относительной лесной доступности, построение нормативных условий для показателей близости вершин графов. В [5,6,8] - получение представлений процедур агрегирования через показатели близости вершин графов. В [4,9] - проверка выполнения условия самосогласованной монотонности для процедур агрегирования парных сравнений. В [10] - получение преобразования метрик

в Е-близости, формулировка и доказательство теоремы о соответствии метршс и функций Е-близости для конечных множеств.