Основные понятия теории графов

Учебное пособие

Основы биоэкологии

Марина Валерьевна Леган

Редактор Н.В. Городник

Выпускающий редактор И.П. Брованова

Дизайн обложки А.В. Ладыжская

Компьютерная верстка В.Ф. Ноздрева

Подписано в печать 19.11.2007. Формат 60´84 1/16. Бумага офсетная. Тираж 100 экз.
Уч.-изд. л. 2,09. Печ. л. 2,25. Изд. № 225. Заказ №. Цена договорная

Отпечатано в типографии
Новосибирского государственного технического университета
630092, г. Новосибирск, пр. К. Маркса, 20

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

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

Определение 1. Неориентированным графом (графом) называется совокупность непустого множества – множества вершин и множества - множества ребер, т.е. неупорядоченных пар различных элементов множества.

Число вершин графа обозначается. Число ребер графа обозначается.

Если – вершины графа, т. е. и – соединяющее их ребро, то есть, тогда вершина и ребро называются инцидентными. Два ребра, инцидентных одной вершине, называются смежными ребрами. Две вершины, инцидентные одному ребру, называются смежными вершинами.

Количество ребер, инцидентных вершине, называется степенью (валентностью) вершины и обозначается.

Определение 2. Ориентированным графом (орграфом) называется совокупность непустого множества – множества вершин и множества E – множества дуг, т.е. упорядоченных пар различных элементов множества.

Вершина дуги называется её началом, а вершина — концом. При этом говорят, что дуга исходит из вершины и заходит в вершину.

В орграфе число дуг, исходящих из вершины v называется полустепенью исхода и обозначается. Число дуг, входящих в v – полустепенью захода и обозначается.

Смежность и инцидентность вершин и дуг, степень дуг орграфа, определяется так же, как для вершин и ребер графа.

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

Рис 1. а) граф, б) орграф

Определение 3. Псевдографом (псевдоорграфом) называется совокупность непустого множества и множества неупорядоченных (упорядоченных) пар элементов из необязательно различных.

Ребро (дуга)псевдографа (псевдоорграфа) назывется петлей.

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

в)

Рис 2. а) псевдограф, – петля, б) мультиграф, - кратное ребро, в) псевдомультиорграф.

Дата добавления: 2014-01-04