7.7. *** Графы

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

1. Найти все вершины заданного графа, недостижимые от заданной его вершины.

2. Определить, что для любой пары вершин заданного орграфа одна из этих вершин достижима от другой.

3. Определить, является ли связным заданный граф.

4. Найти длину кратчайшего цикла в графе.

5. Для двух выделенных вершин графа построить соединяющий их простой путь.

6. Найти самый длинный простой путь в графе.

7. Найти все вершины графа, к которым существует путь заданной длины от выделенной его вершины.

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

9. Источником орграфа назовем вершину, от которой достижимы все другие вершины; стоком – вершину, достижимую от всех других вершин. Найти все источники и стоки данного орграфа.

10. Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными (различными) вершинами и отлична от каждой из них.

11. Найти диаметр графа, т. е. максимум расстояний между всевозможными парами его вершин.

12. Найти медиану графа, т. е. такую его вершину, что сумма расстояний от нее до остальных вершин минимальна.

8. Классы

8.1. Класс «Многоразрядное число»

8.1.1. Объявить класс для решения задачи и определить его методы.

Реализовать:

• три вида конструктора (без аргументов, инициализации, копирования),

• деструктор,

• ввод данных с клавиатуры,

• вывод данных на экран,

• указанные в задании операции реализовать посредством перегрузки операций (операции реализовать и как методы класса, и как внешние дружественные функции).

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

Дополнительно к требуемым в заданиях операциям перегрузить операцию индексирования []. Максимально возможный размер массива задать константой. В отдельном поле size должно храниться максимальное для данного объекта количество элементов массива; реализовать метод get_size(), возвращающий установленную длину. Если количество элементов массива изменяется во время работы, определить в классе поле count. Первоначальные значения size, count устанавливаются конструктором. Обеспечить работу с безопасным массивом, т.е. контролировать выход индекса элемента массива за допустимый описанием объекта диапазон.

1. Объявить класс «128-разрядное целое положительное десятичное число». Реализовать операции: сложения, умножения этих чисел.

2. Объявить класс «128-разрядное целое положительное десятичное число. Реализовать операции: сравнения, сдвигов на n разрядов (десятичных).

3. Объявить класс «256-разрядное целое положительное десятичное число. Реализовать операции: сложения, умножения этих чисел.

4. Объявить класс «256-разрядное целое положительное десятичное число». Реализовать операции: сравнения, сдвигов на n разрядов (десятичных).

5. Объявить класс «64-разрядное целое двоичное число со знаком». Реализовать операции: сложения, умножения. Создать методы для перевода десятичного числа в двоичное, и наоборот.

6. Объявить класс «64-разрядное целое положительное двоичное число». Реализовать операции: сравнения, сдвигов на n разрядов, поразрядные. Создать методы для перевода десятичного числа в двоичное, и наоборот.

7. Объявить класс «128-разрядное целое двоичное число со знаком». Реализовать операции: сложения, умножения. Создать методы для перевода десятичного числа в двоичное, и наоборот.

8. Объявить класс «128-разрядное целое положительное двоичное число». Реализовать операции: сравнения, сдвигов на n разрядов, поразрядные. Создать методы для перевода десятичного числа в двоичное, и наоборот.

9. Объявить класс «64-разрядное целое шестнадцатиричное положительное число». Реализовать операции: сложения, умножения. Создать методы для перевода десятичного числа в шестнадцатиричное, и наоборот.

10. Объявить класс «64-разрядное целое шестнадцатиричное положительное число». Объявить класс «256-разрядное целое положительное двоичное число». Реализовать операцию сложения для тех и других чисел. Создать методы для перевода двоичного числа в шестнадцатиричное, и наоборот.

11. Объявить класс «64-разрядное целое положительное число в p-ричной с/с (2≤p≤16)». Реализовать операции: сложения, умножения. Создать методы для перевода десятичного числа в р-ричное и наоборот.

12. Объявить класс «64-разрядное целое положительное число в p-ричной с/с (2≤p≤16)». Реализовать операции: сравнения, сдвигов на n разрядов. Создать методы для перевода десятичного числа в р-ричное и наоборот.

8.1.2. Реализовать задание, используя объявление и методы соответствующего параметризированного класса из стандартной библиотеки шаблонов STL.