34. Графическое разбиение.

d1+d2+…+dn=2m (m-число рёбер) d1, …,dn-степени вершин

Сумма степеней вершин графа равна удвоенному числу рёбер.

Представление натурального числа p=d1+…+dn в сумме натуральных чисел называется разбиением этого числа.

Разбиение называется графическим, если полученый набор слагаемых является набором степеней вершин некоторого графа.

П=(d1,…,dn)-графическое разбиение, элементы разбиения -набор степеней вершин графа.

Сумма степеней вершин-всегда чётное число.

Предпологаем, что элементы разбиения расположены в порядке невозростания (d1≥d2≥…≥dn)

Пусть П=d1,….,dn-некоторое разбиение

Модефицированым разбиением разбиения П назыв разбиение П’, которое получается следующим образом: первый элемент d1 из разбиения удаляется, а из последующих d1 элемента вычитается по единице, и если необходимо, то элементы упорядочиваются.

Теорема. Разбиение П является графическим тогда и только тогда, когда графически модефицированное разбиение является П’.

Доказательство.Необходимость. Пусть модефицированное разбиение П’ является графическим, и необходимо показать, что П является графическим изображением тоже. Пусть разбиению П’ соответствует граф G’. Разбиению П тогда соответствует граф G, который строится след образом: добавлябтся новые вершины и добавляются рёбра, которые связывают эту вершину с вершинами d1’, d2’,…,dd1’.

Достаточность. Возможно 2 случая:

1.Вершина с номером 1 смежна в графе G с вершинами, которые имеют 2,3,…,d1+1

2.Данные ситуации не имеют места.

В первом случае граф G’, реализующий разбиение П’ (по графу G строится след образом:удал вершина с номером 1 и все инциндентны ей рёбра)

Во втором случае в графе G найдётся некоторая вершина с номером і, которая смежна вершине с номером1, а в разбиение П этой вершине предшествует вершина с номером k такая, что вершины 1 и kне смежны между собой.

В этом случае существует вершина j, смежная с вершиной k и не смежная с вершиной i. Это следует из того, что элементыразбиения упорядоченные в порядке не возрастания.

Перестроим граф G. Удалим рёбра (1, i),(k,j) и добавим рёбра (j,i),(1,k).

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

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

1.Списком рёбер

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

gij= 1(i,j)ЄU

0, в противном случае

3.Матрица инцидентности

(Рёбра нумеруються, строки соответствуют номерам рёбер)

g ij= 1, вершина i и ребро j инцидентно графе

0, в противном случае

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.