Всё для Учёбы — студенческий файлообменник
1 монета
ppt

Студенческий документ № 000118 из ДГТУ (бывш. РИСХМ)

Операции над графами.

Операции над графами:

* 1. Объединение

* 2. Пересечение

* 3. Кольцевая сумма

* 4. Удаление вершины

* 5. Удаление ребра

* 6. Замыкание

* 7. Стягивание

* 8. Произведение

* 9. Композиция над графами

* 10. Построение единых деревьев графа

Даны два графа G1 и G2 с вершинами, обозначенными буквами v и ребрами, обозначенными буквами e.

Наглядно обозначим каждую из операций над графами на примере этих двух графов.

G1 G2

1. Объединение

Объединением графов G1 и G2 будет новый граф G3

G1?G2=G3=(v1?v2, e1?e2)

G3

2. Пересечение

Пересечением графов G1 и G2 называется новый граф G4

G4

3. Кольцевая сумма

Кольцевой суммой графов G1 и G2 будет граф G5, состоящий из ребер входящий только в G1 и G2.

G5

4. Удаление вершины

Удалением вершины называют граф, полученный при удалении вершины исходного, при этом удаляются все ребра, инцидентные этой вершине.

G1 - исходный граф G6 - граф, полученный путем удалением вершины v2

5. Удаление ребра

Удалением ребра называют операцию, при котором из исходного графа удаляют только ребро, при этом вершина не удаляется.

G2 - исходный граф G7 - граф, полученный при удалении ребра е10

6. Замыкание

Операция замыкания или отождествления: пара вершин замыкается или отождествляется, если она заменяется новой вершиной, такой, что все ребра становятся инцидентны новой вершине.

G2 - исходный граф G8 - граф, с замкнутыми вершинами 1;2

7. Стягивание.

Стягивание - это удаление ребра и отождествление его кольцевых вершин.

G2 - исходный граф G9 - граф, полученный путем стягивания ребра e1

8. Произведение графов

Произведение графов определяется по формуле

Данная операция некоммутативная

g1хg2 g2хg1

9. Композиция над графом

G=g1[g2]

GG=g2[g1]

10. Построение единых деревьев графов

Дан граф G

Дерево графа T

Презентацию выполнила студентка группы ВИС 12 Ли Мария.

2009

Показать полностью… https://vk.com/doc-128337234_438473721
153 Кб, 25 октября 2016 в 18:58 - Россия, Ростов-на-Дону, ДГТУ (бывш. РИСХМ), 2016 г., ppt
Рекомендуемые документы в приложении