Лекция №8 Теоретико-множественное определение графа Раздел Графы



Дата11.10.2012
Размер65 Kb.
ТипЛекция


Лекция № 8

Теоретико-множественное определение графа

Раздел 4. Графы


1. Теоретико-множественное определение графа 1

2. Неориентированные графы 3

3. Изоморфизм графов 5

4. Отношение порядка и отношение эквивалентности на графе 5

Контрольные вопросы 5

1. Теоретико-множественное определение графа



Наглядное представление о графе можно получить, если представить себе некоторое множество точек плоскости X, называемых вершинами, и множество направленных отрезков U, соединяющих все или некоторые из вершин и называемых дугами. Математически граф G можно определить как пару множеств Х и U:

G=(Х,U). (1)

На рис.1 изображен граф, вершинами которого являются точки а, b, с, d, е, g, h, а дугами-отрезки (а, а), (с, b), (с, d), (с, е), (d, с), (d, d), (е, d), (g, h). Примерами графов являются отношения отцовства и материнства на множестве людей, карта дорог на местности, схема соединений электрических приборов, отношения превосходства одних участников турнира над другими и т.п.

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

G=(Х,Г).    (2)

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

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

ga=(a,Г) (3)

где  . (4)
 

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

(5)

где  (6)

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



Рисунок 1 - Общий вид графа

Пример 1.
Пусть G= (X, Г) - карта шоссейных дорог России. Тогда карта шоссейных дорог Ставропольского края представляет собой подграф, а карта главных дорог России - частичный граф.

Другими важными понятиями являются понятия пути и контура. Ранее было дано определение дуги как направленного отрезка, соединяющего две вершины. Дуга, соединяющая вершины а и b и направленная от а к b, обозначается u=(а, b).

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

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

(7)

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

Контур - это конечный путь m=(X1,...,Xk), у которого начальная вершина Xi совпадает с конечной Xk. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной, которые совпадают). Контур единичной длины, образованный дугой вида (а, а), называется петлей. Так, на рис. 1 (е, d, с, b)- путь, (с, е, d, с)- контур, (d, d) - петля.

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

Дугу и называют инцидентной вершине х, если она заходит в эту вершину или исходит из нее.

Обозначим через Xi, ...,Хп вершины графа, а через U1,...,Um его дуги. Введем числа:

Rij= 1, если имеется дуга, соединяющая вершину i с вершиной j;

Rij= О, если такой дуги нет.

Квадратная матрица R== [Rij] порядка n*n называется матрицей смежности графа. Введем числа:

Sij=+1, если Uj исходит из Xi,

Sij =-1, если Uj заходит в Xi,

Sij= если Uj не инцидентна Xi.

Матрица S=[Sij] порядка n*m называется матрицей инциденций для дуг графа.

Матрицы инциденций в описанном виде применимы только к графам без петель. В случае наличия в графе петель эту матрицу следует расчленить на две полуматрицы: положительную и отрицательную.


 
Рисунок 2 - Граф без петель

На рис.2 приведен граф без петель, для которого матрицы смежности и инциденции имеют вид:


2. Неориентированные графы



Иногда граф рассматривают без учета ориентации дуг, тогда его называют неориентированным графом. Для неориентированного графа понятие "дуга", "путь" и "контур" заменяются понятиями "ребро", "цепь", "цикл". Ребро - это отрезок, соединяющий две вершины. Цепь - последовательность ребер. Цикл - цепь, у которой начальная и конечная вершины совпадают.

На рис.3,а приведен пример неориентированного графа, у которого вершины обозначены цифрами, а ребра - буквами латинского алфавита.



Рисунок 3 - Неориентированные графы
Описать неориентированный граф О можно путем задания пары множеств(X, U), где Х -множество вершин; U-множество ребер. Однако более удобным является описание неориентированного графа с помощью матрицы смежности или инциденции, которые строятся аналогично соответствующим матрицам для ориентированных графов с той разницей, что не делается различия между заходящей в вершину и исходящей из нее дугами. При этом вершины x и у называют смежными, если существует соединяющее их ребро, а само это ребро называется инцидентным вершинам х и у. Для графа рис. 3,а матрицы смежности и инциденции имеют вид:



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

Для неориентированного графа понятия "подграф" и "частичный граф" аналогичны соответствующим понятиям для ориентированного графа.

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

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

