Статья Автор: Лебедев Дмитрий

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

Вопрос 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).
Задача «Преобразуем число».
Витя хочет придумать новую игру с числами.
В этой игре от игроков требуется преобразовывать четырехзначные числа не содержащие нулей
при помощи следующего разрешенного набора действий:
    1. Можно увеличить первую цифру числа на 1, если она не равна 9.
    2. Можно уменьшить последнюю цифру на 1, если она не равна 1.
    3. Можно циклически сдвинуть все цифры на одну вправо.
    4. Можно циклически сдвинуть все цифры на одну влево.
Входные данные 
На вход подаются два различных четырехзначных числа, каждое из которых не содержит нулей. Каждое число с новой строки
Выходные данные 
Программа должна вывести последовательность четырехзначных чисел, не содержащих нулей.
Последовательность должна начинаться первым из данных чисел и заканчиваться вторым из данных чисел,
каждое последующее число в последовательности должно быть получено из предыдущего числа применением одного из правил.
Количество чисел в последовательности должно быть минимально возможным.
Ссылка на теорию
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
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать