4.8. Упражнения и задачи

4.1. Для графов (орграфов), изображенных на рис. 4.10, показать их представление в виде последовательности ребер (дуг), матрицы смежности, матрицы весов, матрицы инцидентности, векторов смежности, списков смежности, сети и списковой структуры.

а) б) в)

0 (1.5) 2 d1 f1 0 2 1 4

c

d2 a

(1) (4) e 3

g 5 6

1 3 h

^(2.5)

^{г) д)}

(7)

3

1 (5) 2 (1) 5 2 5

(1) (2) (1) (1)

(4)

1 4 6

0 (2) 3 4

(3)

Рис. 4.10. Примеры графов

4.2. На рис. 4.11, показаны различные представления разных графов (орграфов). Изобразить эти графы и определить их основные характеристики: наличие / отсутствие ориентированности; наличие / отсутствие весов и меток; количество вершин и ребер (дуг); наличие / отсутствие связности; количество компонентов связности; наличие / отсутствие петель; наличие / отсутствие изолированных вершин; количество преемников и предшественников каждой вершины; степень каждой вершины и степень графа.

4.3. Дано количество вершин и последовательность дуг графа (орграфа):

а) 4, 3-0, 0-2, 2-3, 2-0, 1-1, 3-2, 0-3;

б) 5, 1-3-6, 4-0-1, 3-1-4, 2-3-5, 0-4-2, 3-2-5

(после каждой дуги указан ее вес);

в) 5, 4-2, 1-3, 0-4, 2-3, 1-4, 1-2, 4-3, 3-1.

Изобразить этот граф, определить, является ли он ориентированным или нет, и показать его представление (если таковое существует) в виде матрицы смежности, матрицы весов, матрицы инцидентности, векторов смежности, списков смежности, сети и списковой структуры.

а) Количество вершин 6, последовательность дуг:

0-1, 1-2, 3-5, 1-0, 3-2, 1-1, 0-2, 2-1, 5-3

б) Матрица в) Матрица г) Списки смежности

смежности инцидентности в параллельных

массивах

	0		1		2		3		4						0		1		2		3		4		5			6	Вершина Ссылки
0	0		1		1		0		0				0		1		1		0		0		0		1			0	Указатели списков				. . .
1	1		0		0		1		0				1		1		0		1		1		0		0			0			10		0	26
2	1		0		0		1		1				2		0		1		1		0		1		0			0			11		1	15
3	0		1		1		0		1				3		0		0		0		1		0		1			1			12		2	18
4	0		0		1		1		0				4		0		0		0		0		1		0			1			13		3	25
д) Матрица е) Векторы смежности весов																													Дуги		14		4	23
																															15		3	24
																															16		4	-1
																															17		1	21
		0		1		2		3		4								1		2		3		4							18		2	22
0		0		2		3		0		7						1		5		2		3		0							19		0	-1
1		4		0		0		5		0						2		4		2		0		0							20		4	17
2		3		0		0		0		5						3		3		1		2		5							21		2	-1
3		0		4		0		0		6						4		5		4		0		0							22		3	-1
4		7		0		5		8		0						5		2		1		4		0							23		3	17
																															24		0	-1
																														25			4	19
																														26			1	16
																																. . .

Рис. 4.11. Примеры представления графов

4.4. Для графов, изображенных на рис. 4.10 в, 4.10 г, 4.10 д, показать последовательность вершин

1) при обходе графа в глубину, начиная с веpшины 1;

2) при обходе графа в ширину, начиная с веpшины 1.

4.5. Для графов, изображенных на рис. 4.10 а, 4.10 в и 4.10 г, показать (изобразить)

1) матрицу связности;

2) матрицу расстояний;

3) матрицу кратчайших путей (как в алгоритме Флойда).

4.6. Описание списковой структуры. Составить описание данных для представления взвешенного орграфа в виде списковой структуры. Вес дуги - вещественное число.

4.7. Написать фрагмент программы вывода последовательности ребер данного неориентированного графа по его матрице смежности.

4.8. Получение списковой структуры. Написать фрагмент программы получения взвешенного орграфа, изображенного на рис. 10.1 а, и представленного в виде списковой структуры. Вес дуги - вещественное число.

4.9. Написать фрагмент программы (подпрограмму) получения

