🗊Презентация Элементы теории графов

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

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

Графом G = (X,U) называется совокупность двух множеств: непустого множества X (вершин) и множества U (ребер), т.е. Каждая дуга соединяет две вершины графа, одна из которых является начальной, другая конечной и направлена от первой вершины ко второй. Обозначают дуги: U1= (x1 ,x2), U1 или (x1 ,x2).

Обычно граф изображают диаграммой: вершины — точками или кружочками, а ребра — линиями. Если ребра графа ориентированы, т.е. показаны стрелкой от вершины к вершине, то они называются дугами, а такой граф называется ориентированным или орграфом. Орграф Для орграфа на рис. Соответствие Г(х1) = {х2,х3,х4}, т.е. вершины х2, х3, х4 являются конечными вершинами дуг, у которых начальной вершиной будет x1

Если ребра не имеют ориентации, то граф называется неориентированным или неографом. Неограф

Примеры. Г(х2) = { х1,х3} Г (х5) = — пустое множество; Г(х3) = {х4,х3}

В случае неографа, предполагается, что соответствие Г задает такой ориентированный граф, который получается из исходного графа заменой: каждого ребра двумя противоположно направленными дугами, соединяющими те же вершины. Например, для неографа, приведенного на рис. Г(х3) = {х1, х2, х3} и т.д.

Так как Г(хi) представляет множество вершин хк ξ X, для которых в G существует дуга (хк, хi), то через Г-1 (хi) обозначают множество вершин хк для которых в графе существует дуга (хк, хi), и называют обратным соответствием. Например, для орграфа G, рис.

Если отображение Г(хi) распространяется не на одну вершину, а на множество вершин Хm = {x1, х2,..., хm}, то под Г(хm) понимают объединение Г(х1) U Г(х2) U ... U Г(хm) Например, для орграфа соответствиями будут Г({х2, х3}) = {x1 х5}, Г({х1, х4}) = {х2, х3, х5, х6}. Отображение Г(Г(хi)) записывают Г2(хi). Тройное отображение Г(Г(Г(хi))) записывают Г3(хi) и т.д.

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

Вершины xi и хк называются смежными, если существует дуга (ребро) U(хi,хк) соединяющая их. Например, (x1,x2), (x1, х3), (x1, x4), вершины х2 и х3 не являются смежными, рис. Вершины xi и хк называются смежными, если существует дуга (ребро) U(хi,хк) соединяющая их. Например, (x1,x2), (x1, х3), (x1, x4), вершины х2 и х3 не являются смежными, рис. Если вершины хi и хк являются концами дуги U (хi,хк), то говорят, что эти вершины инцидентны дуге U (или дуга U инцидентна вершинам хi,хк).

Степенью или валентностью вершины графа называется количество инцидентных ей дуг (ребер) и обозначается d(xi) = Г(xi). Например, d(x1) = 4, d(x2) = 2 Степенью или валентностью вершины графа называется количество инцидентных ей дуг (ребер) и обозначается d(xi) = Г(xi). Например, d(x1) = 4, d(x2) = 2 Вершина, степень которой равна нулю, называется изолированной d(x5) = 0. Число дуг орграфа, которые имеют вершину хi своей начальной вершиной называется полустепенью исхода и обозначается d+(xi).

Аналогично, количество дуг орграфа, которые имеют вершину хк конечной вершиной, называется полустепенью захода и обозначается d-(xi). Аналогично, количество дуг орграфа, которые имеют вершину хк конечной вершиной, называется полустепенью захода и обозначается d-(xi). Например, d+(x1) = 3, d+(x2) = 1, d-(x1) = 1, d-(x4) =2.

Теорема Эйлера. Сумма степеней вершин графа равна удвоенному количеству дуг (ребер): Теорема Эйлера. Сумма степеней вершин графа равна удвоенному количеству дуг (ребер): где n — число вершин графа, m — число дуг. Следствие 1. Число вершин нечетной степени всегда четно. Следствие 2. Сумма полустепеней вершин орграфа равна удвоенному числу дуг:

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

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

Маршрут — это неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленно­стью дуг в орграфе. Маршрутом называется последовательность ребер u1, u2, ... ,un, в которой каждое ребро ui, за исключением, возможно, первого и последнего ребер, связано с ребрами ui-1 и ui+1 своими двумя концевыми вершинами.

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

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

Петлей называется дуга графа, у которой начальная и конечные вершины совпадают и6(х3,х2) Путь и1, и2,, и3, ...., иn называется замкнутым, если в нем конечная вершина дуги ип совпадает с начальной вершиной дуги u1 Замкнутые пути в орграфах называются контурами. Замкнутые маршруты (цепи) в неографах называются циклами. Если дугам орграфа G ставится в соответствие какое-либо число, то говорят, что дуга имеет пропускную способность, величина которой — расстояние между вершинами или время прохождения точки, или объем перевозимого и т.д. Если дуга u = (xi,xk), приписывается число cik, называемое пропускной способностью дуги, а граф G называется графом со взвешанными дугами.

Разновидности графов 1. Подграфы или суграфы Пусть дан граф G = (X,U) Остовным подграфом Gp графа G называется граф, для которого X = X, а т.е. остовный граф имеет то же самое множество вершин, но множество дуг подграфа Gp является подмножеством множества дуг исходного графа.

Порожденным подграфом Gt, называется граф Gt = (Хt, Гt), для которого и для каждой вершины т.е. порожденный подограф состоит из подмножества вершин Хt множества вершин исходного графа и всех таких дуг графа G, у которых конечные и началь­ные вершины принадлежат подмножеству Xt (рис.).

Подграфом Gn = (Хn, Un) или частичным подграфом G = (X,U) является граф, для которого выполняется условие (рис. )

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

Граф G = (X,U) называется симметричным (рис. 10.9), если в множестве дуг U для любой дуги (xi,xk) существует также противоположно направленная дуга (хк, хi). В противоположном случае граф называется ассиметричным (рис.).

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

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

6. Изоморфные графы 6. Изоморфные графы Термин «изоморфный» означает в переводе с латинского (иос — равный, одинаковый и морфи — форма, вид), т.е. одинаковый по форме. Графы на плоскости можно представить различными диаграммами. Два графа G1 и G2 называются изоморфными, если они имеют одно и то же число вершин и две любые вершины хi и хк одного графа соединены ребром (дугой), то и соответствующие им вершины другого графа тоже соединены ребром (рис.). Обозначаются G1 ~ G2.

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

Вершины, инцидентные только одному ребру дерева, называются висячими (х3 х4, х5, х6 и х7). Вершины, инцидентные только одному ребру дерева, называются висячими (х3 х4, х5, х6 и х7). Ориентированным называется древовидный граф без циклов, в котором полустепень захода каждой вершины, за исключением одной, например, вершины хо, равна единице, а полустепень захода вершины х0 равна нулю. Вершина х0 называется корнем дерева (рис.).