Skip to main content

Пример

В этом задании всегда даётся граф, в котором русскими буквами пронумерованы вершины. Лирическое отступление задачи говорит о том, что это не граф, а схема дорог в каком-то регионе или области. Рёбра - это дороги, вершины - населённые пункты. Иногда граф взвешенный, тогда вес рёбер связывают с длиной соответствующих дорог.

Помимо графа в задании даётся матрица смежности(весовая матрица) в форме таблицы с неназванными вершинами.

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

Представления и перестановки​

Как вы понимаете, способов табличной записи графа у нас довольно много, а точнее, n!, где n - кол-во вершин. Почему n!, объясняется в комбинаторике.

Два различных представления одного и того же графа:

Два различных представления одного и того же графа

Мы поменяли местами в таблице столбцы "Б" и "В" и строки "Б" и "В". Хотя таблицы описывают один и тот же граф, но выглядят они по-разному. Эти таблицы - разные представления графа. Над множеством представлений можно определить операцию перехода. т.е. действие над представлениями, чтобы из одного получить другое. Эта операция перехода, на самом деле, - простая перестановка.

Если какое-то из представлений мы выберем эталонным (конечно, удобнее всего эталонным представлением взять таблицу связности, где все вершины расположены в алфавитном порядке), тогда всем остальным представлениям можно сопоставить упорядоченное множество (массив с уникальными элементами) индексов от 0 до n-1, где n - кол-во вершин в графе. Любому представлению соответствует свой однозначно определённый массив. Такой массив будем дальше называть перестановкой. Верно и обратное: любому массиву индексов соответствует своё представление. Такое соотнесение называют биекцией. Доказывать строго это утверждение не будем.

Давайте просто рассмотрим на нашем графе общую логику соотнесения. Рассмотрим перестановку p = {0, 1, 2, 4, 3}. Как нам определить, какому представлению он соответствует?

Представления1

Чтобы установить порядок букв, запишем названия вершин как массив names[] = {'А', 'Б', 'В', 'Г', 'Д'}.

Индекс, стоящий на i-ой позиции соответствует индексу нужной нам буквы. Например, нам нужно установить букву, стоящую четвёртой. Тогда мы должны взять из перестановки элементы с индексом 3 (напомню, позиции нумеруются с нуля). p[3] равно четырём. Тогда смотрим на четвёртый элемент массива: names[4] равен Д.

Представления2

Перебрав таким образом все позиции, мы установили, что вершины в представлении идут в таком порядке: {'А', 'Б', 'В', 'Д', 'Г'}

Представления2

Теперь определим значение, лежащее, например, в ячейке [Б, Д]. Т.е. какой вес у ребра, идущего из вершины Б в вершину Д.

Для этого опять же воспользуемся массивом-перестановкой. Только теперь нам нужно получить не один индекс, а два. Ячейка [Б, Г] соответсвует индексам [1, 4]. Из перестановки получаем для первого индекса значение 1, для второго - '3'. Т.о. в эталонном представлении вес нужного нам ребра находится в ячейке с индексами [1,3]. Там стоит число 5. Переносим его в наше новое представление, и получаем:

Представления2

Перебрав таким образом все элементы, мы получим представление:

Представления2

Это полностью алгоритмический подход. Зная расположение букв, нам уже не надо соотносить индексы, мы можем легко ориентироваться по буквам, смотря на две таблицы. Но компьютер так не умеет. Да, он может научиться определять положение букв, но в итоге всё в итоге сведётся к массиву-перестановке.

Решение​

Задание

(№ 4145) (Е. Джобс) На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите длину дороги между пунктами А и Б, если известно, что длина дороги между Г и Д меньше длины дороги между Г и Е. Передвигаться можно только по указанным дорогам. Задание 1

В первую очередь нам нужно строго записать входные данные. Назовём первую матрицу source и просто запишем на удобном нам языке программирования, а вторую матрицу построим по графу, представленному справа. В нём нам не известны длины, но известна связность. Поэтому каждый элемент матрицы равен 0 или 1. Саму матрицу будем называть target.

Т.е. target - эталонное представление. Дальше в коде будет использоваться переменная SIZE, она хранит в себе кол-во вершин графа и используется для удобства.

    // кол-во вершин (используется для удобства)
    static int SIZE = 7;
    //       П1  П2  П3  П4  П5  П6  П7
    int[][] source = new int[][]{
            {0 , 10, 15, 0 , 0 , 0 , 0 }, // П1
            {10, 0 , 0 , 13, 17, 0 , 0 }, // П2
            {15, 0 , 0 , 0 , 19, 0 , 9 }, // П3
            {0 , 14, 0 , 0 , 10, 20, 11}, // П4
            {0 , 17, 19, 10, 0 , 0 , 20}, // П5
            {0 , 0 , 0 , 20, 0 , 0 , 25}, // П6
            {0 , 0 , 9 , 11, 20, 25, 0 }  // П7
    };
    //       А  Б  В  Г  Д  Е  Ж
    int[][] target = new int[][]{
            {0, 1, 1, 0, 0, 0, 0}, // A
            {1, 0, 0, 1, 1, 0, 0}, // Б
            {1, 0, 0, 1, 0, 1, 0}, // В
            {0, 1, 1, 0, 1, 1, 0}, // Г
            {0, 1, 0, 1, 0, 1, 1}, // Д
            {0, 0, 1, 1, 1, 0, 1}, // Е
            {0, 0, 0, 0, 1, 1, 0}  // Ж
    };

Теперь нам нужно создать все перестановки длины 7, потому что у нас 7 вершин. Для этого воспользуемся рекурсией.

    // поменять местами элементы массива arr с индексами l и r
    public static void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
    // функция-генератор перестановок
    static void permute(int[] p, int pos) {
        // Если мы дошли до последнего элемента
        if (pos == p.length - 1) {
            processPermutation(p);
        } else { // иначе
            // Перебираем все оставшиеся элементы
            for (int i = pos; i < p.length; i++) {
                // меняем местами текущий элемент и перебираемый
                swap(p, pos, i);
                // Вызываем Рекурсию для следующего элемента
                permute(p, pos + 1);
                // меняем местами обратно
                swap(p, pos, i);
            }
        }
    }

Рассмотрим теперь функцию-обработчик перестановок:

    // обработка перестановки
    static void processPermutation(int[] arr) {
        // нужна проверка связности, т.е. того, что при перестановке все связи сохраняются, те не
        // обратятся в ноль
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                // если в эталонном представлении связь между вершинами есть,
                // а в данном в задании - нет
                if (target[i][j] > 0 && source[arr[i]][arr[j]] == 0)
                    // заканчиваем выполнение обработчика, потому такая перестановка
                    // создаёт представление, не совместимое с данным, а значит, нас не
                    // интересует
                    return;
            }
        }
        // здесь мы уже выполняем проверку, определённую заданием

        // расстояние между Г и Д
        int gdDistance = source[arr[3]][arr[4]];
        // расстояние между Г и Е
        int geDistance = source[arr[3]][arr[5]];
        // расстояние между А и Б
        int abDistance = source[arr[0]][arr[1]];
        // если расстояние ГД меньше ГЕ, то комбинация нам подходит
        if (gdDistance < geDistance) {
            // выводим расстояние
            System.out.println(abDistance);
        }
    }
о стартовом массиве

Стартовый массив для рекуррентной генерации перестановок у нас указан вручную. Это сделано для упрощения. Но помните, что если изменится количество вершин, должен измениться и стартовый массив.

Чтобы вывести названия вершин, нам нужно получить обратную перестановку по заданной. Т.е. перестановку, при помощи которой из source можно target. Поэтому добавим функцию getReversePermutation(), которая по заданной перестановке возвращает обратную ей. Это нам понадобится для того, чтобы восстановить названия вершин в source представлении. Когда мы считали длины рёбер, мы использовали прямое преобразование. Мы как бы смотрели на target через source. А с названиями, наоборот, мы смотрим на source через target. Поэтому и перестановка обратная

    // получить обратную перестановку
    static int[] getReversePermutation(int[] arr) {
        int[] reverse = new int[arr.length];
        for (int i = 0; i < SIZE; i++) {
            reverse[arr[i]] = i;
        }
        return reverse;
    }

В C++ коде русские буквы заменены латиницей, потому что из коробки этот замечательный язык с ними работать не умеет, а подключение такой возможности зависит от платформы. В обработчик подходящих комбинаций теперь можно добавить следующий код.

            ...
            // получаем обратную перестановку
            int [] reverse = getReversePermutation(arr);
            // выводим названия вершин
            for (int i = 0; i < SIZE; i++) {
                System.out.print(names[reverse[i]] + " ");
            }
            System.out.println();
            ...

Подводя итог: наша программа запускает рекуррентную функцию, та генерирует все перестановки заданной длины и для каждой перестановки проверяет, можно ли с её помощью получить из эталонного представления заданное.

public class Example1 {

