Шаг 199.
Основы языка Haskell.
Реализация алгоритмов на графах... . Задачи для самостоятельного решения

    На этом шаге мы приведем задачи для самостоятельного решения.

Определения, необходимые для решения задач.
  • (1) Совершенным числом называется натуральное число, равное сумме всех своих делителей, не считая его самого. Например, 6=1+2+3 - совершенное число.

  • (2) Дружественными числами называется пара чисел, обладающих таким свойством: сумма собственных делителей первого из них равна второму числу, а сумма собственных делителей второго числа равна первому числу.

        Например, сумма делителей числа 220 равна

       1+2+4+5+10+11+20+22+44+55+110=284,
    
    а сумма делителей числа 284 равна 220.

  • (3) Палиндромическим числом называется натуральное число, "читаемое" одинаково с обеих сторон. Например, 171 - палиндромическое число.

  • (4) Средней плотностью графа называется частное от деления количества его рёбер на количество вершин.


   Замечание. Найдите ошибки, описки, неточности и прочие изъяны в приведенных задачах.

1. Обход графов в глубину

    1*. Используя обход в глубину, определите количество вершин в связном неориентированном графе.

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

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

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

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

    6*. Перенумеруйте вершины связного неориентированного графа в порядке обхода в глубину.

    7*. (По [1, с.165]) Перенумеруйте вершины связного неориентированного графа в порядке обхода в глубину и вычислите среднюю плотность графа. Можно ли оба эти действия выполнить за один обход графа?

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

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

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

    11. Используйте обход связного неориентированного графа в глубину для определения всех вершин, находящихся на фиксированном расстоянии D от данной вершины.

2. Обход графов в ширину

    0*. Дайте название методу, отличающемуся от поиска в ширину на связном неориентированном графе только тем, что вновь достигнутая вершина помещается не в очередь, а в стек.

    1*. Используя обход в ширину, определите количество вершин в связном неориентированном графе.

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

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

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

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

    6*. Перенумеруйте вершины связного неориентированного графа в порядке обхода в ширину.

    7*. (По [1, с.165]) Перенумеруйте вершины неориентированного графа в порядке обхода в ширину и вычислите среднюю плотность графа. Можно ли оба эти действия выполнить за один обход графа?

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

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

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

    11. Используйте обход связного неориентированного графа в ширину для определения всех вершин, находящихся на фиксированном расстоянии D от данной вершины.

3. Вычисление компонентов связности графа

    1. Покажите на нескольких графах, что в связном графе имеется единственный связный компонент, совпадающая с самим графом.

    2. Реализуйте алгоритм проверки связности графа, изложенный в монографии [2, с.198-205].

4. Построение остовного дерева связного графа

    1*. Реализуйте алгоритм превращения заданного графа в дерево.


(1)Дмитриева М.В., Кубенский А.А. Турбо Паскаль и Турбо Си: построение и обработка структур данных. СПб.: Изд-во СПбГУ, 1996. - 192 с.
(2)Пападимитриу Х., Стайнглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.

    Со следующего шага мы начнем рассматривать классы и их экземпляры.




Предыдущий шаг Содержание Следующий шаг