Методы лапласовской теории орграфов в структурном анализе систем

Методы лапласовской теории орграфов в структурном анализе систем

Автор: Чеботарев, Павел Юрьевич

Шифр специальности: 05.13.01

Научная степень: Докторская

Год защиты: 2008

Место защиты: Москва

Количество страниц: 306 с. ил.

Артикул: 4398332

Автор: Чеботарев, Павел Юрьевич

Стоимость: 250 руб.

Методы лапласовской теории орграфов в структурном анализе систем  Методы лапласовской теории орграфов в структурном анализе систем 

Введение
Глава I. Матричная теорема о лесах
1.1. Необходимые определения простые факты
1.1.1. Общие понятия теории графов.
1.1.2. Структура орграфа.
1.1.3. Деревья и леса
1.1.4. Лапласовская матрица и матрица Кирхгофа.
1.2. Матричная теорема о деревьях и связанные с ней исследования
1.2.1. Некоторые направления в исследовании лапласовских матриц графов
1.2.2. Матричные теоремы о деревьях для неориентированных и ориентированных графов
1.3. Матричная теорема о лесах
1.4. Доказательства матричной теоремы о лесах.
1.4.1. Первое доказательство.
1.4.2. Второе доказательство.
Глава 2. О нахождении собственного проектора и компонент матрицы
2.1. Введение .
2.1.1. О приложениях обобщенно обратной матрицы по Дразину, собственного проектора и компонент матрицы.
2.1.2. Определения.
2.1.3. Вспомогательные утверждения.
2.1.4. О задачах, решаемых в данной главе .
2.2. Характеризации собственного проектора.
2.3. Вычисление собственного проектора Л
с помощью аннулирующего многочлена для Ли
2.4. Нахождение компонент матрицы и се минимального многочлена
2.5. Собственный проектор и компоненты матрицы, собственные значения
которой известны
Глава 3. Исследование матрицы максимальных исходящих лесов орграфа
3.1. Введение
3.2. Простейшие свойства остовиых исходящих лесов.
3.3. Максимальные исходящие леса, базы и недоминируемые узлы .
3.4. Конструктивное описание максимальных исходящих лесов.
3.5. Матричные теоремы о лесах в параметрической форме
3.6. Матрица максимальных исходящих лесов
3.7. Цени Маркова, связанные с орграфом, и матричная теорема о деревьях
для цепей Маркова
3.8. Матрицы лесов и задача структурирования орграфа
Глава Л. Остовные леса орграфа и связанные с ними матрицы
4.1. Введение
4.2. Некоторые свойства исходящих и входящих лесов
4.3. Матрицы исходящих лесов и переходные вероятности цепей Маркова . .
4.4. Выражение матриц лесов через матрицу Кирхгофа и его следствия .
4.5. О некоторых линейных операторах, связанных с орграфом
4.6. сев.дообратная и групповая обратная матрицы для матрицы Кирхгофа
4.7. Об области Гершгорина и аннулирующем многочлене матрицы Кирхгофа
Глава 5. Исследование лапласовского спектра орграфов
5.1. Введение .
5.2. Некоторые свойства лапласовского спектра неориентированного графа .
5.3. О связях лапласовских и стохастических матриц
5.4. Связь спектров лапласовских и стохастических матриц .
5.5. Область, содержащая лапласовекие спектры.
5.6. Многоугольник лапласовских собственных значений.
5.7. Об асимптотических свойствах лапласовских спектров.
5.8. Согласование характеристик в многоагентных системах и спектры ла
пласовских матриц орграфов.
5.8.1. Децентрализованное управление многоагентными системами
5.8.2. Непрерывная модель распределенного согласования характеристик .
5.8.3. Сходимость процесса согласования.
5.8.4. Ранг лапласовской матрицы и критерий сходимости процесса согласования
5.8.5. Итерационная модель распределенного согласования характеристик
5.8.6. Другие задачи децентрализованного управления.
Глава 6. Структурные индексы графов и агрегирование результатов
парных сравнений
6.1. Об агрегировании неполных предпочтений
6.2. Понятия и обозначения, связанные с агрегированием предпочтений . . .
6.3. Пример
6.4. Самосогласованная монотонность
6.5. Процедуры, основанные на индивидуальных оценках
6.6. Совокупные процедуры оценивания
6.6.1. Процедура Уэя.
6.6.2. Процедуры Хассе и Рамануяхариулу
6.6.3. Процедура КацаТомпсонаТейлора.
6.6.4. Процедура направленных деревьев.
6.6.5. Подробнее о процедуре направленных деревьев
6.7. Класс процедур, не удовлетворяющих самосогласованной монотонности .
6.8. Процедуры, однородные к победам и поражениям
6.8.1. Процедура наименьших квадратов.
6.8.2. Обобщенная процедура суммы очков.
6.9. Достаточное условие самосогласованной монотонности.
6 Четыре процедуры, удовлетворяющие самосогласованной монотонности
6 О двух дополнительных аксиомах
. Независимость спмакровершины.
. Сохранение баланса при разбиении.
Глава 7. Агрегирование предпочтений обобщенным методом суммы очков
7.1. Введение
7.2. Обобщение метода суммы очков.
7.3. Свойства обобщенных сумм очков.
7.4. Статистические модели
7.4.1. Гребневые оценки для модели Шеффе.
7.4.2. Байесовская модель .
7.5. Случай парных сравнений с ограниченным результатом.
7.6. Использование обобщенного метода суммы очков для агрегирования числовых оценок объектов
7.7. О выборе параметра е.
7.8. Примеры .
Глава 8. Меры связанности вершин графов, их свойства и характеристические условия
8.1. О приложениях структурных индексов графов .
8.1.1. Транспортные сети.
8.1.2. Химическая информатика, наукометрия, семантические сети
8.1.3. Социальные сети.
8.1.4. Структурные индексы графов в социометрии
8.2. Нормативные свойства показателей связанности
8.3. Исследование простейших показателей связанности вершин графов . . .
8.3.1. Путевая достижимость.
8.3.2. Надежность связи как мера связанности вершин.
8.3.3. Величина максимального потока минимального разреза как мера связанности вершин .
8.3.4. Маршрутная достижимость
8.3.5. Метризуемость близости.
8.4. К формализации понятия близости функции Еблизости.
8.5. Достижимость, двойственная классическому расстоянию на графе
Глава 9. Меры связанности вершин графов, построенные с помощью
матричной теоремы о лесах
9.1. Свойства относительной лесной доступности для мультиграфов
9.2. Свойства относительной лесной доступности для мультиорграфов
9.3. Составляющие относительной лесной доступности .
9.4. Достижимость по густым лесам, связанная с обобщенным обращением лапласовской матрицы графа
9.5. Об особенностях показателей близости вершин графов.
9.0. Продолжение исследования показателей близости, связанных с классификацией лесов, в случае орграфов
9.6.1. Вес максимальных исходящих лесов как показатель близости вершин орграфа .
9.6.2. Относительная лесная доступность параметрический случай
9.6.3. Достижимость по густым лесам
9.7. Относительная лесная доступность и производные структурные индексы
в задачах социометрии .
9.8. Особенности показателей близости не примере фрагмента транспортной
Глава . Свойства лесной метрики графа
.1. Введение
.2. Изменение приведенного лесного расстояния между вершинами при усилении их связи.
.3. Соотношение лесных расстояний для пары графов, отличающихся одним ребром.
.4. Интерпретация лесной метрики графа
.5. О связи лесной метрики и резисторной метрики графа
Заключение
Список литературы


