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

Вспомогательный Рисунок №1 чтобы посмотреть рисунок, щёлкните по гиперссылке и смотрите рис 0.1. На рис. изображён граф, вершинами которого служат пронумерованные вершины, а рёбрами - линии (со стрелками или без), соединяющие некоторые из этих кружков. Ребро а ориентированное (направленное): оно соединяет вершину 1 с вершиной 2, но не соединяет 2 с 1; к такому тину рёбер, называемых дугами, относятся так же e, f, g. Ребро h не ориентированное: оно одновременно соединяет вершину 1 с 4, так и 4 с 1; к таким рёбрам, называемым ещё звеньями, относятся также i, j. Наконец, каждое из рёбер b, c, d, k является петлёй - соединяет некоторую вершину с ней же.

Вспомогательный Рисунок №1 на рис 0.2 гиперссылки показаны основные атрибуты графа.

Если x={v, w} - ребро графа, то v и w называются концами ребра x, в этом случае так же будем говорить, что x соединяет v и w, и если v начало, а w конец, то будем говорить, что x выходит из v и заходит в w. Если x выходит из v или заходит в w, если v является концом(началом) ребра(дуги) x, то говорят, что v и x инцидентны. Вершины v и w графа G называются смежными, если рёбра их соединяющие принадлежат X. Два ребра называются смежными если они имеют общую вершину. Степенью вершины v графа G называется число d (v). Это число рёбер графа G инцидентных вершине v. Вершина графа со степенью 0 - изолированная, а со степенью 1 висячей. Полустепенью исхода, захода вершины v орграфа D называется число дуг орграфа, исходящих из v (заходящих в v).

Вспомогательный Рисунок №1 на рис 0.2 в вершину v₂ входит дуга x₁, а выходит x₂, поэтому можно записать d ⁺(v₂)=1 полу степень исхода, d ^-(v₂)=1 полу степень захода.

{v, w}О X₁Ы {φ(v),φ(w)}О X₂.

Орграфы D₁(V₁,X₁) и D₂(V₂,X₂) называются изоморфными, если существует биективное отображение φ:V₁→ V₂, сохраняющая смежность, т.е. {v, w}О X₁Ы {φ(v),φ(w)}О X₂.

Если графы G₁ и G₂ изоморфны, то выполняется:

а) " v О V₁: d (v)=d (φ(v))

б) m(G₁)=m(G₂); n(G₁)=n(G₂).

Если орграфы D₁ и D₂ изоморфны, то:

а) " v О V₁: d ⁺(v)=d ⁺(φ(v))

d ^-(v)=d ^-(φ(v))

б) m(D₁)=m(D₂); n(D₁)=n(D₂). Где m - количество рёбер, а n - вершин.

Вспомогательный Рисунок №1 на рис 0.3 показаны изоморфные графы.

Операция подразвиения: (измельчения дуги (u, v) в орграфе D) состоит в удалении из набора X дуги (u, v) и добавления к множеству V новой вершины w и добавлении к набору X двух дуг (u, w), (w, v). Орграф D₁ называется подразвиением орграфа D₂, если D₁ можно получить из D₂ путём последовательного применения операций подразвиения дуг. Аналогично с графами. Щёлкните на вспомогательный рис №1, чтобы посмотреть пример подразвиения, он показан на рис 0.4.

Гомеоморфными называются графы G₁, G₂ (D₁, D₂), если их подразвиение является изоморфным.

Маршруты, пути: последовательность v₁, x₁, v₂, x₂,…, x_k,v_k+1, в которой чередуются вершины и рёбра, называется маршрутом, соединяющим вершины v₁, v_k+1. Последовательность v₁, x₁, v₂, x₂,…, x_k,v_k+1, в которой чередуются вершины и дуги, называется путём, соединяющим вершины v₁- v_k+1. При этом v₁ начальная вершина v_k+1 конечная, а остальные внутренние. Одна и та же вершина может быть начальной, конечной и внутренней. Число рёбер (дуг) в маршруте (пути) называется длиной маршрута (пути). Маршрут (путь) называется замкнутым, если его начальная вершина совпадает с конечной. Не замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны называется цепью. Цепь, в которой все вершины попарно различны называется простой. Замкнутый маршрут(путь), в котором все рёбра (дуги) попарно различны называется циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым.

Пусть D-орграф, где V={v₁,v₂,…,v_n}, X={x₁,x₂,…,x_n}. Матрицей смежности орграфа D называется матрица A(D)=[a_ij] порядка n, у которой:

1, (v_i,v_j) О x

