Теория графов презентация

В и С, связанных ребрами – ребро d между вершинами А и В, ребро e между вершинами В и С, ребро f между вершинами В и А, ребро g между вершиной С и С.
Как называется ребро е по отношению к ребру d?
Как называется ребро g?

для этого графа.

2

все попарно неизоморфные несвязные 5-вершинные графы, не имеющие петель, кратных ребер и изолированных вершин.

и кратных ребер со следующим набором степеней вершин (2, 2, 3, 3, 3, 5)
Изобразить все попарно неизоморфные не имеющие петель и кратных ребер кубические графы с 6 вершинами (кубические – однородные (у которых все вершины – одинаковой степени) графы со степенью 3)

Ответ обосновать.

Ответ обосновать.

Ответ обосновать.

возникает при проектировании линий электропередачи, трубопроводов, дорог и т.п., когда требуется заданные центры соединить некоторой системой каналов, связных либо непосредственно соединяющим их каналом, либо через другие центры и каналы, так, чтобы общая длина (или, например, стоимость) каналов связи была минимальной. Решение этой задачи «слепым» перебором вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых n (можно доказать, что полный граф Kn содержит nn–2 различных остовных дерева). Однако для ее решения имеются эффективные алгоритмы. Опишем два из них - алгоритмы Дж. Краскала (1956) и Р. Прима (1957), применяемые к произвольному связному графу (G, w) порядка n.

множестве вершин VG ребро e1∈VG минимального веса.
Шаг 2. Если граф Ti уже построен и i

алгоритм Краскалла.

12

1

2

4

3

7

8

5

6

10

11

9

1

7

9

5

6

2

3

4

1

6

7

1

8

2

1

1

6

4

3

b – две его вершины. Требуется найти цепь, соединяющую вершины а и b и содержащую наименьшее число ребер.

с а и соединенные с а, дугами, инцидентными вершине а, помечаем индексами 1.
Вершины, смежные с помеченными индексами 1 и соединенные с ними инцидентными вершинам 1 дугами, помечаем индексами 2.

m, обозначим Am.
В некоторой момент будет помечена вершина b, пусть b∈An. Останавливаем процесс индексации.

тем же соображениям существует вершина b2∈An-2, смежная с b1, и т.д.
Искомая цепь с наименьшим числом ребер получается теперь как последовательность вершин (b, b1, b2, …, bn=a), где bi An-i, то есть нужно двигаться, начиная от конечной вершины b в сторону убывания индекса вершины.

количество шагов все вершины графа будут снабжены индексами, причем наибольший из них является условным радиусом графа G относительно вершины а.
ra=max d(a, b)

длины кратчайших путей от вершины а до остальных вершин графа;
Найти длины кратчайших путей от каждой вершины графа до вершины а.
При этом в основном алгоритме изменяется только построение множества Аn.

кратчайшей цепи из a в b.
Радиус графа определяется как наименьший из условных радиусов вершин графа.
Центром графа G называется такая вершина a, что максимальное расстояние между a и любой другой вершиной является наименьшим из всех возможных. Это расстояние называется радиусом графа.
Диаметром d связного графа называется максимальное возможное расстояние между любыми двумя его вершинами.
Если расстояние между двумя вершинами равно диаметру графа, то кратчайший путь, соединяющий эти вершины, называется диаметральным путем, а подграф, образованный вершинами и ребрами этого пути, – диаметральной цепью.

n + 1 вершины, то есть ориентированный граф, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг.
Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг).
Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети.
Известно, что для существования кратчайшего пути необходимо и достаточно отсутствия в сети контуров отрицательной длины.

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

минимальным значением и объявим ее постоянной. Затем, до тех пор, пока стоку не будет приписана постоянная метка, необходимо выполнить следующее:

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

t, сумма весов дуг которой минимальна.

S

V1

V2

t

V5

V3

V4

1

3

10

2

3

1

6

7

5

1

3

3

2

t, сумма весов дуг которой минимальна.

t, сумма весов дуг которой минимальна.

t

S

5

12

5

6

6

9

4

8

2

4

12

8

2

3

7

8

3

V1

V2

V3

V8

V7

V6

V4

V5