Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Определение графа

Читайте также:
  1. I.2 Определение понятия фразеологизма
  2. II. Оснащение транспортных средств тахографами
  3. III. ОПРЕДЕЛЕНИЕ ЭФФЕКТИВНОСТИ ПРОИЗВОДСТВА
  4. А) ВЕРБАЛЬНОСТЬ КАК ОПРЕДЕЛЕНИЕ ГЕРМЕНЕВТИЧЕСКОГО ПРЕДМЕТА
  5. А) Определение расчетных усилий в ветвях колонны
  6. А) Определение требуемой площади поперечного сечения колонны.
  7. А) ПОНЯТИЕ ЖИЗНИ У ГУССЕРЛЯ И ГРАФА ЙОРКА

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

Определение графа

 

 

Рассмотрим множество Х, состоящее из соединенных некоторым образом точек. Элементы - вершины графа. Граф G=G(X) с множеством вершин Х есть некоторое семейство сочетаний или пар вида

указывающие, какие вершины считаются соединенными.

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

Можно определить понятие графа иначе, если представить себе некоторое множество точек плоскости Х, называемых вершинами, и множество направленных отрезков D, соединяющих все или некоторые из вершин и называемых дугами. Т.е. математически граф G можно определить как пару множеств G=(X, D). Примерами графа может являться карта автомобильных или железных дорог, схемы соединения электрических цепей и т.п.

Можно считать, что множество направленных дуг D, соединяющих элементы множества Х, отображают это множество само в себя. Поэтому можно считать граф заданным, если дано множество его вершин Х и способ отображения Г множества Х в Х. Таким образом, граф G есть пара (Х, Г), состоящая из множества Х и отображения Г, заданного на этом множестве.

G=(Х, Г). (2.1)

Так, рис. 2.1 изображен граф, вершинами которого являются точки a, b, c, d, e, g, h, а дугами – отрезки (a, a), (c, b), (c,d), (c, e), (d, c), (d, d), (e, d), (g, h). Отображение приведенного графа будет определяться следующим образом: Га=а; Гb=Æ; Гс={b, d, e}; Гd={d,c}; Ге=d; Гg=h; Гh=Æ.

Рис. 2.1

 

Нетрудно видеть, что данное определение графа полностью совпадает с определением отношения на множестве.

В определении ребра можно принимать или не принимать во внимание порядок расположения двух его концов. Если этот порядок несуществен, т.е. если , то D есть неориентированное ребро, если же порядок существен, то D называют ориентированным ребром, и при этом хi –начальная вершина, – конечная вершина.

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

неориентированный граф ориентированный граф

Рис. 2.2

 

В ряде случаев имеет место смешанные графы.

Как в случае ориентированного, так и неориентированного ребра говорят, что ребро D=(хi, xj) инцидентно вершинам xi и xj, а также, что xi и xj инцидентны ребру D. Вершина, не инцидентная никакому ребру, называется изолированной. Часто имеет смысл учитывать только неизолированные вершины.

Граф, состоящий только из изолированных вершин, называется нуль-графом.

Наиболее важным случаем является полный граф G=(X, D), ребрами которого являются всевозможные пары () для двух различных вершин хi и xj из Х. На рис. 2.3 приведены полные графы.

Рис. 2.3

В ориентированном полном графе имеются пары ребер, по одному в каждом направлении, соединяющие любые две различные вершины xi и xj. Ребра, у которых обе концевые точки совпадают L=(a, a) называются петлей.

(См. рис. 2.1 вершины “а”, “d”). Петля обычно считается неориентированной. Можно расширить полный граф до полного графа с петлями, добавляя петлю в каждой вершине.

Допускается, чтобы пара вершин соединялась несколькими различными ребрами.

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

Для каждого ориентированного графа существует также соотнесенный неориентированный граф Gu, ребрами которого являются ребра графа G, но уже без ориентации. Иногда удобно превратить неориентированный граф G в ориентированный граф Gd при помощи процесса удвоения, состоящего в замене каждого ребра G парой ребер с теми же вершинами и приписыванием им (ребрам) противоположных ориентаций.

Граф называется плоским если он может быть изображен на плоскости так, что все пересечения ребер являются вершинами G.

Подграфом GA графа G=(X, Г) называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с дугами, соединяющими эти вершины. Например, очерченная пунктиром область на рис. 2.1. Математически это записывается следующим образом:

GA=(A, ГА), (2.2)

где

(2.3)

Частичным графом GD по отношению к графу G=(X, Г) называется граф, содержащий только часть дуг графа G, т.е. определяемый условием

GD=(X, D), (2.4)

где

Например, если G=(Х, Г) – карта автомобильных дорог России. Тогда карта дорог Нижегородской области представляет собой подграф, а карта главных автомагистралей России – частичный граф.

Путем в графе G называют такую последовательность дуг d=(u1, u2, …uk), в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь d, последовательными вершинами которого являются вершины a, b, c, … m обозначается через d=(a, b, c, … m).

Длиной пути d=(u1, u2, … uk) называют число l(d)=k, равное числу дуг, составляющих путь d. Иногда каждой дуге ui приписывают некоторое число l(ui), называемое длиной дуги. Тогда длина пути определяется как сумма длин дуг, составляющих путь

. (2.5)

Путь, в котором никакая дуга не встречается дважды, называется простым. Путь, в котором никакая вершина не встречается дважды, называется элементарным.

Контур – это конечный путь d=(x1, x2, … xk), у которого начальная вершина х1 совпадает с конечной xk. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной, которые совпадают). Контур единичной длины, образованный дугой вида (а, а), называется петлей. Так, на рис. 2.1 (e, d, c, b) – путь, (с, e, d, c) – контур, (d, d) –петля.

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

 


Дата добавления: 2015-10-13; просмотров: 115 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Предмет теории графов| Матричные представления графа

mybiblioteka.su - 2015-2024 год. (0.008 сек.)