Транзитивное замыкание отношений

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ

ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. В.Г.ШУХОВА»

(БГТУ им. В.Г. Шухова)

Кафедра программного обеспечения вычислительной техники и автоматизированных систем

Лабораторная работа №3.2

дисциплина: Дискретная математика

тема: «Транзитивное замыкание отношений»

Выполнил: ст. группы ВТ-201

Ковалев Дмитрий Сергеевич

Проверил:

 Рязанов Юрий Дмитриевич

Белгород 2021

Цель занятия: изучить и выполнить сравнительный анализ алгоритмов вычисления транзитивного замыкания отношения.

Задания

1.Изучить и программно реализовать алгоритмы 3.10 — 3.12 вычис-

ления транзитивного замыкания.

    //Алгоритм Уоршалла

int  transitСlosureW(int** a, int** c, int n)

{

    int k = 0;

    for (int x = 1; x < n; x++)

        for (int y = 1; y < n; y++)

            c[x][y] = a[x][y];

    int x, y, z  = 1 ;

    for (z = 1; z < n; z++)

        for (x = 1; x < n  ; x++)

            for (y = 1; y < n; y++) {

                c[x][y] |= c[x][z] && c[z][y];

                k++;

            }

    return k;

}//3.10

int tranzСlosure2(int** a, int** c1, int N) {

    int i, j,k=0 ;

    int** b, ** b1, **c2;

    for (i = 1; i < N; i++)

        for (j = 1; j < N; j++)

            c1[i][j] = a[i][j];

    c2 = get_mem(N);

    k += composition(c1, c1, c2, N);

    while (inclusion(c2,c1,N)) {

        k += unification(c1, c2, c1, N);

        k+= composition(c1, c1, c2, N);

    }

    return k;

}

//3.11

int tranzСlosure1(int** a, int** c, int N)

{

    int i, j, k = 0;

    int** b, ** b1;

    for (i = 1; i < N; i++)

        for (j = 1; j < N; j++)

            c[i][j] = a[i][j];

    b = get_mem(N);

    b1 = get_mem(N);

    for (i = 1; i < N; i++)

        for (j = 1; j < N; j++)

            b[i][j] = b1[i][j] = a[i][j];

    for (i = 2; i < N; i++){

        k += composition(b1, a, b, N);

        k += unification(c, b, c, N);

        for (i = 1; i < N; i++)

            for (j = 1; j < N; j++) {

                b1[i][j] = b[i][j];

                ++k;

            }

    }

    free_mem(b, N);

    free_mem(b1, N);

    return k;

}2. Усовершенствовать алгоритм 3.11 объединения степеней (АОС).

//3.11 усов.

int tranzСlosure1_up(int** a, int** c, int N)

{

    int i, j;

    int** b, ** b1, **I;

    for (i = 1; i < N; i++)

        for (j = 1; j < N; j++)

            c[i][j] = a[i][j];

    b = get_mem(N);

    b1 = get_mem(N);

    I = get_mem(N);