Для того, чтобы определить связность ориентированного графа, не нужно обращать внимание на ориентацию дуг. Граф, изображенный на рис.1, несвязный. Однако его подграф, состоящий из вершин b, с, d, е, является связным. Для ориентированного графа, существует понятие сильной связности. Граф сильно связен, если для любых двух вершин и у, х и y) существует путь, идущий из х в у.

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



Рисунок 4 - Дерево

Если дано множество вершин a, b, c, ... , то дерево можно построить следующим образом. Одну из вершин, например а, примем за начальную и назовем её корнем дерева. Из этой вершины проводим ребра в близлежащие вершины b, с, d..., из них проводим ребра в соседние сними вершины е, f, g, h...a т. д. Таким образом, дерево можно построить, последовательно добавляя ребра в его вершинах. Это дает возможность установить связь между числом вершин и числом ребер дерева.

Простейшее дерево состоит из двух вершин, соединенных ребром. Каждый раз, когда мы добавляем еще одно ребро, в конце его прибавляется также и вершина. Следовательно, дерево с п вершинами имеет п-1 ребер.

3. Изоморфизм графов



Один и тот же граф геометрически можно изобразить различными способами. Так, на рис. 5,а приведены три изображения одного и того же графа. Такие графы называют изоморфными.

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



Рисунок 5 - Изоморфные (а) и неизоморфные (б) графы

Если какие-то из этих параметров у двух графов различны, то эти графы различны. Однако если все параметры у двух графов совпали, то это не гарантирует, что графы изоморфны. Так, на рис.5,б приведены два графа, у которых все параметры совпадают, и тем не менее они различны.

4. Отношение порядка и отношение эквивалентности на графе



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

Будем считать, что на графе G=(Х, Г) введено отношение порядка, если для любых двух вершин и у), удовлетворяющих условию x существует путь из х в у. В этом случае говорят, что вершина х предшествует вершине у или что вершина у следует за вершиной х.


Контрольные вопросы



1.Что представляет собой карта шоссейных дорог Ставропольского края по отношению к карте главных дорог России?

2.Какие графы бывают?

3. Изоморфизм графов.

4. Отношение порядка и отношение эквивалентности на графе.





Похожие:

Лекция №8 Теоретико-множественное определение графа Раздел Графы iconЭлементы теории графов.  1: Определение графа. Ориентированные и неориентированные графы
Определение 1: Совокупность двух множеств точек и линий, между элементами которых определено отношение инцидентности, называется...
Лекция №8 Теоретико-множественное определение графа Раздел Графы iconЛекция №14-15 Алгоритмы на графах Определение графа Графом
Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть "множеством вершин", а — семейством ребер...
Лекция №8 Теоретико-множественное определение графа Раздел Графы iconТема Графы Лекция Цель – познакомить студентов с основными понятиями и определениями графа и его элементов, с операциями над графами, с деревьями, лесом, бинарными деревьями, со способами задания графа и с изоморфными графами
Графом называется пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек
Лекция №8 Теоретико-множественное определение графа Раздел Графы icon1. Фрактальные и предфрактальные графы 4 Укладка фрактального графа в различные пространства 5
От того, насколько удачно изображен граф, зависит то, насколько хорошо будет воспринята информация, которую он несет. Принципы “правильного”...
Лекция №8 Теоретико-множественное определение графа Раздел Графы iconГрафы, в которых окрестности вершин – псевдогеометрические графы для
Г на множестве всех вершин, находящихся на расстоянии i от a. Положим. Если граф зафиксирован, то вместо будем писать. Для множества...
Лекция №8 Теоретико-множественное определение графа Раздел Графы iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Лекция №8 Теоретико-множественное определение графа Раздел Графы iconАлгоритм Зыкова
Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный...
Лекция №8 Теоретико-множественное определение графа Раздел Графы iconТеоретико-множественное обоснование арифметических действий целых неотрицательных чисел
Презентация учебно-методического материала для самостоятельной работы студентов (научная конференция в агу 2009 года))
Лекция №8 Теоретико-множественное определение графа Раздел Графы iconРабочая программа дисциплины "Теория конечных графов и ее приложения" Направление подготовки 010300. 62 «фиит»
Графы ориентированные и неориентированные. Изоморфизм графов. Маршруты, цепи, циклы. Деревья. Помеченные графы. Плоские и планарные...
Лекция №8 Теоретико-множественное определение графа Раздел Графы iconПояснительная записка: Требования к студентам : курс «Дискретные математические модели»
ЕН. Ф. 01. Плоские графы; эйлеровы графы; гамильтоновы графы; орграфы; сетевые графики; сети Петри
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org