0, (v_i,v_j) П x

Матрицей инцидентности орграфа D называется матрица (n ґ m) B(D)=[b_ij] , у которой:

1, если вершина v_i является концом дуги x_j

-1, если v_i является началом дуги x_j

0, если v_i не инцидентна дуге x_j

Вспомогательный рисунок №2 на рис 1.2 показан пример матричного задания орграфа.

Пусть G(V, X) граф, где V={v₁,v₂,…,v_n}, X={x₁,x₂,…,x_n}. Матрицей смежности графа G называется матрица A(G)=[a_ij] порядка n, у которой:

1, (v_i,v_j) О x

0, (v_i,v_j) П x

Матрицей инцидентности графа G называется матрица (n ґ m) B(G)=[b_ij], у которой:

1, если вершина v_i инцидентна ребру x_j

0, если v_i не инцидентна x_j

Вспомогательный рисунок №2 на рис 1.1 показан пример матричного задания графа.

Связанность. Компоненты связанности.

Говорят, что вершина w орграфа D ( гр. G ) достижима из вершины v, если либо w = v, либо существует путь из v в w (маршрут из v в w ). Говорят, что граф связан (оргр. сильно связанный ), если для его вершин v, w существует маршрут ( путь ), соединяющий эти вершины. Оргр. называется односторонне цельно связанным, если для его вершин по крайней мере одна достижима из другой.

Матрица связанности: пусть D=(V, X) орграф, где V={v₁,…,v_n}. Матрицей достижимости называется квадратная матрица T(D)=[t_ij] порядка n, у которой t_ij=1, если вершина v_j достижима из v_i, t_ij=0 в противном случае.

Матрицей сильной связанности орграфа D называется квадратная матрица S(D)=[s_ij] порядка n, у которой s_ij=1, если вершина v_i достижима из v_j и одновременно v_j достижима из v_i, s_ij=0 в противном случае. Пусть G=(V, X) граф. Матрицей связанности графа G называется квадратная матрица S(G)=[s_ij] порядка n, у которой s_ij=1, если j = i или существует маршрут соединяющий v_i и v_j, s_ij=0 в противном случае.

Алгоритм Терри: (алгоритм поиска маршрута в связанном графе G, соединяющего заданные вершины v и w О V, где v ≠ w.)

Шаг2: исходя из некоторой v^' , всегда следовать только по тому ребру, которое не было пройдено или было пройдено в противоположном направлении.

Шаг3: для всякой вершины v^', отличной от v отмечать первое заходящее в v^' ребро, если v^' встречается первый раз.

Шаг4: исходя из некоторой вершины v^', отличной от v по первому заходящему ребру идти лишь тогда, когда нет других возможностей.

Так же существуют задачи на нахождение маршрута.

Утверждение. Пусть G-связный граф, v – висячая вершина в G, G^' – граф полученный из G в результате удаления вершины v и инцидентного ей ребра. Тогда G^' - связный граф.

Утверждение. Пусть G^' -- граф являющийся деревом, G- граф полученный в результате добавления к G^' новой вершины v и ребра {v, W} где W -- некоторая вершина графа G^'. Тогда G - дерево.

Утверждение. Пусть G = (v, X) – связный граф с n ребрами и m вершинами и пусть так же выполняется равенство m = n –1. Тогда G – дерево.

ОСТОВНОЕ ДЕРЕВО СВЯЗНОГО ГРАФА.

Число m (G) – n (G) + 1 называется цикломатическим числом связного графа G и обозначается через v (G).

Алгоритм выделения остовного дерева. Для произвольного связного графа G = (v, X).

Шаг 1. Выбираем в G произвольную вершину v₁, которая образует подграф G₁ графа G, являющийся деревом. Полагаем i = 1.

Шаг 2. Если i =n, где n = n (G), то задача решена, и G_i – искомое остовное дерево псевдографа G. B противном случае переходим к шагу 3.

Шаг 3.Пусть уже построено дерево G_i являющееся подграфом графа G и содержащее некоторые вершины v₁,…,v_i , где 1 Ј i Ј n-1. Строим граф G_i+1, добавляя к графу G_i новую вершину v_i+1 О v, смежную в G с некоторой вершиной v_j графа G_i, и новое ребро {v_i+1, v_j} (в силу связности G и того обстоятельства, что i<n, указанная вершина v_i+1 обязательно найдется). Граф G_i+1 так же является деревом. Присваиваем i: = i +1 и переходим к шагу 2.

кликни по микрофону, чтоб перейти на основную страницу...