В 4 Кельмаис и Челноков показали, что коэффициенты лапласовского характеристического многочлена могут быть выражены через количества остовных лесов мультиграфа С с фиксированным числом компонент. Этот результат используется в одном из доказательств матричной теоремы о лесах, приведенных далее в этой главе. Другой близкий результат был независимо получен Кроуэллом 1 и Фидлером и Седлачеком 9, переоткрыт в , заново доказан в 4 и обобщен в ,9,1,7. Рассмотрим матрицу С Ь2 1,7, где X, XI Ьй лапласовская характеристическая матрица мультиграфа 6 единичная матрица. Суть матричной теоремы о лесах, о которой речь пойдет ниже, состоит в том, что определитель всегда ненулевой матрицы ИС и обратная к ней матрица могут быть использованы для подсчета остовных корневых лесов мультиграфа С напомним, что корневой лес граф, слабыми компонентами которого являются корневые деревья. Данный результат является естественным продолжением матричной теоремы о деревьях, согласно которой миноры матрицы ЬС могут бы ть использованы для подсчета остовных деревьев. Существует определенный параллелизм между теоремами о деревьях и результатами, касающимися характеристической матрицы, построенной по матрице смежности графа см. Разделы 1. Кастлейна 0 и Понстейна 4, а также 6. О перечислении лесов см. Лиу и Чоу 5 получили довольно сложное выражение для для количества Акомпонентных остовных лесов графа через главные миноры лапласовской матрицы. Мирволд 3 дала более простое теоретикографовое доказательство одной из версий их результата и предложила полиномиальный алгоритм для подсчета количества ккомпонентных остовных лесов. Идеи ее доказательства сходны с идеями некоторых доказательств Кельмаиса и Челнокова 4. У. Татта см. Обозначим через V алгебраическое дополнение элемента 4 в ЬС, где ЬС7 лапласовская матрица взвешенного мультиграфа С. Пусть Тб Т множество всех остовных деревьев С. Теорема 1. Для любого взвешенного мультиграфа С и для любых Д V С имеет место Д Т. Здесь еТ вес множества Т см. Татт доказал также аналогичный результат для взвешенных мультиорграфов. Теорема 1. Для любого взвешенного мультиорграфа Г и для любых Д I7Г имеет место Т. Элементы различных строк Ь могут иметь разные алгебраические дополнения, но алгебраические дополнения всех элементов одной строки равны. Согласно теореме 1. Г, исходящих из г. Для простоты Татт формулирует эти теоремы только дня алгебраических дополнений Ь V диагональных элементов. Ориентированная матричная теорема о деревьях с произвольными Д приведена в . Если веса всех ребер дуг равны 1, то теоремы 1. Для алгебраических дополнений элементов лапласовской матрицы взвешенного мультиорграфа справедлив результат, вполне аналогичный теореме 1. Пусть Т1 множество остовных входящих деревьев мультиорграфа Г, входящих в г, а Ь1 алгебраическое дополнение элемента у в Ь. Теорема 1. Матричная теорема о лесах формулируется для мультиграфов и мультиорграфов. I единичная матрица, С мультиграф, Г мультиорграф. Пусть ТС Т множество всех остовных корневых лесов мультиграфа 6 а Т множество тех остовных корневых лесов в 6, в которых 1 и принадлежат одному дереву с корнем г. Пусть XV XV С, И И,. Лемма 1. УС имеет место Уг еР3. Нискольку матрица XV взвешенного мультиграфа симметрична пункт 2 леммы 1. Напомним обозначения, введенные в подразделе 1. Пусть XV И7Г, Цп Й7Г и И ИГ. Пусть IV аф XV И1 присоединенная матрица для матрицы XV. И Ув I ,, ЩГ I Г, 1УГ ДГ,
1. ИГ. Лемма 1. Я Я. У1 Ь 1. М 1 1 а
1. XV У1Т и У И1 присоединенные матрицы для И7 и IV. Матричная теорема о лесах ,8 является следствием лемм 1. Теорема 1. Для любого взвешенного мультиграфа существует матрица С И1 и Яц еЯеЯ гЯЧеП м 1, п. При единичных весах всех ребер дуг веса множеств остовных лесов в леммах 1. Матричная теорема о лесах позволяет рассматривать О, И и И как матрицы относительных доступностей по лесам или относительных лесных доступностей кратко доступностей вершин С или Г. Эти величины могут использоваться в качестве меры близости чем дальше от , тем меньше и дхз вершин, что подтверждается их свойствами, которые будут рассмотрены в главе 9.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.262, запросов: 244