Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 3 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

СОДЕРЖАНИЕ
ВВЕДЕНИЕ .................................................................................................................5
1. ГРАФЫ И СПОСОБЫ ИХ ПРЕДСТАВЛЕНИЯОШИБКА! ЗАКЛАДКА НЕ ОПРЕДЕЛЕНА.
1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ............................... ОШИБКА! ЗАКЛАДКА НЕ ОПРЕДЕЛЕНА.
1.2 СПОСОБЫ ОПИСАНИЯ ГРАФОВ................................................................................. 10
1.2.1. Теоретико-множественное представление графов .............................. 10
1.2.2. Задание графов соответствием ............................................................. 10
1.2.3. Матричное представление графов.......................................................... 10
1.3 ОПЕРАЦИИ НАД ГРАФАМИ........................................................................................ 14
2. ДОСТИЖИМОСТЬ И СВЯЗАНОСТЬ В ГРАФАХ ................................................. 17
2.1.МНОГОЗНАЧНЫЕ ОТОБРАЖЕНИЯ ............................................................................. 17
2.1.1.Прямые отображения.................................................................................. 17
2.1.2. Обратные отображения............................................................................ 17
2.2. ТРАНЗИТИВНЫЕ ЗАМЫКАНИЯ.................................................................................. 20
2.2.1. Прямое транзитивное замыкание............................................................ 20
2.2.2. Обратное транзитивное замыкание ....................................................... 21
2.2.3.Нахождение транзитивных замыканий по матрице смежности........... 21
2.3 ДОСТИЖИМОСТЬ И КОНТРДОСТИЖИМОСТЬ............................................................. 25
3. ГРАФЫ И ПОДГРАФЫ.......................................................................................... 29
3.1
ТИПЫ ГРАФОВ. ....................................................................................................... 29
3.1.1.Теорема о двудольности............................................................................. 31
Доказательство. .................................................................................................. 32
3.2.ВИДЫ ПОДГРАФОВ .................................................................................................. 36
3.3.С
ИЛЬНО СВЯЗНЫЕ ГРАФЫ И КОМПОНЕНТЫ ГРАФА..................................................... 40
4. МЕТОДЫ РАЗБИЕНИЯ ГРАФА НА МАКСИМАЛЬНЫЕ СИЛЬНО СВЯЗНЫЕ
ПОДГРАФЫ ................................................................................................................ 45
4.1 МЕТОД МАЛЬГРАНЖА....................................................................................... 45
4.2.
МАТРИЧНЫЙ МЕТОД РАЗБИЕНИЯ ............................................................................ 51
5.ПУТИ И ЦИКЛЫ В ГРАФАХ .................................................................................... 54
5.1.П
УТИ И МАРШРУТЫ ................................................................................................. 54
5.2 МАТРИЧНЫЙ МЕТОД НАХОЖДЕНИЯ ПУТЕЙ В ГРАФАХ ................................................. 55 
                                                     СОДЕРЖАНИЕ

ВВЕДЕНИЕ .................................................................................................................5

1. ГРАФЫ И СПОСОБЫ ИХ ПРЕДСТАВЛЕНИЯОШИБКА! ЗАКЛАДКА НЕ ОПРЕДЕЛЕНА.

  1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ............................... ОШИБКА! ЗАКЛАДКА НЕ ОПРЕДЕЛЕНА.
  1.2 СПОСОБЫ ОПИСАНИЯ ГРАФОВ ................................................................................. 10
     1.2.1. Теоретико-множественное представление графов .............................. 10
     1.2.2. Задание графов соответствием ............................................................. 10
     1.2.3. Матричное представление графов.......................................................... 10
  1.3 ОПЕРАЦИИ НАД ГРАФАМИ ........................................................................................ 14

2. ДОСТИЖИМОСТЬ И СВЯЗАНОСТЬ В ГРАФАХ ................................................. 17

  2.1.МНОГОЗНАЧНЫЕ ОТОБРАЖЕНИЯ ............................................................................. 17
     2.1.1.Прямые отображения.................................................................................. 17
     2.1.2. Обратные отображения............................................................................ 17
  2.2. ТРАНЗИТИВНЫЕ ЗАМЫКАНИЯ .................................................................................. 20
     2.2.1. Прямое транзитивное замыкание............................................................ 20
     2.2.2. Обратное транзитивное замыкание ....................................................... 21
     2.2.3.Нахождение транзитивных замыканий по матрице смежности........... 21
  2.3 ДОСТИЖИМОСТЬ               И КОНТРДОСТИЖИМОСТЬ ............................................................. 25

3. ГРАФЫ И ПОДГРАФЫ.......................................................................................... 29

  3.1 ТИПЫ ГРАФОВ. ....................................................................................................... 29
     3.1.1.Теорема о двудольности............................................................................. 31
     Доказательство. .................................................................................................. 32
  3.2.ВИДЫ ПОДГРАФОВ .................................................................................................. 36
  3.3.СИЛЬНО СВЯЗНЫЕ ГРАФЫ И КОМПОНЕНТЫ ГРАФА ..................................................... 40

4. МЕТОДЫ РАЗБИЕНИЯ ГРАФА НА МАКСИМАЛЬНЫЕ СИЛЬНО СВЯЗНЫЕ
ПОДГРАФЫ ................................................................................................................ 45

  4.1 МЕТОД МАЛЬГРАНЖА ....................................................................................... 45
  4.2. МАТРИЧНЫЙ МЕТОД РАЗБИЕНИЯ ............................................................................ 51

5.ПУТИ И ЦИКЛЫ В ГРАФАХ .................................................................................... 54

  5.1.ПУТИ И МАРШРУТЫ ................................................................................................. 54
  5.2 МАТРИЧНЫЙ МЕТОД НАХОЖДЕНИЯ ПУТЕЙ В ГРАФАХ ................................................. 55

Страницы