Вопросы_Графы

Вопрос 17
Графы. Определение, основные виды и способы задания.
Переход от одного способа задания к другому.
Задача. Найдите суммарную длину всех дорог в городе Новые Васюки. Схема дорог задана в виде весовой матрицы графа.
На некоторых дорогах введено одностороннее движение. Если длины дорог из пункта А в пункт Б разные, это означает, что есть две разные дороги.
Ссылка на теорию

Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=33227

Вопрос 18
Графы. Определения и способы задания. Подсчет основных характеристик графа.
Задача. Для заданного списком ребер графа проверьте, является ли он полным.
Входные данные
Сначала вводятся числа n ( 1≤ n ≤ 100 ) – количество вершин в графе и m ( 0≤ m ≤ n(n−1)/2 ) – количество ребер.
Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите  «YES», если граф является полным, и «NO» в противном случае.
Ссылка на теорию

Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=45659

Вопрос 19
Двудольные графы.  Определение, свойства. 
Задача. Двудольный граф
Дан граф. Требуется проверить, является ли он двудольным, и если да, то раскрасить его вершины.
Входные данные
В первой строке задано сначала число N - количество вершин графа (не превышает 100).
Далее идет матрица смежности - матрица размером NxN из 0 и 1 (0 обозначает отсутствие ребра, 1 - наличие).
Граф неориентированный, без петель.
Выходные данные 
В первую строку выведите одно из сообщений YES или NO (в зависимости от того, является ли граф двудольным или нет).
В случае ответа YES, во второй строке выведите N чисел - цвета, в которые нужно раскрасить вершины: 
для первого цвета используйте значение 1, для второго цвета - значение 2. 
Первая вершина должна иметь цвет 1.

Ссылка на теорию
https://www.silvertests.ru/OlympTask.aspx?Id=33138
Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=33138
 

Вопрос 20
Графы. Метод обхода графа в ширину (BFS).
Задача «Один конь».
На шахматной доске NxM в клетке (x1, y1) стоит голодный шахматный конь.
Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава.
Какое наименьшее количество ходов он должен для этого сделать?
Ссылка на теорию
https://www.silvertests.ru/CourseTask_NoteBook.aspx?Id=50271&IDCourse=40076
Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=33251

 

Вопрос 21
Графы. Метод обхода графа в ширину (BFS).
Задача «Преобразуем число».
Витя хочет придумать новую игру с числами.
В этой игре от игроков требуется преобразовывать четырехзначные числа не содержащие нулей
при помощи следующего разрешенного набора действий: Входные данные 
На вход подаются два различных четырехзначных числа, каждое из которых не содержит нулей. Каждое число с новой строки
Выходные данные 
Программа должна вывести последовательность четырехзначных чисел, не содержащих нулей.
Последовательность должна начинаться первым из данных чисел и заканчиваться вторым из данных чисел,
каждое последующее число в последовательности должно быть получено из предыдущего числа применением одного из правил.
Количество чисел в последовательности должно быть минимально возможным.
Ссылка на теорию
https://www.silvertests.ru/CourseTask_NoteBook.aspx?Id=50271&IDCourse=40076
Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=37016

Вопрос 22
Графы. Метод обхода графа в ширину (BFS).
Задача «Два коня».
На стандартной шахматной доске (8х8) живут 2 шахматных коня: Красный и Зеленый.
Обычно они беззаботно скачут по просторам доски, пощипывая шахматную травку, но сегодня особенный день:
у Зеленого коня День Рождения. Зеленый конь решил отпраздновать это событие вместе с Красным.
Но для осуществления этого прекрасного плана им нужно оказаться на одной клетке.
Заметим, что Красный и Зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди,
а одновременно, и если оказываются на одной клетке, никто никого не съедает.
Сколько ходов им потребуется, чтобы насладиться праздником?
Ссылка на теорию
https://www.silvertests.ru/CourseTask_NoteBook.aspx?Id=50271&IDCourse=40076
Ссылка на задачу
https://www.silvertests.ru/OlympTask.aspx?Id=38628