Главная страница
Навигация по странице:

  • Теорема

  • Определения

  • лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4


    Скачать 1.51 Mb.
    НазваниеОсновные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
    Анкорлекции по дм
    Дата08.02.2021
    Размер1.51 Mb.
    Формат файлаdocx
    Имя файлалекции.docx
    ТипДокументы
    #174835
    страница25 из 40
    1   ...   21   22   23   24   25   26   27   28   ...   40

    Представление графов в ЭВМ


    Наиболее распространены следующие 4 метода представления графов в ЭВМ:

    • Матрица смежности,

    • Матрица инцидентности,

    • Списки смежности вершин,

    • Списки смежности дуг.

    Вы уже имеете представление о представлении графа матрицами смежности и инцидентности (Тема 11, пункт 1). Поясним суть списков смежности вершин.

    Списки смежности вершин – представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей на списки смежных вершин, где элемент списка представлен структурой.

    Представление графа с помощью массива структур представляется в виде записей: .

    Тема 12. Компоненты связности и объединение графов. Оценка числа ребер через число вершин и число компонентов связности. Вершинная и реберная связность. Мосты и блоки.

    Объединение графов и компоненты связности. Оценка числа рёбер через число вершин и число компонентов связности. Вершинная и рёберная связность: мосты и блоки, меры связности.


    Напомним, что если граф G состоит из одной компоненты связности, (то есть k(G) = 1), то он называется связным.

    В связном графе любые две вершины соединены (простой) цепью.

    Теорема: Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.

    Рассмотрим граф:



    Vk1 k2

    Замечание: Несвязный граф можно всегда представить как объединение связных компонент. Эти компоненты можно рассматривать независимо.

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

    В любом нетривиальном графе есть, по крайней мере, две вершины, которые не являются точками сочленения.

    Теорема: Пусть р – число вершин, q – число ребер, k – число компонент связности графа. Тогда (p-k) ≤ q ≤ (p-k)(p-k+1) / 2.

    Следствие: Если q > (p-1)(p-2) / 2 , то граф связен.

    Мостом называется ребро, удаление которого увеличивает число компонент связ­ности.

    Рассмотрим рисунок:

    w c d


    a


    bef

    u, v – точки сочленения, х – ребро-мост, awb, buw, awub, cdv, evf – блоки.


    Блоком называется связный граф, не имеющий точек сочленения.

    Если в графе есть мост, то есть и точка сочленения. Концы всякого моста кроме висячих вершин являются точкой сочленения, но не всякая точка сочленения является концом моста.

    Вершинной связностью графа G (обозначается x(G)) называется наименьшее чи­сло вершин, удаление которых приводит к несвязному или тривиальному графу.

    Пример:

    æ(G) = 0, если G несвязен;

    æ(G) = 1, если G имеет точку сочленения;

    Граф G называется k-связным, если æ(G) = k.
    Реберной связностью графа G (обозначается A(G)) называется наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.

    Пример:

    λ(G) = 0, если G несвязен;

    λ(G) = 1, если G имеет мост;

    λ(Кр) = р-1, значит, граф Кр – полный.


    Тема 13. Потоки в сетях. Определение потока. Разрезы. Пример сети с потоками. Теорема Форда и Фалкерсона. Алгоритм нахождения максимального потока.

    Потоки в сетях. Примеры практических задач, определение потока, разрезы.


    Рассмотрим некоторые примеры практических задач.

    Пример:

    1) Пусть имеется сеть трубопроводов, соединяющих пункт А (скажем, нефтепромысел) с пунктом В (скажем, нефтеперерабатывающим заводом). Трубопроводы могут соединяться и разветвляться в промежуточных пунктах. Количество нефти, которое может быть перекачено по каждому отрезку трубопровода в единицу времени, также не безгранично и определяется такими факторами, как диаметр трубы, мощность нагнетающего насоса и т. д. (обычно это называют «пропускной способностью» или «максимальным расходом» трубопровода). Сколько нефти можно прокачать через такую сеть в единицу времени?

    2) Пусть имеется система машин для производства готовых изделий из сырья, и последовательность технологических операций может быть различной (то есть операции могут выполняться на разном оборудовании или в разной последовательности), но все допустимые варианты заранее строго определены. Максимальная производительность каждой единицы оборудования, естественно, также заранее известна и постоянна. Какова максимально возможная производительность всей системы в целом и как нужно организовать производство для достижения максимальной производительности?

    Определения:

    Пусть G(V, Е) – сеть, сетью называется граф, имеющий вершины. S и t – соответственно источник и сток сети. Дуги сети нагружены неотрицательными вещественными числами Е  R+ . Если u и v – вершины, то число с(u, v) – называется пропускной способностью дуги (u, v).


    При решении будем полагать, что C(2,1)= C(1,2).

    Максимальное количество Xij вещества, которое может пропустить в единицу времени ребро между вершиной (i,j) называют его пропускной способностью.

    В общем случае Xij ≠Xji. Пропускные способности рёбер сети можно задать квадратной матрицей n-го порядка, где n – число вершин сети. В теории потоков предполагается, что Xii=0. И поэтому главная диагональ матрицы состоит из нулей.



    ||Cij|| =


    1 2 3 4 5 6

    1. 0 6 1 0 0 0

    2. 6 0 2 0 3 0

    3. 1 2 0 3 0 0

    4. 0 0 3 0 1 2

    5. 0 3 0 1 0 5

    6. 0 0 0 2 5 0



    Сформируем начальный поток 0, состоящий из суммы потоков по

    следующим путям, и найдем пропускные способности путей:

    1 = (1, 3, 4, 6), ( 1 ) = 1;

    2 = (1, 2, 3, 4, 6), ( 2 ) = 2;

    3 = (1, 2, 5, 6), ( 3 ) = 3.

    Т.e. пропускная способность потока 0 равна:

    0 = ( 1 )+ ( 2 )+ ( 3 ) = 6
    Величина потока каждого ребра выглядят так :

    (e13) = 1;

    (e12) = 4;

    (e23) = 1;

    (e34) = 2;

    (e46) = 2;

    (e25) = 3;

    (e56) = 3.
    Составим теперь матрицу построенного потока ( M2 ) c эле- ментами (eij):
    1 2 3 4 5 6




    1. 0 4 1 0 0 0

    2. -4 0 1 0 3 0

    3. -1 -1 0 2 0 0

    4. 0 0 -2 0 0 2

    5. 0 -3 0 0 0 3

    6. 0 0 0 -2 -3 0



    Далее строим матрицу М3 = М1 - М2 = { C(eij) - (eij) }:
    1 2 3 4 5 6



    1. 0 2 0 0 0 0

    2. 10 0 1 0 0 0

    3. 2 3 0 1 0 0

    4. 0 0 5 0 1 0

    5. 0 6 0 1 0 2

    6. 0 0 0 4 8 0


    В соответствии с данным алгоритмом составляем максимальный поток:

    1)Построим начальный поток.

    2)Составляем по ненасыщенному пути А={1,2,3,4,5,6},где 1I и

    6S,в сответствии с п.2 алгоритма построения по теореме Форда-Фалкерсона,сток попал в количество ребер по ненасыщенному пути.

    3)Выделим путь из истока в сток состоящий из ненасыщенных ребер 4=(1,2,3,4,5,6).

    Потом высчитываем Сij-Xij:C12-X12=6-4=2, C23-X23=2-1=1,

    C34-X34=3-2=1,∆45=1,∆56=2.

    Min(Cij-Xij)=1,увеличиваем на единицу построенный поток и возвращаемся к п.2 (4)=1.

    П.2 строим множество по ненасыщенным ребрам А={1,2}

    Построим разрез min пропускной способности. Этот разрез будет иметь вид (A\B)=1+2+3=6.

    Построим разрез транспортной сети. Он будет пересекать дуги, начало которых принадлежит множеству А,а конец мно-жеству В.



    Считаем пропускную способность разреза:

    R(A\B)=1+2+3=6.

    Таким образом, согласно теореме Форда- Фалкерсона построен

    Максимальный поток, равный минимальной пропускной способности pазреза сети.
    1   ...   21   22   23   24   25   26   27   28   ...   40


    написать администратору сайта