Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Графом называется непустое конечное множество вершин

Введение.

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736 г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно ее приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем электрических цепей и молекулярных схем. В настоящее время можно указать главы чистой математики, например теория математических отношений, в которых теория графов служит естественным аппаратом; с другой стороны, эта теория находит многочисленные применения в многообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов и, вообще, в так называемом «программировании». Теория графов теперь применяется и в таких областях, как экономика, психология и биология. Математические развлечения и головоломки тоже остаются частью теории графов, особенно если отнести к ним знаменитую проблему четырех красок, интригующую математиков и посей день.

1.Основные понятия.

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

Определение 1:

Графом называется непустое конечное множество вершин

V={V1 ,V2 ,… , Vn } и множество ребер E={l1 ,l2 ,…,lm } ,оба конца которых принадлежат множеству V.

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

Определение 2:

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

Определение 3:

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

Определение 4:

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

Определение 5:

Ребра, имеющие общую вершину, называются смежными.

Определение 6:

Ребро, соединяющее две вершины графа G , называются инцидентным этим вершинам, а любая из вершин инцидентной ребру.

Определение 7:

Пары вершин графа G могут соединяться двумя и более ребрами. Такие ребра называются кратными.

Определение 8:

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

Определение 9:

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

Поясним сказанное на чертежах:

Степень вершины.

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

Определение:

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

Для изолированной вершины степень равна нулю. Если степень вершины графа равно единице, то вершина называется висячей.

Определение:

Вершина называется нечетной, если ее степень - нечетное число, и четной, если ее степень – четное число.

На рис. 8 V1 – висячая вершина , d (V1) =1

V2 – изолированная V (V2) =0

V5 – нечетная, d (V5) =3

V7 – четная, d (V7) =

 

Примем без доказательства следующие теоремы:

Теорема 1.

В графе G (V ,E) сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа:

n

∑d(Vi)= 2m, где n-число вершин графа;

I=1

M- число ребер графа.

Теорема 2.

Число нечетных вершин любого графа четно.

Следствие Т. 2.

Невозможно начертить граф с нечетным числом нечетных вершин.

Полный граф.

Определение:

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

 

Пусть число вершин полного графа равно n. Тогда степень любой вершины, очевидно, равна d(V)=n-1, а число ребер m=Gn²

 

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

Определение.

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

X- вершина; y- вершина.

Определение:

Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается r(G):

r(G)= min e(x)= min max d (x, y)

X - вершина x, y- вершина.

Определение:

Вершина называется центральной, если e(x)= r(G)

Определение:

Центральная вершина x5

Определение:

Связный граф.

У несвязного графа не все вершины можно соединить цепями с данной вершиной V1.Те вершины, которые можно соединить с вершиной V1 , и все инцидентные им ребра образуют связную компоненту вершины V1. Таким образом, весь граф распадается на связные компоненты, не соединенные между собой ни ребрами, ни цепями.

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

 

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

Примем без доказательства следующую теорему:

Теорема 3.

Теорема 4.

Граф G с мостами ВС и СЕ.

Двудольные графы.

Определение:

Неориентированный граф G(V, E) называется двудольным, если множество его вершин может быть разбито на такие два непересекающиеся подмножества V1 и V2 ,что каждое ребро графа G имеет один конец в V1, а другой в V2.

Например,

Множество вершин V1 неориентированного графа составляют вершину {a, b, c, d, e}, а множество вершин V2 {f, g, j, k}.

Определение:

Плоские графы.

Определение:

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

Например: графы G на рис. 18 является плоским, т.к. существует изоморфный ему граф G´.

А1, А2 , А3 , А4 , А5 .

 

Теорема Эйлера.

Связный плоский граф с n вершинами и m ребрами разбивает плоскость на r областей (включая внешнюю) , причем n-m+r=2.

Примеры неплоских графов.

Спустя некоторое время обитатели домов А, В и С серьезно поссорились друг с другом и решили проложить дорожки к колодцам x, y, z так, чтобы по пути к колодцам и обратно им не приходилось встречать друг друга.

Можно ли это сделать?

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

Вопрос: является ли соответствующий граф плоским, т.е. можно ли провести дорожки так, чтобы они не пересекались нигде, кроме вершин графа A, B, C, x, y, z?Сколько не пытаться, нужного решения не найти. Однако наша неспособность решить задачу методом проб не дает математического доказательства того, что это вообще невозможно сделать.

Теорема Жордана.

Пусть K-непрерывная замкнутая линия на плоскости. Линия

£ делит плоскость на внешнюю и внутреннюю области так, что любая непрерывная кривая £ , соединяющая произвольную точку P внутренней области с некоторой точкой Q внешней области, пересекает K. (рис. 22)

Вывод: Граф задачи является неплоским .

Другой пример неплоского графа показан на рис. 23

Эйлеровы графы.

Гамильтоновы графы.

Определение.

Определение.

Определение.

Определение.

Путь кончится в V2.

Закончится.

Определение.

Определение.

Другие гамильтоновы циклы.

На рис. 26 изображен гамильтоновый граф.

Деревья.

Определение.

Определение.

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

Теорема.

Граф G является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

1)граф связен и не содержит циклов;

Определение.

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

Например, на рис. 28 изображено бинарное дерево уровня 3.

10.Способы задания графов.

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

Одним из самых распространенных способов является матричный. Рассмотрим его:

Определение.

Назовем матрицей смежности графа G без кратных ребер квадратную матрицу А порядка n, в который аij=1, если есть ребра соединяющее вершины Vi, Vj ;

aij=0, если нет ребер, соединяющих вершины Vi, Vj.

Т.к. аij= aji , то матрица смежности неориентированного графа является симметрической и не меняется при транспонировании.

