Архив разработки (80 Кб, Mathcad-документ)

Бинарные операции

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

1. Выполняем генерацию матриц М1, М2 смежности неориентированных помеченных графов G1, G2.

алгоритм генерации матриц:

генерация матриц смежности М1 и М2:

m2 - вектор с номерами вершин матрицы М2; номера вершин матрицы М2 можно задавать любые

2. Выполняем операцию объединения графов G1 и G2, заданных матрицами М1 и М2 соответственно.

алгоритм объединения графов:

r - размерность второй матрицы (M2)

объединим матрицы М1 и М2:

объединенная матрица М:

счет вершин в графе ведется по часовой стрелке от левой вершины

граф матрицы М1 вершины имеют номера	граф матрицы М2 вершины имеют номера

граф объединенной матрицы М

3. Выполняем операцию пересечения графов G1 и G2, заданных матрицами М1 и М2 соответственно.

m2 - вектор с номерами вершин матрицы М2; номера вершин матрицы М2 можно задавать любые

алгоритм пересечения графов:

r - размерность второй матрицы (M2)

матрица пересечения графов G1 и G2

4. Выполняем операцию кольцевой суммы графов G1 и G2, матрицы которых М1 и М2 соответственно (кольцевая сумма аналогична сложению по модулю 2).

алгоритм кольцевой суммы графов:

r - размерность второй матрицы (M2)

матрица кольцевой суммы графов G1 и G2

граф матрицы М1 вершины имеют номера	граф матрицы М2 вершины имеют номера
граф матрицы пересечения графов	граф матрицы кольцевой суммы графов

5. Задаем графы, содержащие два ребра. Выполним операцию декартова произведения графов.

n,m - размерности матриц

М - матрица декартова произведения графов G1 и G2

два исходных графа

их декартово произведение

Наверх

В начало