а) матрицы связности графа по алгоритму Уоршалла. Количество вершин графа не более 32. Биты каждой строки матрицы упакованы в виде переменной типа long.

б) матрицы расстояний и матрицы кратчайших путей графа по алгоритму Флойда , если количество вершин не превышает 20.

4.10. Составить описание данных для представления графа в виде

а) последовательности ребер (дуг), д) векторов смежности,

б) матрицы смежности, е) списков смежности,

в) матрицы весов, ж) сети,

г) матрицы инцидентности, з) списковой структуры.

Необходимые детали представления уточнить самостоятельно.

4.11. Составить фрагмент программы (подпрограмму) ввода графа и его преобразования из последовательности ребер (дуг) в

а) матрицу смежности; б) сеть; в) списковую структуру.

Необходимые детали представления уточнить самостоятельно.

4.12. Задан граф (орграф) в виде матрицы смежности. Составить программу (фрагмент программы, подпрограмму)

а) проверки, есть ли в графе петли;

б) поиска в графе изолированной вершины (не смежной с другими);

в) определения степени графа;

г) получения последовательности ребер.

4.13. Обработка сети. Задан орграф в виде регулярной сети с четырьмя ссылками, одна из которых указывает на следующую по порядку вершину, а остальные изображают дуги. Составить фрагмент программы подсчета количества предшественников вершины с номером 1 (количества вершин, от которых ведут дуги к вершине1).

4.14. Задан орграф в виде регулярной сети с четырьмя ссылками, одна из которых указывает на следующую по порядку вершину, а остальные изображают дуги. Составить фрагмент программы (подпрограмму)

а) подсчета количества вершин, не имеющих преемников;

б) определения номера вершины с максимальным количеством предшественников;

в) получения матрицы смежности орграфа.

4.15. Привести пример дерева и показать разные способы его представления. Указать последовательность вершин при обходе дерева в глубину и в ширину.

4.16. Составить фрагмент программы (подпрограмму) определения высоты данного дерева, представленного регулярной сетью.

Необходимые детали представления уточнить самостоятельно.

Указание: требуется обход дерева (раздел 4.3).

4.17. Составить фрагменты программы (подпрограммы) преобразования друг в друга пар: а-в, а-д, б-г, д-е, б-ж, ж-з представлений графа из задачи 4.10.

4.18. Дан граф (орграф). Составить описание данных для его представления и фрагмент программы

а) получения кратчайших путей и расстояний между всеми вершинами по алгоритму Флойда и вывода кратчайшего пути от вершины A до вершины B.

б) получения матрицы связности по алгоритму Уоршалла и вывода номеров вершин каждой компоненты связности графа.

4.19. Составить трассировочную таблицу обхода дерева из рис. 4.9 б по алгоритму 4.10 (раздел 4.3.5).

4.20. Составить нерекурсивные алгоритмы решения задачи обхода бинарного дерева из раздела 4.3.5 для трех способов обхода дерева: прямого, внутреннего и обратного. Представление дерева выбрать самостоятельно.

4.21. Дан граф (орграф) без циклов. Составить описание данных для его представления и фрагмент программы (подпрограмму)

а) проверки, существует ли путь от вершины A к вершине B.

б) поиска какого-либо пути от вершины A к вершине B.

4.22. Расстояние до всех вершин. Дана матрица весов взвешенного орграфа, причем веса всех дуг неотрицательны. Количество вершин не превышает 20. Написать фрагмент программы вычисления расстояний от заданной вершины до всех вершин.

4.23. Кратчайшие пути до всех вершин. Дополнить вычисление расстояний в задаче 4.22 получением кратчайших путей.

Указание. Дерево кратчайших путей можно представить в виде вектора, как в алгоритме обхода в ширину обычного не взвешенного графа. В этом случае получается обратная последовательность вершин каждого пути: от конца к началу.

4.24. Решить задачу 4.22 более быстрым методом за время О(n log n).

Указание: для поиска минимального элемента за время О(log n), вместо О(n), представить массив расстояний d для множества T алгоритма Дейкстры в виде бинарного дерева с помощью адресной арифметики (см. примеры 3.22 и 3.23 из раздела 3.3.3). Это обеспечит для алгоритма Дейкстры время работы О(n log n).

