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

В 1736г. А. Эйлер написал знаменитую статью о Кёнигсбергских гоостах. Эта статья явилась 1ой статьёй по теории графов и оставалась единственной по этой теории в течении почти ста лет.В те времена по Кенигсбергу протекала река Преголь, на котором было 7 мостов.Жителей города интересовал вопрос, можно ли, выйдя с какого-нибудь участка суши пройти по каждому мосту ровно один раз и возвратиться на этот жк учсток суши

Df.1.:Цикл наз. эйлеровым, если он содержит все рёбра графа по одному разу.

Df.2.:Граф, содержащий элеров цикл наз. эйлеровым.

Теор.1.: Связный граф явл. эйлеровым = когда степень кажд. его вершины четная.

Д-вo: 1. Пусть связн. граф. явл. эйлеровым, тогда при обходе графа в кажд. вершину мы входим по одному ребру, выходим по другому. Поэтому при прохождении кажд. вершины (вход,выход) степень этой вершины увеличивется на 2е единицы. А т.к. в эйлеровом цикле кажд. ребро встречается ровно один раз, то степень кажд. вершины будет четно.

2. Пусть в связн. Графе степень кажд. вершины будет четным. Выберем произвольн. Вершину Vi графа и начнём обход графа из этой вершины, при этом, попадая в какую-либо вершину графа по одному ребру выходить из этой вершины будем по другому. Кроме того ни по какому ребру мы не будем проходить дважды, т.к. степень кажд. вершины четная, то такой обход сможет закончиться только в вершине V_i. Полученный, в рез-те такого обхода, цикл обозначим через P₁. Если цикл P₁ содержит все ребра исходн. Графа, то док-во закончено. Если же нет, то удалим из исходного графа G все ребра цикла P₁ и оставшийся граф обозначим через G₁.

Поскольку и в исх. Графе G и в цикле P₁ степень кажд. вершины тоже будет четная.

Поскольку исх. граф. G был связный, то найдется такая вершина, котор. будет Э и циклу P₁ и графу G₁.

Обозначим эту вершину через Vj. Теперь совершим обход по ранее описанным правилам графа G1 и полученный в рез-те этого цикла обозначим через P2.

Затем из ребер циклов P₁ и P₂ образуем новый цикл P₂ =(часть цикла P₁ от вершины V_i до V_j) + (цикл P₂) + (часть цикла P1 от V_j до V_i).

Если цикл P₂ содержит все ребра исходного графа G, то док-во закончено. Если же нет, то продолжим этот процесс. Поскольку число ребер в графе конечно, то этот процесс не может продолжаться бесконечно.

Д-но.

33. Геометрическая реализация графов

Df.1.: Под геометр. Реализацией графа будем понимать такое представление графов в Евклидовом простр-ве , что никакая вершина или внутр. Точка никакого ребра не явл. вершиной или внутр. Точкой никакого другого ребра.

Прим.: Пусть дан. Граф G=(V,E), где V={V₁,V₂,V₃}, E={(V₁,V₂),(V₂,V₃,(V₃,V₁)}. Тогда из следующих трех представлений графа на плоскости геометрич. Реализацией двухмерное Евкмед. Простр-во будет явл.:

а) нет геом. реализ.

б) есть геом. реализ.

в) нет геом. реализ.

Только б).

Теор 6.: Кажд. конечный граф имеет геометр. реализацию в трехмерном Евклид. простр-ве.

Д-вo: Пусть дан граф G=(V,E),имеющий n-вершин:v_{1 ,}v₂ ,…,v_n и m-рёбер e₁ ,e ,…,e_m.В трёхмерном Евклид. простр.-ве возьмём прямую а и через неё проведём связку из m-плоскостей.На прямой отметим n- точек,которые будут соответствовать вершинами v_{1 ,}v₂ ,…,v_n.Затем,каждой плоскости поставим в соответствии ребро.

Пусть концами ребра e_i явл. вершины v_i1,v_i2 ,тогда в плоскости соответствующей ребру e_i,проведём линию,соединяющую вершины v_i1,v_i2 ,т.е. концы ребра e_i .При таком подходе построенные линии (рёбра) будут пересекаться только лишь в вершинах,расположенных на прямой а.Ч.Т.д.

