Ветухновский Ф.Я. Графы и сети Изд. 2

---

Предисловие				3
Глава I. Графы				3
§ 1. Элементы графа. Способы задания графа. Подграфы				3
§ 2. Цеди, Циклы. Связность				7
§ 3. Деревья				9
§ 4. Эйлеровы (четные) графы. Цикломатическое число				12
Глава II. Двухполюсные сети				14
§ 5. Сети. Цепи в сетях. Соединения сетей				14
§ 6. Потоки в сетях				16
§ 7. Сильно связные сети и несепарабельные графы				28
§ 8. Каноническое разложение сетей				32
Глава III. Подсчет числа графов и сетей				40
§ 9. Некоторые простые оценки				40
§ 10. Подсчет числа деревьев				42
§ 11. Оценки числа графов и сетей с р ребрами				44
Глава IV. Раскраска графов				49
§ 12. Хроматическое число и хроматический класс				49
§ 13. Раскраска вершин				49
§ 14. Раскраска ребер				54
Литература				60

---

Язык и методы теории графов используются для описания и исследования структурных (комбинаторных) свойств управляющих систем. В настоящее время на русском языке имеется несколько руководств по теории графов [1, 3, 6, 9]. Поэтому в задачу автора не входило представить многочисленные направления теории графов, и многие важные вопросы здесь не рассматриваются.

Цель настоящей книги дать некоторые основные сведения, и главное, продемонстрировать методы теории графов и сетей, а также изложить отдельные специальные вопросы. Все вопросы, включенные в рассмотрение, изложены с полными доказательствами, так что чтение не требует обращения к литературе.

К особенностям работы можно отнести следующее:

1. При изложении отдельных тем были заимствованы фрагменты ряда работ: Элайеса, Фейнстейна и Шеннона [11 ], Трахтен-брота [7] в главе II, Лупанова [4, 5] в главе III. Следует также отметить использование работ Форда и Фалкерсона [8], Ви-зинга [2] и Зыкова [3].

2. Довольно большое внимание, например, по сравнению с монографиями по теории графов уделено теории сетей.

3. Намеренно подчеркивается та роль, которую в теории графов играет класс деревьев. С этой целью в доказательстве некоторых утверждений используются свойства Деревьев, хотя возможны и другие доказательства.

---