Графы, Основные определения, Селезнева С.Н.

Графы, Основные определения, Селезнева С.Н.

Фрагмент из книги:
Граф, в котором допускаются и петли, и кратные ребра иногда называется псевдографом.
Граф без петель, но, возможно, с кратными ребрами называется мультиграфом.
Граф без петель и кратных ребер называется простым, или обыкновенным графом.
Мы будем, как правило, рассматривать простые графы, т.е. графы без петель и кратных ребер. Дальнейшие определения будут вводится, в основном, только для таких графов.




Остовные деревья.
Остовным деревом связного графа G называется его подграф D со всеми вершинами, являющийся деревом.

Предложение 7. В каждом связном графе G = (V, Е) найдется остовное дерево.
Доказательство (1-й способ). Если в графе G нет циклов, то он является своим остовным деревом.

Иначе, рассмотрим в графе G цикл. Пусть е —  ребро из этого цикла. Повторим рассуждения для графа G —  е, который также является связным.

Т.к. на каждом шаге мы разрываем хотя бы один цикл графа G, а циклов конечное число, то через конечное число шагов мы получим дерево. Оно и есть остовное дерево графа G.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Графы, Основные определения, Селезнева С.Н. - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Селезнева