Замеч.:Можно показать,что в двухмерном Евклидовом простр.-ве,т.е. на плоскости,не кажд. конечный граф имеет геометр. реализицию.

Df.2.: Два графа наз. изоморфными,если имеется взаимнооднозначное соответствие между их вершинами и взаимнооднозначное соответствие между их рёбрами такое,что соотв. ребра соединют соотв. вершины.

Df.3.: Пусть дан граф G=(V,E) в котор. имеется ребро e=(v_i v_j).Тогда операция подразделения ребра е заключается, во-первых в удалении этого ребра и во-вторых в построении 2ух новых рёбер (v_i v_k) и (v_k v_j),где вершина v_k ранее графу не принадлежала.

Df.4.:Граф G’ наз. подразделением графа G,если G’ можно получить из G,путём конечного числа раз применения операции подразделения ребра.

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

Теор.: Конечн. Граф имеет плоск. Геометрич. Реализацию «=» когда никакой его подграф не гомеоморфен ни одному из след. 2ух графов:

34. Сети

Df.1.:Транспортной сетью или просто сетью наз. конечн. Ориентированный граф без петель,удовлетворяющий след. требованиям:

1)имеется ровно одна вершина,называемая входом,в котор. не входит ни одна дуга;

2)имеется ровно одна вершина,называемая выходом,в котор. не исходит ни одна дуга;

3)кажд. дуге v_i v_j приписано неотрицательн. число С(v_i v_j),называемое пропускной способностью дуги.

Df.2.: Потоком по транспортной сети наз. ф.-ция ϕ(u),где u-дуга,удовлетворяющая след. требованиям:

1)ни для какой дуги величина потока не может превышать пропускной способности дуги;

2)для кажд. величины отличной от входа и выхода сумма потоков дуг,входящих в эту вершину в точности=сумме потокв дуг исходящих из этой вершины.

Замеч.:Из второго условия следует,что величина потока во входной вершине в точности=величине потока в выходной.

Df.3.:Пусть А-множ. вершин сети,включающее в себя выходн. вершину и не включающее входную.Тогда разрезом,определяемым множ. А,наз. множ. дуг,входящих и исходящих из вершин множ. А.

Df.4.:Пропускной способностью разреза наз. сумма пропускных способностей дуг,входящих в этот разрез.

Теор.1.:Если пропускная способность некоторого разреза совпадает с величиной потока,то этот поток явл. наибольшим,а разрез явл. разрезом с наименьшей пропускной способностью.

Замеч.:Д.-ва теоремы следует из того,что каждая частица потока,двигаясь от входа к выходу,обязательно пройдёт по какой-либо дуге разреза.

Df.5.:Дуга наз. насыщенной,если её пропускная способность совпадает с величиной потока по этой дуге.

Df.6.:Поток наз. полным,если каждый путь потока от входн. Вершины к выходной содержит хотя бы одну насыщенную дугу.

Замеч.:Величина потока не явл. строго определённой величиной и зависит от распределения потока по дугах.

Рассм. Алгоритм Форда-Фолкерсона нахождения наибольшего потока.Этот алгоритм выполн. В 2а этапа:

1)нахождение полного потока.Для этого рассматривают послед.-но пути,каждый из которых содержит насыщенную дугу.

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

Присврение индексов проводится по след. правилам:

1) входн. Вершине присваиваем индекс 0;

2) если вершина v_i имеет индекс,то индекс +i присваивается вершинам,ещё не имеющим индексов,в которые идут ненасыщенные дуги из вершины v_i .Кроме того, индекс -i присваивается вершинам,ещё не имеющ. индексов,из которых в вершину v_i идут дуги с величиной потока >0

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

Можно увеличить,а отрицательные на дуги,по котор. поток надо уменьшить.

Замеч.:После того,как мы построили полный поток,величиной 5 единиц,присвоение индексов можно было не выполнять ,т.к.ьдо этого мы указали разрез,пропускная способность которого тоже = 5 единицам,следовательно по теор. 6.6 полученный поток явл. наибольшим.