11 класс Часть I задания части I выполняются во время проведения зачётной работы



Скачать 184.91 Kb.
Дата06.07.2013
Размер184.91 Kb.
ТипДокументы

Алгоритмы на графах

Индивидуальные задания к зачету

11 класс


Часть I

Задания части I выполняются во время проведения зачётной работы.

  1. Для заданного графа выполните следующие задания (при необходимости пронумеруйте вершины графа):

  1. Запишите матрицу смежности графа.

  2. Запишите граф в виде списка рёбер.

  3. Определите степени вершин графа.

  4. Определите, является ли граф полным.

  5. Определите, является ли граф связным. Если нет, назовите количество компонент связности.

  6. Определите, является ли граф ориентированным.

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

  8. Начертите дерево обхода графа по алгоритму BFS.

  9. Начертите дерево обхода графа по алгоритму DFS.

  10. Перечислите вершины графа в порядке их полного просмотра («окраски» в чёрный цвет) по алгоритму BFS.

  11. Перечислите вершины графа в порядке их полного просмотра («окраски» в чёрный цвет) по алгоритму DFS.

  12. Определите, содержит ли граф простые циклы. Если да, то назовите хотя бы один такой цикл.

  13. Определите, содержит ли граф Эйлеров путь. Если да, перечислите вершины графа в порядке их прохождения по Эйлерову пути.

  14. Определите, содержит ли граф Эйлеров цикл. Если да, перечислите вершины графа в порядке их вхождения в цикл.


















  1. Граф задан матрицей смежности.
    Как по этой матрице определить:

  1. вид графа;

  2. число вершин графа;

  3. число ребер, выходящих из вершины;

  4. число ребер, входящих в вершину?




  1. Создайте граф, соответствующий матрице смежности:











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




  1. Постройте граф соответствующий следующим результатам соревнований: команда А выиграла у В и С, и сыграла вничью с D; В проиграла А, сыграла вничью с С и выиграла у D; С проиграла А, выиграла у D и сыграла вничью с В; D сыграла вничью с А и проиграла В и С. Определите команду-победителя.




  1. Нарисуйте полный граф с n вершинами и подсчитайте количество ребер, если:
    a) n=2; b) n=9; c) n=15.
    Ответьте на вопрос: сколько ребер у полного графа с n вершинами?




  1. В доме отдыха Вишкиль 57 корпусов. Электрик решил соединить телефонными проводами каждый корпус ровно с пятью другими. Сможет ли он это сделать?




  1. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?




  1. В деревне Вишкиль 9 домов. Из каждого дома тянется четыре шланга к четырём другим домам. Сколько шлангов в деревне?




  1. Чему равна сумма степеней входа всех вершин графа, если сумма степеней выхода всех вершин равна 45?




  1. Какой граф называется регулярным?




  1. Какой граф называется полным?




  1. Сколько рёбер в полном графе с 20 вершинами?




  1. Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?




  1. Верно ли следующее утверждение: число нечетных вершин любого графа четно. Почему? Проверьте это на примере.




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




  1. Существуют ли графы, степени вершин которых равны:

a) 8, 7, 5, 4, 4, 3, 2, 2, 2;

b) 8, 7, 6, 5, 4, 4, 3, 2, 1?

Если да, то постройте их.


  1. На рисунке ниже изображен граф. Определите степень входа и степень выхода каждой его вершины.




  1. Выполните задания.

1. Создайте граф с пятью вершинами, который не является связным.

2. "Дорисуйте" граф, чтобы он стал связным.


  1. Найдите пути, связывающие вершины 2 и 5 в графе на рис. Существует ли простой путь, соединяющий эти вершины?

(Путь от A1 до An называется простым, если он не проходит ни через одну из вершин графа более одного раза.)




  1. Найдите в графе на рис. циклы, содержащие:

а) 4 ребра; б) 7 ребер; в) 11 ребер.
Есть ли среди них простые?

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




  1. Определите, можно ли нарисовать следующий рисунок, не отрывая карандаша от бумаги. Объясните своё решение.




  1. Поле разбито межами на несколько участков (см. рис). Землемер захотел, не выходя за пределы поля, пройти по нему так, чтобы пересечь каждую межу ровно один раз. Удастся ли ему это?



  1. Создайте простой цикл с 9 вершинами. Подсчитайте количество ребер.
    Сколько ребер содержит цикл с 20 вершинами (с n вершинами)?




  1. Муравей забрался в банку из-под сахара, имеющую форму куба. Сможет ли он последовательно обойти все рёбра куба, не проходя дважды по одному ребру?




  1. Дана карта участка реки Волошихи. Требуется обойти все 13 мостов, соединяющих острова и берега этой реки, так, чтобы каждый мост оказался пройденным не более одного раза. Возможно ли это?




  1. Людоед захватил маленькую принцессу. Он нарисовал на земле k квадратов в ряд. Людоед обещал отпустить принцессу, если она сможет пропрыгать по всем квадратам по разу и снова вернуться на первый, при этом прыгать с любого квадратика на соседний нельзя, можно прыгать только через один или через два квадратика (например, с 5 можно прыгнуть только на 2, 3, 7 или 8). Если принцесса не выполнит задание, людоед её съест. Как принцессе спастись при

а) k=5;

б) k=10?
Часть II

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


Представление графа. Характеристики графа

Задача №1

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

Задача №2

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

Задача №3

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

Задача №4

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

Задача №5

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

Задача №6

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

Задача №7

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

Задача №8

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

Задача №9

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

Задача №10

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

Задача №11

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

Задача №12

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

Задача №13

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

Задача №14

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

Задача №15

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

Задача №16

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

Задача №17

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

Задача №18

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

Задача №19

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

Задача №20

Напишите программу, определяющую, является ли граф, заданный матрицей смежности, звездой (звезда – граф, у которого одна вершина соединена со всеми, а у остальных степень равна 1).

Обход графа. DFS и BFS

Задача №21

Алгоритм BFS

Для графа, заданного матрицей смежности, вывести номера вершин в порядке их просмотра по алгоритму BFS. Просмотр начинается с заданной вершины.

Задача №22

Алгоритм DFS

Орграф задан количеством вершин и матрицей смежности.

Договорились в процессе выполнения обхода графа называть непросмотренные вершины «белыми», частично просмотренные – «серыми», а полностью просмотренные – «чёрными».

До обработки все вершины орграфа белые. Необходимо с помощью алгоритма DFS (обход в глубину) «перекрасить» все вершины графа в чёрный цвет. При этом начинать просмотр нужно каждый раз с такой «белой» вершины, номер которой наименьший.

В качестве ответа нужно вывести номера вершин в порядке их «раскраски» в чёрный цвет.

Задача №23

Проверка связности

Проверить, является ли граф, заданный матрицей смежности, связным.

Задача №24

Достижимость

Для заданной вершины графа определить количество вершин, достижимых из неё. Граф задан матрицей смежности.

Задача №25

Достижимость-2

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

Задача №26

Достижимость-3

Граф задан матрицей смежности. Задана одна из вершин графа. Найти все вершины, из которых существует путь в данную.

Задача №27

Компоненты связности

Для графа, заданного матрицей смежности, определить количество компонент связности.

Задача №28

Путь заданной длинны

Для графа, заданного матрицей смежности, определить, существует ли путь длинной L между двумя данными вершинами.

Задача №29

Знакомые

На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Можно ли опосредованно перезнакомить их всех между собой? (Незнакомые люди могут познакомиться только через общего знакомого).

Задача №30

Кольцо

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

Поиск кратчайшего пути

Задача №31

Кратчайшие пути

Найти кратчайшие пути из одной вершины взвешенного ориентированного графа во все остальные. Гарантируется, что в графе нет циклов отрицательного веса. Граф задаётся матрицей смежности.

Задача №32

Флойд

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

По его матрице смежности постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса. Граф задаётся матрицей смежности.

Задача №33

Флойд-Max

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

Входные данные:

В первой строке входного файла единственное число: N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует ребру из вершины i в вершину j): -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы - всегда нули.

Выходные данные:

Вывести искомое максимальное кратчайшее расстояние.

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

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

4

0 5 9 -1

-1 0 2 8

-1 -1 0 7

4 -1 -1 0

16


Задача №34

Флойд-Min

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

Входные данные:

В первой строке входного файла единственное число: N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует ребру из вершины i в вершину j): -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы - всегда нули.

Выходные данные:

Вывести искомое минимальное кратчайшее расстояние.

Задача №35

Задача о дорогах

