Графы. Задания с решением. Информатика. 8 класс
материал по информатике и икт (8 класс)

8 класс, кр № 1, 1 вариант, № 1(часть В)

Задания Д11 № 271

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение.

Начнем считать количество путей с конца маршрута — с города К. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В К можно приехать из Е, В, Г или Ж, поэтому N = NК = NЕ + NВ + NГ + NЖ (*).

Аналогично:

NЕ = NБ = 1;

NВ = NА + NБ = 1 + 1 = 2;

NГ = NВ + NА + NД = 2 + 1 + 1 = 4;

NЖ = NГ + NД = 4 + 1 = 5;

NБ = NА = 1;

NД = NА = 1.

Подставим в формулу (*): N = 1 + 2 + 4 + 5 = 12.

Источник: ГИА по информатике 31.05.2013. Основная волна. Вариант 1314.

8 класс, кр № 1, 2 вариант, № 1(часть В)

Задания Д11 № 849

На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?

Решение.

Начнем считать количество путей с конца маршрута — с города D. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В D можно приехать из C или E, поэтому N = ND = NC + NE(*).

Аналогично:

NC = NB + NE = 3 + 2 = 5;

NB = NA + NE = 1 + 2 = 3;

NE = NF + NG = 1 + 1 = 2;

NG = NF = 1;

NF = NА = 1.

Подставим в формулу (*): N = 5 + 2 = 7.

Ответ: 7.

Задачи «Графы»

Задания Д11 № 869

№1 На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?

Решение.

Начнем считать количество путей с конца маршрута — с города D. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В D можно приехать из C или E, поэтому N = ND = NC + NE(*).

Аналогично:

NE = NB + NC + NF + NG = 1 + 1 + 1 + 1 = 4;

NC = NB = 1;

NG = NF = 1;

NB = NA = 1;

NF = NА = 1.

Подставим в формулу (*): N = 1 + 4 = 5.

Ответ: 5.

Задания Д11 № 890

№ 2 На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город G?

Решение.

Начнем считать количество путей с конца маршрута — с города G. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В G можно приехать из D, E или F, поэтому N = NG = ND + NE + NF(*).

Аналогично:

NF = NC + NE = 1 + 2 = 3;

NE = NB + NC = 1 + 1 = 2;

ND = NB = 1;

NB = NA = 1;

NC = NА = 1.

Подставим в формулу (*): N = 1 + 2 + 3 = 6.

Ответ: 6.

Задания Д11 № 1062

№ 3 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение.

Начнем считать количество путей с конца маршрута — с города К. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В К можно приехать из Д, В, Г или Е, поэтому N = NК = NД + NВ + NГ + NЕ(*).

Аналогично:

NД = NБ + NВ = 1 + 3 = 4;

NВ = NБ + NА + NГ = 1 + 1 + 1 = 3;

NГ = NА = 1;

NЕ = NГ= 1;

NБ = NА = 1;

NА = 1.

Подставим в формулу (*): N = 4 + 3 + 1 + 1 = 9.

Ответ: 9.

Задания Д11 № 592

№ 4 На рисунке изображена схема соединений, связывающих пункты А, В, С, D, Е, F. По каждому соединению можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт F?

Решение.

Начнем считать количество путей с конца маршрута — с города F. Пусть NX — количество различных путей из города F в город X, N — общее число путей.

В F можно приехать из B или E, поэтому N = NF = NB + NE (*).

Аналогично:

NB = NA + NC = 1 + 2 = 3;

NE = NC + ND = 2 + 1 = 3;

NC = NA + ND = 1 + 1 = 2;

ND = NA = 1;

Подставим в формулу (*): N = 3 + 3 = 6.

Задания Д11 № 331

№ 5 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение.

Начнем считать количество путей с конца маршрута — с города К. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В К можно приехать из Е или Д, поэтому N = NК = NЕ + NД(*).

Аналогично:

NД = NБ + NВ = 1 + 3 = 4;

NЕ = NВ + NГ = 3 + 1 = 4;

NБ = NА = 1;

NВ = NБ + NА + NГ = 1 + 1 + 1 = 3;

NГ = NА = 1.

Подставим в формулу (*): N = 4 + 4 = 8.

Задания Д11 № 291

№ 6 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение.

Начнем считать количество путей с конца маршрута — с города К. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В К можно приехать из Е, В, Г или Ж, поэтому N = NК = NЕ + NВ + NГ + NЖ (*).

Аналогично:

NЕ = NБ + NВ = 1 + 2 = 3;

NВ = NА + NБ = 1 + 1 = 2;

NГ = NВ + NА = 2 + 1 = 3;

NЖ = NГ + NД = 3 + 1 = 4;

NБ = NА = 1;

NД = NА = 1.

Подставим в формулу (*): N = 3 + 2 + 3 + 4 = 12.

Задания Д11 № 11

№ 7 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение.

Начнем считать количество путей с конца маршрута — с города К. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В К можно приехать из Е, В, Г или Ж, поэтому N = NК = NЕ + NВ + N Г + NЖ (*).

Аналогично:

NЕ = NБ + NВ = 1 + 1 = 2;

