АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I. Задания для самостоятельной работы
  2. I. Открытые способы определения поставщика.
  3. I. Ситуационные задачи и тестовые задания.
  4. II. Расчетная часть задания
  5. III. Задания для самостоятельной работы по изучаемой теме.
  6. III. Задания для самостоятельной работы по изучаемой теме.
  7. III. Задания для самостоятельной работы по изучаемой теме.
  8. III. Задания для самостоятельной работы по изучаемой теме.
  9. III. Задания для самостоятельной работы по изучаемой теме.
  10. III. Задания для самостоятельной работы по изучаемой теме.
  11. III. Способы очистки.
  12. MathCad: способы решения системы уравнений.

1.Матрица смежности вершин графа – квадратная матрица н порядка, где н – число вершин. Строки и столбцы матрицы соответствуют вершинам графа. Элементы рijравны числу дуг, направленных из и в жи. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0 либо 1. В случае не ориентированного графа ему вместе с ребром (Xi Xj) принадлежит ребро (Xi Xj).

2.Матрица смежности дуг – квадратная матрица м порядка, м – число дуг. Строки и столбцы матрицы соответствуют дугам графа. Элементы q­ij­ равны 1, если дуга уi непосредственно предшествует дуге yj и 0 в остальных случаях.

3.Матрица смежности ребер неориентированного графа – матрица м порядка, м – число ребер с элементами qij = 1, если ребра y­­I yj имеют общую вершину и 0 в остальных.

4.Матрица инцидентности орграфа – прямоугольная матрица, размерности Н х М, строки которой соответствуют вершинам, а столбцы дугам орграфа. Элементы r­ij равны 1, если дуга yj исходит из I вершины. Равны 0, если дуга не инцидентна итой вершине.

5 wEZhkZMkI60oXyogG4bLVb0bDywYGSFCKjWA8r+D9rERxtPaDsBe0R+zDdEpozVhAGppLPwua9ge ShV9/EF1rzXKPrfVLg01tQN3Lw1h/0/icv94T/Dvv3nxDQAA//8DAFBLAwQUAAYACAAAACEAmJdc +uAAAAAKAQAADwAAAGRycy9kb3ducmV2LnhtbEyPy07DMBBF90j8gzVI7KjdEDWPxqkQqMsKGliU nRu7SUQ8DrHbpn/PdFV28zi6c6ZYTbZnJzP6zqGE+UwAM1g73WEj4etz/ZQC80GhVr1DI+FiPKzK +7tC5dqdcWtOVWgYhaDPlYQ2hCHn3NetscrP3GCQdgc3WhWoHRuuR3WmcNvzSIgFt6pDutCqwby2 pv6pjlaCr8W8irfvu+gj/v7dvO3W2WXTS/n4ML0sgQUzhRsMV31Sh5Kc9u6I2rNeQpYmRNL8WcTA rkCaLIDtqUiyCHhZ8P8vlH8AAAD//wMAUEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAA AAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACU AQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEAXwb94AkCAAAV BAAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEAmJdc+uAA AAAKAQAADwAAAAAAAAAAAAAAAABjBAAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAHAF AAAAAA== " strokecolor="black [3200]" strokeweight="2pt"> В случае неориентированного графа будет или 0.

 

 

1.

  Х1 Х2 Х3 Х4 Х5 Х6
Х1            
Х2            
Х3            
Х4            
Х5            
Х6            

 

2.

U1                  
U2                  
U3                  
U4                  
U5                  
U6                  
U7                  
U8                  
U9                  

 

3.

  U1 U2 U3 U4 U5 U6 U7 U8 U9
X1   -1   -1          
X2         -1        
X3     -1            
X4           -1 -1    
X5                  
X6               -1 -1

 

Остовные деревья минимального веса. Алгоритмы Прима и Крускала

Пусть G неориентированный связный граф. Любой связный подграф G* из множества (G* с G) содержащий все вершины графа и не имеющий циклов называется остовом G или остовным деревом.

Постановка задачи:

Имеется связный граф, каждому ребру которого поставлено в соответствие неотрицательное число, называемое весом ребра. Требуется найти остовное дерево минимального веса. Вес дерева равен сумме весов ребер, входящих в него.

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

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

К.Если подграф Gк-1 из множества G уже построен,… получается из Gк-1 добавлением ребра Л обладающего свойствами:

1.Л инцедентно какому-либо ребру Gк-1

2.При добавлении к Л Gк-1 не обр цикла

3.Л имеет минимальный вес среди ребер, удовлетворяющих условию 1 и 2.

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

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

К.Если подграф Gк-1 из множества G уже построен,… получается из Gк-1 добавлением ребра Л обладающего Свойства:

1.При добавлении Л Gк-1 не обр циклов

2. Л имеет мин вес среди ребер, удовлетворяющих условию 1.

 

 

Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дейкстры

Постановка задачи:

Пусть задан орграф G=(V,E) с заданными положительными длинами ребер. Найти длину кратчайшего пути(и сам путь), соединяющий 2 произвольные фиксированные вершины s(начало) и t(конец).

Алгоритм Дейкстры:

1.В начале алгоритма все вершины не окрашены. Каждой вершине В во время выполнения алгоритма ставиться в соответствие либо L(v) – длина кратчайшего пути включающего только окрашенные, L(v*) – временная метка, которая становиться равной L(v) в момент когда В окрашивается. Полагаем что L(s)=0, L(v*)…. Окрашиваем вершину s. Для каждой неокрашенной вершины и соседней с последней из окрашенных В пересчитываем L(u)=min(L*(u)L(v)+L(v,u)), L(v,u) – длина дуги.

3(?).В момент, когда вершина t становиться окрашенной находим кратчайший путь, соединяющий s t, состоящий из окрашенных дуг.

s
c
d
t
a
b
3

4 7

3 2

 

L(s)=0 L(c)=3 L(a)=4 L(d)=6 L(b)=7

L*(a)=4 L*(d)=6 L*(b)=7 L*(t)=8 L*(t)=9

L*(b)=7 L*(d)=6

L*(c)=3

 

L(t)=8(s-c-d-t)

 

Алгоритм Флойда (расстояние между 2 точками)

Рассмотрим сеть, в каждой дуге которой (U,V) поставлено в соответствие действительное число L(u,v), называемое длиной дуги. В зависимости от конкретного приложения это число может быть мерой физического расстояния, времени, стоимости или иного параметра.

 
 
 
 
 
Длиной цепи называется сумма длин, взятая по всем дугам этой цепи.

 

 

L0= здесь пишем расстояния из i в j

S0= здесь пишем вершины (справочная)

Алгоритм Флойда

1.планируем,что вершины графа G – числа(1,2,…н). Обозначим через L0 матрицу, элементами которой Lij=длина или бесконечность(1.1 например). Введем матрицу S0 матрица н*н, где элементы Sij=j. Пусть матрицы Lp Sp найдены. Выделим элементы p строки и столбца, назовем их базовой строкой и базовым столбцом соответственно.

2.построим матрицы Lp+1 Sp+1 по следующим правилам:

а)элементы базовой строки и столбца переписываем без изменений.

б) если элемент Lij>Lip+1+Lp

3.алгоритм заканчивает свою работу, когда построены матрицы Ln и Sn.

Замечание 1.Если итый элемент базоваого столбца равен бесконечности, то для ээтой строки шаг 2 выполнять не нужно.

Замечание 2.Если житый элемент равен бесконечности, то шаг 2 выполнять не нужно.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)