Есть дома и дороги, их соединяющие. Также заданы длины дорог. Найти кратчайшую длину пути от города s до города k, если двигаться можно только по дорогам.

Задача №36

Города и дороги

Имеется N городов. Для каждой пары городов (I,J) можно построить дорогу, соединяющую эти два города и не заходящие в другие города. Стоимость такой дороги A(I,J). Вне городов дороги не пересекаются.

Написать алгоритм для нахождения самой дешевой системы дорог, позволяющей попасть из любого города в любой другой. Результаты задавать таблицей B[1:N,1:N], где B[I,J]=1 тогда и только тогда, когда дорогу, соединяющую города I и J, следует строить.

Задача №37

Дома и дороги

Вводится N - количество домов и К - количество дорог. Дома пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел - двумя номерами домов - концов дороги и длиной дороги. В каждом доме живет по одному человеку. Найти такой дом - место встречи всех людей, от которого суммарное расстояние до всех других домов будет минимальным.

Примечание: длины дорог - положительные целые числа.

Задача №38

Флойд-существование

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

вершин определить, существует ли кратчайший путь между ними или нет.

Комментарий:

Кратчайший путь может не существовать по двум причинам:

-Нет ни одного пути

-Есть пути сколь угодно маленького веса

Входные данные:

В первой строке входного файла записано единственное число: N (1 ≤ N ≤ 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j): число 0 обозначает отсутствие ребра, а любое другое число – наличие ребра соответствующего веса. Все числа по модулю не превышают 100.

Выходные данные:

Выведите N строк по N чисел. j-ое число в i-ой строке должно соответствовать кратчайшему пути из вершины i в вершину j. Число должно быть равно 0, если пути не существует, 1 - если существует кратчайший путь, и 2 - если пути существуют, но бывают пути сколь угодно маленького веса.

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

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

5

0 1 2 0 0

1 0 3 0 0

2 3 0 0 0

0 0 0 4 -1

0 0 0 -1 0

1 1 1 0 0

1 1 1 0 0

1 1 1 0 0

0 0 0 2 2

0 0 0 2 2

Задача №39

Кратчайший путь

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

Ограничения

Максимальное количество вершин не больше 100.

Входные и выходные данные

Во входном файле в первой строке два числа - n - количество вершин в графе, и m - число ребер в графе. В следующей строке номера начальной и конечной вершины. Далее, в m строчках записаны по три числа, описывающие по одному ребру. Первое число - номер вершины, из которой идет ребро, второе - номер вершины куда идет ребро, третье число - вес ребра (от 0 до 1000). В файл output.txt необходимо выдать стоимость кратчайшего пути из начальной вершины в конечную, и затем сам этот путь: номера вершин через пробел, включая начальную и конечную вершину.

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

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

4 5

2 3

2 1 1

2 3 25

4 3 10

2 4 2

1 3 3

1 2 0

4

2 1 3

Задача №40

Самый длинный путь

Найти самые длинные дороги между всеми парами вершин взвешенного ориентированного графа. Граф задаётся матрицей смежности.

Задача №41

Длинна максимального пути

Для заданной вершины взвешенного ориентированного графа определить максимальные длины путей из этой вершины во все остальные. Граф задаётся матрицей смежности.

Задача №42

Второй путь

Для заданного матрицей смежности ориентированного взвешенного графа и заданной вершины определить второй по величине наименьший путь из этой вершины. Вывести длину найденного пути. Если такого пути не существует, вывести ‘NO SOLUTION’.

Задача №43

Второй путь-2

Задано N городов c номерами от 1 до N и сеть из M дорог с односторонним движением между ними. Каждая дорога задается тройкой (i, j, k), где i - номер города, в котором дорога начинается, j - номер города, в котором дорога заканчивается, а k - ее длина (число k - натуральное). Дороги друг с другом могут пересекаться только в концевых городах.

Все пути между двумя указанными городами A и B можно упорядочить в список по неубыванию их длин (если есть несколько путей одинаковой длины, то выбираем один из них). Необходимо найти один из путей, который может быть вторым в списке.

Вывести его длину L и города, через которые он проходит. Если такого пути не существует, вывести ‘NO SOLUTION’.

Задача №44

Заправки

В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег.

Входные данные

Во входном файле записано сначала число N (1≤N≤100), затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все это целые числа из диапазона от 0 до 100). Затем идет число M - количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами - номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

