П1.3. Решение задач по теории графов

Графы по своему виду делятся на ориентированные и неориентированные. Вид ориентированного графа показан на рисунке П.2, а вид неориентированного графа приведен на рисунке П.3.

Ориентированный граф как математический объект можно представить в следующем виде: сформируем множество вершин , определим отображения вершин, то есть дуги соединяющие вершины: , , , , .

В неориентированных графах отображения вершин определяются следующим образом: , , , , .

В ориентированном графе матрица смежности имеет следующий вид:

Матрица смежности неориентированного графа имеет вид:

Определим матрицу инцидентности ориентированного графа:

Матрица смежности неориентированного графа имеет вид:

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

Выполним с этими графами следующую операцию

.

Определим пересечение множеств вершин заданных графов

.

Определим отображения всех общих вершин, множества пересечения вершин

, ,

.

Выполним с этими же графами следующую операцию

.

Определим объединение множеств вершин этих графов

.

Определим отображение всех вершин обоих графов

, ,

, ,

.

В результате пересечения графов получится граф изображенный на рисунке П.4, а в результате объединения этих двух графов получится граф изображенный на рисунке П.5.