Учебники

Графовый алгоритм

Сентябрь 28, 2018

Граф — это абстрактная нотация, используемая для представления связи между парами объектов. Граф состоит из —

  • Вершины — взаимосвязанные объекты в графе называются вершинами. Вершины также известны как узлы .

  • Края. Края — это ссылки, соединяющие вершины.

Вершины — взаимосвязанные объекты в графе называются вершинами. Вершины также известны как узлы .

Края. Края — это ссылки, соединяющие вершины.

Есть два типа графиков —

  • Направленный граф — В ориентированном графе ребра имеют направление, то есть ребра переходят из одной вершины в другую.

  • Ненаправленный граф. В неориентированном графе ребра не имеют направления.

Направленный граф — В ориентированном графе ребра имеют направление, то есть ребра переходят из одной вершины в другую.

Ненаправленный граф. В неориентированном графе ребра не имеют направления.

Раскраска графика

Раскраска графа — это метод назначения цветов вершинам графа, чтобы не было двух смежных вершин одинакового цвета. Некоторые проблемы раскраски графа —

  • Раскраска вершин — способ раскраски вершин графа, чтобы никакие две смежные вершины не имели одинаковый цвет.

  • Раскраска краев — это метод назначения цвета каждому ребру, чтобы два соседних ребра не имели одинаковый цвет.

  • Раскраска граней — назначает цвет каждой грани или области плоского графа, чтобы никакие две грани с общей границей не имели одинакового цвета.

Раскраска вершин — способ раскраски вершин графа, чтобы никакие две смежные вершины не имели одинаковый цвет.

Раскраска краев — это метод назначения цвета каждому ребру, чтобы два соседних ребра не имели одинаковый цвет.

Раскраска граней — назначает цвет каждой грани или области плоского графа, чтобы никакие две грани с общей границей не имели одинакового цвета.

Хроматическое число

Хроматическое число — это минимальное количество цветов, необходимое для окраски графика. Например, хроматическое число следующего графика — 3.

график

Концепция раскраски графиков применяется при составлении расписаний, присвоении подвижной радиочастоты, Suduku, распределении регистров и раскраске карт.

Шаги для раскраски графа

  • Установите начальное значение каждого процессора в n-мерном массиве в 1.

  • Теперь, чтобы назначить конкретный цвет вершине, определите, назначен ли этот цвет соседним вершинам или нет.

  • Если процессор обнаруживает тот же цвет в смежных вершинах, он устанавливает свое значение в массиве в 0.

  • После n 2 сравнений, если какой-либо элемент массива равен 1, то это допустимая раскраска.

Установите начальное значение каждого процессора в n-мерном массиве в 1.

Теперь, чтобы назначить конкретный цвет вершине, определите, назначен ли этот цвет соседним вершинам или нет.

Если процессор обнаруживает тот же цвет в смежных вершинах, он устанавливает свое значение в массиве в 0.

После n 2 сравнений, если какой-либо элемент массива равен 1, то это допустимая раскраска.

Псевдокод для раскраски графа 

begin

   create the processors P(i 0 ,i 1 ,...i n-1 ) where 0_i v < m, 0 _ v < n
   status[i0,..i n-1 ] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if a j,k =1 and i j =i k then
            status[i 0 ,..i n-1 ] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

Минимальное остовное дерево

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

Минимальное остовное дерево

Некоторые возможные остовные деревья приведенного выше графика показаны ниже —

Остовное деревоSpanning Tree 1Spanning Tree 2Минимальное остовное деревоSpanning Tree 3Spanning Tree 4Spanning Tree 5

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

Для реализации минимального связующего по стоимости дерева используются следующие два метода:

  • Алгоритм Прима
  • Алгоритм Крускала

Алгоритм Прима

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

Шаги алгоритма Прима

  • Выберите любую вершину, скажем, v 1 графа G.

  • Выберите ребро, скажем, e 1 из G так, что e 1 = v 1 v 2 и v 1 ≠ v 2, а e 1 имеет минимальный вес среди ребер, падающих на v 1 в графе G.

  • Теперь, следуя шагу 2, выберите минимальное взвешенное ребро инцидента на v 2 .

  • Продолжайте до тех пор, пока не будут выбраны n – 1 ребра. Здесь n — количество вершин.

Выберите любую вершину, скажем, v 1 графа G.

Выберите ребро, скажем, e 1 из G так, что e 1 = v 1 v 2 и v 1 ≠ v 2, а e 1 имеет минимальный вес среди ребер, падающих на v 1 в графе G.

Теперь, следуя шагу 2, выберите минимальное взвешенное ребро инцидента на v 2 .

Продолжайте до тех пор, пока не будут выбраны n – 1 ребра. Здесь n — количество вершин.

Граф Прим Алгоритм

Минимальное остовное дерево —

Минимальное связующее дерево алгоритма Прима

Алгоритм Крускала

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

Шаги алгоритма Крускала

  • Выберите ребро минимального веса; скажем, е 1 графа G и е 1 не является петлей.

  • Выберите следующий минимальный взвешенный край, связанный с e 1 .

  • Продолжайте до тех пор, пока не будут выбраны n – 1 ребра. Здесь n — количество вершин.

Выберите ребро минимального веса; скажем, е 1 графа G и е 1 не является петлей.

Выберите следующий минимальный взвешенный край, связанный с e 1 .

Продолжайте до тех пор, пока не будут выбраны n – 1 ребра. Здесь n — количество вершин.

График алгоритма Крускала

Минимальное остовное дерево приведенного выше графика —

Минимальное остовное дерево алгоритма Крускала

Алгоритм кратчайшего пути

Алгоритм кратчайшего пути — это метод нахождения пути с наименьшей стоимостью от исходного узла (S) к узлу назначения (D). Здесь мы обсудим алгоритм Мура, также известный как алгоритм поиска в ширину.

Назовите исходную вершину S и назовите ее i и установите i = 0 .

Найдите все немаркированные вершины, смежные с вершиной, помеченной i . Если вершины S не связаны с вершиной, то вершина D не связана с S. Если есть вершины, связанные с S, обозначьте их i + 1 .

Если D помечен, то перейдите к шагу 4, иначе перейдите к шагу 2, чтобы увеличить i = i + 1.

Остановитесь после того, как длина кратчайшего пути найдена.

54
Share: