АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОПРЕДЕЛЕНИЕ. Графом называется всякая пара G = (V, U), в которой V - это конечное множество, называемое множеством вершин графа

Графом называется всякая пара G = (V, U), в которой V - это конечное множество, называемое множеством вершин графа, а U - конечное множество ребер графа.

Всякое ребро графа представляется либо одной парой вершин (а, b), либо двумя противоположными парами (a, b) и (b, a). Если ребро из U представляется только одной парой (a, b), то оно называется ориентированным ребром, ведущим из a в b. При этом a называется началом, а b -концом такого ребра.

Если ребро u представляется двумя парами (a, b) и (b, a),
то u называется неориентированным ребром. Всякое неориентированное ребро между вершинами a и b ведет как из a в b, так и обратно. При этом вершины a и b являются как началами, так и концами этого ребра. Говорят, что ребро ведет как из a в b, так и из b в a.

Всякие две вершины, которые соединяются ребром, называются смежными.

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

(В последнем случае соответствующая пара ребер будет рассматриваться как одно неориентированное ребро.)

Тогда ребра графов можно представлять просто парами вершин вида (a, b), для которых дополнительно указывается; является ли ребро ориентированным или нет. В этом случае число ребер графа совпадает с числом пар вершин, которые представляют собой ребра графа.

Поэтому в дальнейшем будем считать, что U - это множество пар вершин. При этом каждое ребро представляется одной парой вершин или двумя парами. То есть, если G = (V, U) и пара (a, b) представляет ребро графа G, то допустима запись (a, b) Î U.

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

Ребро, у которого вершины начала и конца совпадают, называется петлей.

Число ребер, выходящих из некоторой вершины a и отличных от петель, называется степенью этой вершины и обозначается как d (a). Вершина a для которой выполнено равенство d (a) = 0, называется изолированной.

Граф, все ребра которого неориентированные, называется неориентированным графом.

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

Рассмотрим пример геометрического задания графа, приведенный на рис. 5.2.:

a

b

v

e

C d

Рис. 5.2.

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

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

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

1.Списки ребер

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

Дата добавления: 2015-09-27 | Просмотры: 365 | Нарушение авторских прав