Выходные данные

В выходной файл выведите одно число - суммарную стоимость маршрута или -1, если добраться невозможно.
Примеры

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

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

4

1 10 2 15

4

1 2 1 3 4 2 4 3

3

Комментарий

Оптимальное решение - из 1-го города поехать в 3-й, а затем в 4-й.

Горючее придется покупать в 1 и 3 городах.


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

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

4

1 10 2 15

0

-1

Комментарий

Добраться невозможно

Циклы

Задача №45

Цикл

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

Задача №46

Длина цикла

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

Задача №47

Цикл с заданной вершины

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

Задача №48

Получение цикла

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

Задача №49

Цикл по заданным вершинам

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

Задача №50

Задача о домино

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

Распределение задач вариантам

Вариант

Задачи

Представление графа. Характеристики графа

Обход графа. DFS и BFS

Поиск кратчайшего пути

Циклы



1

21

31

45



2

21

32

45



3

22

33

46



4

22

34

46



5

23

35

47



6

23

35

47



7

24

36

48



8

24

36

48



9

25

37

49



10

25

37

49



11

26

38

50



12

26

38

50



13

27

39

45



14

27

39

45



15

28

40

46



16

28

40

46



17

29

41

47



18

29

42

47



19

30

43

48



20

30

44

48



1

23

33

49



2

24

34

49



3

25

35

50



4

26

36

50



5

27

37

45

Похожие:

11 класс Часть I задания части I выполняются во время проведения зачётной работы iconПовторение курса по математике 5 8 классов и полугодие 9 класса
Задания первой части выполняются с краткой записью ответа или выбором правильного ответа. Задания второй части предусматривают полное...
11 класс Часть I задания части I выполняются во время проведения зачётной работы iconЗадания для кср№2 по истории психологии. Задания выполняются на отдельных листах а-4
В верхней части листа указываются фамилия, имя студента и номер группы, в которой он учится
11 класс Часть I задания части I выполняются во время проведения зачётной работы iconЛитература, 11 класс. Единый государственный экзамен по литературе вариант №1212 Инструкция по выполнению работы
Экзаменационная работа по литературе состоит из 3 частей. На ее выполнение даётся 4 часа (240 минут). Рекомендуем распределить время...
11 класс Часть I задания части I выполняются во время проведения зачётной работы iconИнструкция по выполнению работы На выполнение экзаменационной работы по информатике отводится 4 часа (240 минут), включая работу за компьютером
Включает тридцать два задания с выбором ответа. К каждому заданию дается четыре ответа, из которых только один правильный. Задания...
11 класс Часть I задания части I выполняются во время проведения зачётной работы iconИнструкция по выполнению работы На выполнение экзаменационной работы по информатике отводится 4 часа (240 минут), включая работу за компьютером
Включает тридцать два задания с выбором ответа. К каждому заданию дается четыре ответа, из которых только один правильный. Задания...
11 класс Часть I задания части I выполняются во время проведения зачётной работы iconСтуденты выполняют одну контрольную работу по аналитической химии (количественный анализ). Выбор номера варианта контрольных заданий в контрольной работе осуществляется по последней цифре в номере зачетной книжки
Например, если номер в зачетной книжке 2178, то вам следует выполнять задания под номерами 8, 18, 28 и т д
11 класс Часть I задания части I выполняются во время проведения зачётной работы iconЗадания для экзаменационной работы Биология 9 класс
При выполнении этой части укажите в бланке ответов цифру, которая обозначает выбранный вами ответ
11 класс Часть I задания части I выполняются во время проведения зачётной работы iconКонтрольная работа №3); кратные и криволинейные интегралы (контрольная работа №4)
Номер варианта совпадает с последней цифрой зачетной книжки студента. По второй части курса высшей математики студент сдает экзамен,...
11 класс Часть I задания части I выполняются во время проведения зачётной работы iconПри выполнении заданий этой части (задания А1 – А17) из четырех вариантов ответов выберите один правильный. А1
Демонстрационная версия экзаменационной работы по русскому языку для учащихся 5 класса, поступающих в гимназический класс
11 класс Часть I задания части I выполняются во время проведения зачётной работы iconИнструкция по выполнению работы
Части 1 и 2 экзамена выполняются в экзаменационной работе. При решении заданий частей 1 и 2 нельзя пользоваться компьютером, справочной...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org