    // кол-во вершин (используется для удобства)
    static int SIZE = 7;

    // названия вершин
    static char[] names = {'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ж'};

    //      П1  П2  П3  П4  П5  П6  П7
    static int[][] source = new int[][]{
            {0, 10, 15, 0, 0, 0, 0}, // П1
            {10, 0, 0, 13, 17, 0, 0}, // П2
            {15, 0, 0, 0, 19, 0, 9}, // П3
            {0, 14, 0, 0, 10, 20, 11}, // П4
            {0, 17, 19, 10, 0, 0, 20}, // П5
            {0, 0, 0, 20, 0, 0, 25}, // П6
            {0, 0, 9, 11, 20, 25, 0}  // П7
    };
    //       А  Б  В  Г  Д  Е  Ж
    static int[][] target = new int[][]{
            {0, 1, 1, 0, 0, 0, 0}, // A
            {1, 0, 0, 1, 1, 0, 0}, // Б
            {1, 0, 0, 1, 0, 1, 0}, // В
            {0, 1, 1, 0, 1, 1, 0}, // Г
            {0, 1, 0, 1, 0, 1, 1}, // Д
            {0, 0, 1, 1, 1, 0, 1}, // Е
            {0, 0, 0, 0, 1, 1, 0}  // Ж
    };

    // степени вершин
    static int[] sourceSum = new int[SIZE];
    static int[] targetSum = new int[SIZE];

    // получить обратную перестановку
    static int[] getReversePermutation(int[] arr) {
        int[] reverse = new int[arr.length];
        for (int i = 0; i < SIZE; i++) {
            reverse[arr[i]] = i;
        }
        return reverse;
    }


    // обработка перестановки
    static void processPermutation(int[] arr) {
        // проверяем, что в представлениях совпадают степени вершин
        for (int i = 0; i < SIZE; i++) {
            if (sourceSum[arr[i]] != targetSum[i]) {
                return;
            }
        }

        // нужна проверка связности, т.е. того, что при перестановке все связи сохраняются, те не
        // обратятся в ноль
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                // если в эталонном представлении связь между вершинами есть,
                // а в данном в задании - нет
                if (target[i][j] > 0 && source[arr[i]][arr[j]] == 0)
                    // заканчиваем выполнение обработчика, потому такая перестановка
                    // создаёт представление, не совместимое с данным, а значит, нас не
                    // интересует
                    return;
            }
        }
        // здесь мы уже выполняем проверку, определённую заданием

        // расстояние между Г и Д
        int gdDistance = source[arr[3]][arr[4]];
        // расстояние между Г и Е
        int geDistance = source[arr[3]][arr[5]];
        // расстояние между А и Б
        int abDistance = source[arr[0]][arr[1]];
        // если расстояние ГД меньше ГЕ, то комбинация нам подходит
        if (gdDistance < geDistance) {
            // получаем обратную перестановку
            int [] reverse = getReversePermutation(arr);
            // выводим названия вершин
            for (int i = 0; i < SIZE; i++) {
                System.out.print(names[reverse[i]] + " ");
            }
            System.out.println();
            // выводим расстояния
            System.out.println(abDistance + " " + gdDistance + " " + geDistance);
        }

    }

    // поменять местами элементы массива arr с индексами l и r
    public static void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }


    // функция-генератор перестановок
    static void permute(int[] p, int pos) {
        // Если мы дошли до последнего элемента
        if (pos == SIZE - 1) {
            processPermutation(p);
        } else { // иначе
            // Перебираем все оставшиеся элементы
            for (int i = pos; i < SIZE; i++) {
                // меняем местами текущий элемент и перебираемый
                swap(p, pos, i);
                // Вызываем Рекурсию для следующего элемента
                permute(p, pos + 1);
                // меняем местами обратно
                swap(p, pos, i);
            }
        }
    }

    // главный метод программы
    public static void main(String[] args) {
        // рассчитываем взвешенные степени
        for (int i = 0; i < SIZE; i++) {
            sourceSum[i] = 0;
            targetSum[i] = 0;
            for (int j = 0; j < SIZE; j++) {
                // в исходном представлении надо не забыть заменить ненулевые веса единицей
                sourceSum[i] += Math.signum(source[i][j]);
                targetSum[i] += target[i][j];
            }
        }
        // запускаем генерацию перестановок
        permute(new int[]{0, 1, 2, 3, 4, 5, 6}, 0);
    }

}

На выходе получим:

А Б В Д Г Ж Е
10 10 20

Ответ: 10