Договоримся считать акк=0, если у вершины Vк нет петли и акк=1, если петля есть.

Например, на рис. 30 изображен граф G.

Является матрицей смежности

Графа.

II .ОРИЕНТИРОВАННЫЕ ГРАФЫ.

Определение:

Определение.

Определение.

Определение.

Пример.

В орграфах в зависимости от сочетания степеней входа и выхода для данной вершины рассматриваются три случая:

А степень выхода равна 0.

Пример:

Определение.

Определение.

Определение.

Определение.

Замечание.

Матрица смежности.

Для двух вершин Vi и Vj (i ≠j) существуют две принципиальные возможности: все ребра выходят из одной вершины и заходят в другую, или для каждой вершины существуют как входящие, так и исходящие ребра.

Например:

Определение.

Пути в орграфах.

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

Решение.

0000 0000 0000

0011 0011 0000

Бесконтурный орграф.

Определение:

Контуром в орграфе С1 принято называть последовательность вершин x0, x1, …, xk ,образующую путь, в которой первая вершина x0 совпадает с последней xk , а других повторяющихся вершин в ней нет.

Определение:

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

В задаче о планировании заданий соответствующий бесконтурный орграф имеет кодовое название “система PERT”от Program Evaluation and Review Technique. PERT была разработана для помощи в конструировании подводной лодки военно –морского флота США.

Пример:

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

  КУРСЫ Предварительные курсы
A Биотехнология B
B Начальный курс биотехнологии C
C Цитология H
D Структура ДНК C
E Энзимология D,A
F Диетология E
G Генная инженерия C
H Биология человека Никаких требований.

Решение.

Система PERT –это просто орграф, представляющий данную приоритетную структуру. Вершины орграфа – восемь курсов. Дуги орграфа отражают представленные в таблице требования, необходимые для условия данного курса.

Ориентированные деревья.

Определение:

Ориентированный граф называется ориентированным деревом, если:

Бинарный поиск.

Сортировка.

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

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

Рассмотрим фразу “У моего компьютера есть чип на материнской плате ”. Дерево двоичного поиска может быть организовано следующим образом:

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

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

 

Поиск (дерево)

Begin

ifдерево нулевое then

поиск: = ложь;

else

ifключ поиска = ключ корня then

поиск := истина;

else

ifключ поиска < ключ корня then

поиск := поиск(левое поддерево);

else

поиск := поиск(правое поддерево);

end

Задача 1. Проследите за работай алгоритма над двоичным деревом поиска, изображенном на рис.39. Известно, что ключ поиска –буква R, а ключи вершины упорядочены лексикографически.

Решение. Поскольку R > K , то поиск продолжается в правом поддереве вершины К. Так как R < K, процесс поиска переключается на левое поддерево вершины Т. Наконец, ввиду неравенства R ≠ M и отсутствия поддеревьев у вершины М , алгоритм заканчивается и сообщает, что искомая вершина не была найдена.

 

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

Вставка (запись, дерево)

Begin

ifдерево нулевое then

добавить новую вершину;

else

ifключ вставки = ключ корня then

вывести на печать:

«запись содержится в дереве»;

else

ifключ вставки < ключ корня then

вставка := вставка(запись, левое поддерево);

else

вставка := вставка(запись, правое поддерево);

end

 

Задача 2. проследите за работай алгоритма вставки на примере вершин R, A и L в дереве из задачи 1.

 

Решение. Поскольку R > K, мы применяем алгоритм вставки к правому поддереву вершины К. Далее мы видим, что R < T. Значит, алгоритм вставки переключается на левое поддерево вершины Т. Так как R > М и правое поддерево вершины М нулевое, то мы ставим вершину R справа то М и получаем дерево, изображенное на рис. 40. Теперь вставим A и L, построив дерево, показанное на рис. 41.

Алгоритм вставки можно использовать для создания двоичного дерева поиска, начиная с нулевого дерева и последовательно добавляя новые данные в удобном для нас порядке. Например, двоичное дерево поиска на рис. 38 является результатом применения алгоритма вставки к нулевому дереву в процессе добавления слов фразы «У МОЕГО КОМПЬЮТЕРА ЕСТЬ ЧИП НА МАТЕРИНСКОЙ ПЛАТЕ» в том порядке, в котором они в ней записаны.

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

 

Правильный обход (дерево)

Begin

ifдерево нулевое then

ничего не делать;

else

Begin

правильный обход (левое поддерево);

напечатать корневой ключ;

правильный обход (правое поддерево);

end

end

Задача 3. Примените алгоритм правильного обхода к дереву, полученному в задаче 2 после вставки R, A и L.

 

Решение. После работы алгоритма над указанным деревом получается список:

A, C, K, L, M, R, T, V.

Он соответствует обходу дерева против часовой стрелки (рис.7.30.) и печати информации, содержащейся в вершинах, как только Вы прошли под вершиной.

 

Введение.

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736 г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно ее приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем электрических цепей и молекулярных схем. В настоящее время можно указать главы чистой математики, например теория математических отношений, в которых теория графов служит естественным аппаратом; с другой стороны, эта теория находит многочисленные применения в многообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов и, вообще, в так называемом «программировании». Теория графов теперь применяется и в таких областях, как экономика, психология и биология. Математические развлечения и головоломки тоже остаются частью теории графов, особенно если отнести к ним знаменитую проблему четырех красок, интригующую математиков и посей день.

1.Основные понятия.

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

Определение 1:

Графом называется непустое конечное множество вершин

V={V1 ,V2 ,… , Vn } и множество ребер E={l1 ,l2 ,…,lm } ,оба конца которых принадлежат множеству V.

Последнее изменение этой страницы: 2016-08-28

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...