Дискретная математика: графы и автоматы. Альпин Ю.А - 3 стр.

                                  Оглавление


Глава    1. Неориентированные графы . . . . . . . . . . . . . . . . . . .               4
  § 1.    Первые понятия теории графов . . . . . . . . . . . . . . . . . . . .          4
  § 2.    Эйлеровы и гамильтоновы графы . . . . . . . . . . . . . . . . . . .          10
  § 3.    Деревья. Минимальные остовы графов . . . . . . . . . . . . . . . .           14
  § 4.    Листы и деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    17
  § 5.    Теорема о свадьбах, двудольные графы и (0,1)-матрицы . . . . . .             19

Глава 2. Ориентированные графы . . . . . . . . . . . . . . . . . . . . .               24
  § 1. Взаимодостижимость, компоненты и конденсация . . . . . . . . .                  24
  § 2. Нормальная форма матрицы смежности
       приводимого графа . . . . . . . . . . . . . . . . . . . . . . . . . . .         28
  § 3. Арифметические свойства сильно связного графа. Циклические
       классы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     30
  § 4. Примитивные графы и матрицы . . . . . . . . . . . . . . . . . . . .             37
  § 5. Некоторые алгоритмические вопросы . . . . . . . . . . . . . . . . .             38
  § 6. Цепи Маркова . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        40

Глава    3. Задача о максимальном потоке в сети              . . . . . . . . . . . .   49
  § 1.    Основные леммы о потоках и разрезах в сети        . . . . . . . . . . . .    49
  § 2.    Нахождение максимального потока: алгоритм         и теорема . . . . . .      51
  § 3.    Приложения теоремы о потоках . . . . . . . .      . . . . . . . . . . . .    56

Глава   4. Теория автоматов . . . . . . . . . . . . . . . . . . . . . . . . . .        60
  § 1.   Буквы, слова, языки, автоматы. . . . . . . . . . . . . . . . . . . . .        60
  § 2.   Критерий распознаваемости языка конечным автоматом . . . . .                  63
  § 3.   Единственность минимального автомата . . . . . . . . . . . . . . .            67
  § 4.   Признаки нераспознаваемости языка
         конечным автоматом . . . . . . . . . . . . . . . . . . . . . . . . . .        69
   § 5. Свойства операций над языками . . . . . . . . . . . . . . . . . . . .          71
   § 6. Синтаксический моноид . . . . . . . . . . . . . . . . . . . . . . . .          74
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     78