Спектры графов. Теория и применение

Обложка......Page 1
Титульный лист оригинального издания......Page 2
Титульный лист......Page 3
Аннотация и выходные данные......Page 4
Предисловие к переводу......Page 5
Предисловие авторов......Page 7
§ 0.1. Что такое спектр графа и что о нем говорится в этой книге......Page 9
§ 0.2. Еще несколько теоретико-графовых понятий и обозначений......Page 13
§ 0.3. Некоторые теоремы теории матриц и их применение к исследованию спектров графов......Page 16
§ 1.1. Матрица смежности и обыкновенный спектр графа......Page 22
§ 1.2. Общий метод определения различных типов спектров графа......Page 24
§ 1.3. Некоторые замечания о рассматриваемых спектрах......Page 28
§ 1.4. Коэффициенты многочлена $P_G(\lambda)$......Page 30
§ 1.5. Коэффициенты многочлена $C_G(\lambda)$......Page 36
§ 1.6. Коэффициенты многочлена $Q_G(\lambda)$......Page 39
§ 1.7. Формула, связывающая цикловидную и древовидную структуры регулярного или полурегулярного мультиграфа......Page 41
§ 1.8. О числе маршрутов......Page 43
§ 1.9. Другие результаты и задачи......Page 46
§ 2.1. Многочлен графа......Page 53
§ 2.2. Спектр дополнения, прямой суммы и полного произведения графов......Page 55
§ 2.3. Процедуры сведения для вычисления характеристического многочлена......Page 61
§ 2.4. Реберные и тотальные графы......Page 63
§ 2.5. NEP-сумма и булевы функции......Page 68
§ 2.6. Определение характеристических многочленов и спектров графов некоторых специальных типов......Page 75
§ 2.7. Другие результаты и задачи......Page 80
§ 3.1. Орграфы......Page 84
§ 3.2. Графы......Page 88
§ 3.3. Регулярные графы......Page 98
§ 3.4. Некоторые замечания о сильно регулярных графах......Page 107
§ 3.5. Собственные векторы......Page 108
§ 3.6. Другие результаты и задачи......Page 116
§ 4.1. Понятие делителя......Page 121
§ 4.3. Обобщение понятия делителя......Page 123
§ 4.4. Свойства симметрии и делители графов......Page 124
§ 4.5. Основная лемма о делителе и спектре......Page 126
§ 4.6. Факторизация характеристического многочлена с помощью делителя......Page 129
§ 4.7. Структура—делитель—спектр......Page 132
§ 4.8. Другие результаты и задачи......Page 135
§ 5.1. Симметрия и простые собственные значения......Page 139
§ 5.2. Спектр и представления группы автоморфизмов......Page 146
§ 5.3. Передний делитель, индуцированный подгруппой группы автоморфизмов......Page 156
§ 5.4. Коспектральные графы с заданными (различными) группами автоморфизмов......Page 159
§ 5.5. Другие результаты и задачи......Page 160
§ 6.1. Некоторые семейства неизоморфных коспектральных графов......Page 164
§ 6.2. Характеризация графа с помощью его спектра......Page 169
§ 6.3. Характеризация и другие спектральные свойства реберных графов......Page 177
§ 6.4. Метрически регулярные графы......Page 188
§ 6.5. Матрица (—1,1,0)-смежности и переключение Зайделя......Page 194
§ 6.6. Другие результаты и задачи......Page 196
§ 7.1. Существование и несуществование некоторых комбинаторных объектов......Page 200
§ 7.2. Сильно регулярные и транзитивные по расстоянию графы......Page 205
§ 7.3. Равноугольные прямые и два-графы......Page 211
§ 7.4. Связность и двудольность некоторых произведений графов......Page 216
§ 7.5. Определение числа маршрутов......Page 222
§ 7.6. Определение числа остовных деревьев......Page 230
§ 7.7. Экстремальные задачи......Page 234
§ 7.8. Другие результаты и задачи......Page 237
§ 8.1. Теория Хюккеля......Page 244
§ 8.2. Графы, связанные с бензоидными углеводородами......Page 254
§ 8.3. Задача о димерах......Page 260
§ 8.4. Колебания мембраны......Page 267
§ 8.5. Другие результаты и задачи......Page 274
§ 9.1. Собственные значения и вложения......Page 277
§ 9.2. Характеристический многочлен матрицы расстояний......Page 280
§ 9.3. Алгебраическая связность графа......Page 282
§ 9.5. Некоторые нерешенные задачи......Page 283
Приложение. Таблицы спектров графов......Page 285
Список литературы......Page 338
Указатель обозначений......Page 373
Именной указатель......Page 374
Предметный указатель......Page 377
ОГЛАВЛЕНИЕ......Page 382
Выходные данные......Page 384