36. Типы связности орграфов

Последовательность вершин орграф(i1, i2,…,ik) такая, что любые 2 соседние вершины этой последовательности смежности, называются полумаршрутом.

Последовательность вершин орграфа (i1,i2,…,ik) такая, что любые 2 соседних её вершины связаны дугой (ip,ip+1), называются муршрутом.

Маршрут (полумаршрут), у которого все дуги различны, называется путём(полупутём)

Замкнутый путь называется контуром, замкнутый полупуть называется полуконтуром.

Пусть G=(N,U)-некоторый ор.граф. Граф Д=(N,W) лежит в основе орграфа G если любые 2 вершины смежны в графеД тогла и только тогда, когда они смежны в орграфе G(за исключением петель).

Ор.граф назыв слаюосвязным (слабым), если в его основе лежит связный граф.

Орграф назыв односторонне связным или односторонни, если для любой пары вершин (i,j) имеется путь либо из вершины i в вершину j, или имеется обратный путь из j’в i.

Орграф называется сильносвязным или сильным, если для любой пары вершин (i,j) сущ путь как из і в j, так и из j в i.

Если орграф сильносвязен, то он слоюосвязен и одностороннее связен. Обратное не верно.

Если орграф односторонне связен, то он слабосвязен. Обратное не верно.

Орграф не связен, если он не слабосвязен.

3 типа компонента связности

Сильной компонентой связности орграфа назыв макс сильный подграф.

Односторонней компонентой связности орграфа назыв макс односторонний подграф.

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

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

Орграф, не имеющий контуров, назыв безконтурным

Нормальным упорядоченьем вершин орграфа (i1,i2,…,in) назыв такое их упорядоченье, при котором всегда, когда имеется дуга (k,l) в упорядоченьи вершина k стоит раньше за вершину l.

Теорема. Для орграфа G след условия эквивалентны:

1.Орграф G-безконтурный

2.Оргаф G обладает рекурентным свойством нор: если множ вершин графа не пусто, то сущ вершина, не имеющая входящих дуг, и после удаления этой вершины, новый подграф обладает свойством нор.

3.Множ нормальных упорядеченьях графа не пусто.

Доказательство. Докажем, что из 1=>2. Предположим, что орграф безконтурный и покажем, что в этом случае вершины не имеют входящих дуг. Предположим противное: пусть некоторые вершины имеют только входящие дуги. Удаление такой вершины не влияет на безконтурность и, по крайней мере, одна вершина остаётся. Последовательно, удаляя такие вершины, приходим к ситуации, когда каждая вершина

I.Имеет как входящие так и выходящие дуги.

II. Найдётся вершина, которая имеет только выходящие дуги. Противоречие получено.

В первом случае в исходном графе можно выделть контур, например, следующим образом: выбирается произвольная вершина и от неё по дуге двигаемся к смежной ей вершине. Продолжая таким образом, через конечное число шагов некоторая вершина повторится. В исходном графе получен контур. Получили противоречие. После удаления этой вершины, новый орграф будет безконтурным, то есть существует вершина, не имеющая входящих дуг. Доказали, что из 1=>2.

Докажем, что из 2=>3. Если выполняется свойство 2, то по крайней мере одно нормальное упорядочинье можно построить следующим образом :выбераем в графе произвольную вершину, не имеющую входящих дуг. Удаляем её из орграфа и ставим на первое место слева в строющееся нормальное упорядочинье. Если множество вершин графа не пусто, то продолжаем эту процедуру до тех пор, пока множество не станет пустым. Доказали, что из 2=>3.

Докажем, что из 3=>1. Предположим, что S-произвольное нормальное упорядоченье орграфа G. Предположим противное:что в орграфе есть контур (i1,i2,…,ik,i1). Тогда прилюбом расположении веришн этого контура в нормальном упорядоченьи S найдётся дуга (p,l) такая, что в упорядоченьи S вершина N предшествует вершине P. А это противоречит тому, что упорядоченье S является нормальным. Получили, что из 3=>1.