Главная > Теория графов. Алгоритмический подход
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

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

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

Глава 1. ВВЕДЕНИЕ

1. Графы. Определение

Граф задается множеством точек или вершин (которое обозначается через X) и множеством линий или ребер (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф полностью задается (и обозначается) парой

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

В этой книге, когда дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т. е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. обозначение относится к дуге а к дуге

Другое, употребляемое чаще описание ориентированного графа состоит в задании множества вершин X и соответствия которое показывает, как между собой связаны вершины. Соответствие называется отображением множества а граф в этом случае обозначается парой

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

Рис. 1.1. (см. скан) (а) Ориентированный граф. (б) Неориентированный граф. (в) Смешанный граф.

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

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

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

Вполне очевидно, что для неориентированного графа для всех

Когда отображение действует не на одну вершину, а на множество вершин то под понимают объединение

т. е. является множеством таких вершин что для каждой из них существует дуга в где Для графа, приведенного на рис.

Отображение записывается как Аналогично «тройное» отображение записывается как Для графа, показанного на рис. имеем:

Аналогично понимаются обозначения

1
Оглавление
email@scask.ru