Задача остовных деревьев в k–связном графе

Введение………………………………………………………………………….2
Глава I Основные определения………………………………………………….4
§1 Основные определения теории графов……………………………………...4
§2 Матрицы смежности и инцидентности……………………………………..10
§3 Деревья………………………………………………………………………..13
Глава II Связность ………………………………………………………………18
§4 Вершинная связность и реберная вязность…………………………………18
§5 Двусвязные графы…………………………………………………………....22
§6 Теорема Менгера………………………………………………………….….32
Глава III Выделение k непересекающихся остовных деревьев
2k–реберно связном графе………………………………………………………36
§7 Построение k непересекающихся остовных деревьев………...………...…37
§8 Необходимость условия (G)2k……………………………………..….40
§9 Текст программы……….………………………………………………….…42
Вывод……………………………………………………………………………..51

Введение
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач–проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.