4.25. Оценить необходимый объем памяти для структур данных из задач: 4.1 - 4.3, 4.8, 4.9, 4.12. Недостающие детали представления уточнить самостоятельно.

4.26. Родственники (1-й турнир ICL, 2000). Требуется составить программу, которая вводит и выполняет последовательность команд двух видов: сообщения и запросы. Сообщения о рождении человека поступают в хронологическом порядке и требуют запоминания заданной информации. По запросу программа выдает информацию о характере родственной связи между двумя людьми. Сообщение о рождении человека по имени X имеет вид

X сын Y Z

или X дочь Y Z

где Y – имя матери, Z – имя отца.

Запрос “кем является человек по имени X для человека по имени Y” имеет вид

кто X для Y

Два человека являются родственниками, если у них есть общий предок. Характер родственной связи X и Y программа определяет в виде пары чисел m, n, равных, соответственно, расстоянию (количеству поколений) от X и от Y до их ближайшего общего предка. При этом человек считается собственным предком поколения 0.

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

Кроме того, прямой потомок или предок поколения более чем 2 именуется добавлением соответствующего количества приставок пра-, например: правнучка – дочь внучки или внука, праправнук – сын правнучки или правнука, прабабушка – мать бабушки или дедушки, прапрадедушка – отец прабабушки или прадедушки и т. д. Входной файл содержит последовательность команд. В этой последовательности не более 2000 различных имен. Длина имени не превышает 50 символов, при этом средняя длина всех имен не более 10 символов. Имена людей и служебные слова (сын, дочь, кто, для), из которых состоит команда, разделяются произвольным количеством разделителей - пробелов и/или символов новой строки. Команды отделяются друг от друга таким же образом. Имя может содержать любые символы, кроме разделителей.

Выходной файл состоит из ответов на запросы. Ответ начинается с новой строки и содержит числа m, n и название родственника (если имеется), разделяемые одним пробелом:

m n название

или слова “нет связи”, если отсутствует информация о родственной связи.

Пример входного файла: Выходной файл

Апполон сын Латона Зевс 0 1 отец

кто Зевс для Апполон 1 0 сын

Афродита дочь Диона Зевс 1 1 сестра

кто Апполон для Зевс нет связи

кто Афродита для Апполон

кто Апполон для Диона

4.27. Пробирки (Всероссийская олимпиада школьников, 1998). Имеются три пробирки вместимостью по 100 мл. На двух пробирках нанесены одинаковые риски, третья без рисок. Возле каждой риски надписано целое число миллилитров, которое вмещается в пробирку до этой риски. Изначально одна из пробирок с рисками наполнена 100 мл воды, а остальные две пустые. Составить программу, которая выясняет, можно ли отмерить в пробирку без рисок ровно 1 мл воды, и если да, то находит минимально необходимое для этого число переливаний. Воду можно переливать из одной пробирки в другую до тех пор, пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до какой-нибудь риски.

Входной файл содержит количество рисок n (n  20) и значения, приписанные рискам V[1], ..., V[n] (последняя риска считается сделанной на верхнем крае пробирки, числа разделены пробелами и/или переводом строки).

Выходной файл должен содержать слово YES и найденное число или NO:

YES (или NO)

минимальное число переливаний

4.28. Знакомство [45]. K членов клуба решили познакомиться (0<K100), организовав два вечера встреч. Известно, кто с кем уже знаком. Составить программу, определяющую, возможно или нет пригласить на каждую встречу только незнакомых друг с другом членов клуба (YES/NO). Если это возможно, то программа выдает номера членов клуба, приглашенных на каждую из встреч. Числа в файлах разделены пробелами и/или символами новой строки.

Входной файл:

K Количество членов клуба

1 N[1,1] N[1,2] ... Номера знакомых 1-го члена клуба

2 N[2,1] N[2,2] ... Номера знакомых 2-го члена клуба

. . .

K N[1,1] N[1,2] ... Номера знакомых K-го члена клуба

Выходной файл (три строки):

YES или NO

Номера участников первого вечера (если ответ YES)

Номера участников второго вечера (если ответ YES)

Пример входного файла: Выходной файл для этого примера:

5 YES

1 2 3 5 1 4

2 1 2 3 5

3 1

4 5

5 1 4