URSS.ru Магазин научной книги
Обложка Ветухновский Ф.Я. Графы и сети Обложка Ветухновский Ф.Я. Графы и сети
Id: 294551
396

Графы и сети Изд. 2

2023. 64 с.
Белая офсетная бумага
  • Мягкая обложка
Элементы графа. Способы задания графа. Подграфы • Цепи. Циклы. Связность • Деревья • Эйлеровы графы. Цикломатическое число • Двухполюсные сети • Подсчет числа графов и сетей • Раскраска графов.

Аннотация

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

Для людей, которые хотят познакомиться или усовершенствовать свои знания в теории графов и сетей. (Подробнее)


Содержание
top
Предисловие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

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

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

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

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

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

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


Об авторе
top
photoВетухновский Феликс Яковлевич
Кандидат физико-математических наук. Окончил механико-математический факультет Московского государственного университета имени М. В. Ломоносова. Преподавал высшую математику (2-й Московский государственный медицинский институт имени Н. И. Пирогова, Московский государственный строительный университет).

Область научных интересов — дискретная математика, теория графов.