NЖ = NД = 1;

NВ = NА = 1;

NГ = NВ + NА + NД = 1 + 1 + 1 = 3;

NД = NА = 1;

NБ = NА = 1.

Подставим найденные значения в формулу (*): N = 2 + 1 + 3 + 1 = 7.

Задания Д11 № 31

№ 8 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение.

Начнем считать количество путей с конца маршрута — с города К. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В К можно приехать из Е, В, Г или Ж, поэтому N = NК = NЕ + NВ + N Г + NЖ (*).

Аналогично:

NЕ = NБ + NВ = 1 + 2 = 3;

NЖ = NД = 1;

NВ = NА + NБ = 1 + 1 = 2;

NГ = NА + NД = 1 + 1 = 2;

NД = NА = 1;

NБ = NА = 1.

Подставим в формулу (*): N = 3 + 2 + 2 + 1 = 8.

Задания Д11 № 51

№ 9 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение.

Начнем считать количество путей с конца маршрута — с города К. Пусть NX — количество различных путей из города А в город X, N — общее число путей.

В К можно приехать из Е, В, Г или Ж, поэтому N = NК = NЕ + NВ + N Г + NЖ (*).

Аналогично:

NЕ = NБ = 1;

NВ = NБ + NА = 1 + 1 = 2;

NГ = NА + NВ = 1 + 2 = 3;

NЖ = NГ + NД = 3 + 1 = 4;

NД = NА = 1;

NБ = NА = 1.

Подставим в формулу (*): N = 1 + 2 + 3 + 4 = 10.

№ 10 В таблице приведена стоимость перевозок между пятью железнодорожными станциями, обозначенными буквами A, B, C, D и E. Укажите схему, соответствующую таблице.

1) 

2) 

3) 

4) 

Из таблицы видно, что только из пункта D есть всего одна дорога, которая идёт в пункт B, а из дорога из пункта A в пункт E равняется 1. Следовательно, подходит только вариант 2.

Правильный ответ указан под номером 2.

Задание 4 № 544

№ 11 Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого длинного участка кратчайшего пути от Ивана-Царевича до Марьи-Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:

1) 1

2) 2

3) 3

4) 6

Решение.

Найдём все варианты маршрутов из И в М и выберем самый короткий.

Из пункта И можно попасть в пункты А, Б, Г, М.

Из пункта Г можно попасть в пункты И, М.

Из пункта В можно попасть в пункты А, Б.

Из пункта Б можно попасть в пункты В, И, М.

И—А—В—Б—М: длина маршрута 7 км.

И—Б—М: длина маршрута 4 км.

И—Г—М: длина маршрута 7 км.

И—М: длина маршрута 8 км.

Самый короткий путь: И—Б—М. Длина маршрута 4 км. Самый длинный участок этого пути равен 3 км.

Задание 4 № 1014

№ 12 Машинист электропоезда должен добраться из пункта А в пункт C за 6 часов. Из представленных таблиц выберите такую, согласно которой машинист сможет доехать из пункта А в пункт C за это время. В ячейках таблицы указано время (в часах), которое занимает дорога из одного пункта в другой. Передвигаться можно только по дорогам, указанным в таблицах.

Решение.

Найдём кратчайшие маршруты из A в С для каждой таблицы.

Исходя из первой таблицы, кратчайший маршрут из A в С: A—B—C, его можно преодолеть за 8 часов. Для второй таблицы кратчайшая дорога: A—B—C, она занимает 6 часов. Третий маршрут: A—C, его можно преодолеть за 9 часов. Четвёртый маршрут: A—B—C, его можно преодолеть за 7 часов.

Правильный ответ указан под номером 2.

Задание 3 № 7662

№ 13 Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E. Передвигаться можно только по указанным дорогам.

Решение.

Заметим, что в Е можно попасть только из D и F, следовательно, в маршруте также обязательно должен присутствовать пункт D. Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут A—B—D—E—F, его длина равна 15 км. Теперь, начиная с начала маршрута, будем изменять путь, пользуясь следующим соображением: если расстояние, например, A—B—D больше расстояния A—D, то заменяем участок маршрута A—B—D на A—D. Попробовав произвести все такие замены, получим, что маршрут A—B—D—E—F — самый короткий из тех, что удовлетворяют условию задачи.

Любое другое изменение пути, через которые проходит маршрут, приводит к увеличению его длины.

Ответ: 15.

№ 14 Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Рассмотрим все возможные маршруты. Кратчайшим окажется A-B-E-F-G длиной 17

Задание 3 № 3487

№ 15 Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

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

Решение.

Найдём все варианты маршрутов из A в B и выберем самый короткий.

В пункт B можно попасть из пунктов С и F.

В пункт F можно попасть из пунктов А и D.

В пункт С можно попасть из пунктов D и Е.

В пункты D и Е можно попасть из пункта А.

A-D-C-B. Длина маршрута 1 + 2 + 4 = 7.

A-E-C-B. Длина маршрута 4 + 1 + 4 = 9.

A-F-B. Длина маршрута 3 + 5 = 8.

A-D-F-B. Длина маршрута 1 + 2 + 5 = 8.

Видно, что кратчайший путь равен 7.