ВУЗ:
Составители:
Рубрика:
СОДЕРЖАНИЕ
ВВЕДЕНИЕ .................................................................................................................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