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

По кнопкам "Купить бумажную книгу" или "Купить электронную книгу" можно купить в официальных магазинах эту книгу, если она имеется в продаже, или похожую книгу. Результаты поиска формируются при помощи поисковых систем Яндекс и Google на основании названия и авторов книги.

Наш сайт не занимается продажей книг, этим занимаются вышеуказанные магазины. Мы лишь даем пользователям возможность найти эту или похожие книги в этих магазинах.

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

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

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

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


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

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

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

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



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

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



Скачать - pdf - Яндекс.Диск.
Дата публикации:





Теги: :: ::


Следующие учебники и книги:
Предыдущие статьи:


 


 

Книги, учебники, обучение по разделам




Не нашёл? Найди:





2025-04-26 00:02:37