Нахождение кратчайшего пути в графе с ограничениями
материал для подготовки к егэ (гиа) по информатике и икт (9 класс)

Лесбуридис Елена Васильевна
Опубликовано 21.11.2023 - 15:36 - Лесбуридис Елена Васильевна

Подготовка к ОГЭ. Задание №4 .Построение графа, нахождение кратчайшего пути. Анализ графа.

Скачать:

ВложениеРазмер
Microsoft Office document icon kratchayshiy_put_v_grafe_s_ogranicheniyami.doc66 КБ

Предварительный просмотр:

Кратчайший путь в графе с ограничениями

1.Между населенными пунктами построены дороги, протяженность которых приведена в таблице. Отсутствие числа означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами В и F, проходящего через пункт Е. Передвигаться можно только по указанным дорогам.

A

B

C

D

E

F

A

1

3

6

B

1

2

3

10

C

3

2

4

7

D

3

4

5

8

E

10

5

9

F

6

7

8

9

2.Между населенными пунктами построены дороги, протяженность которых приведена в таблице. Отсутствие числа означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами В и F, проходящего через пункт D. Передвигаться можно только по указанным дорогам.

A

B

C

D

E

F

A

3

1

4

B

3

5

6

15

C

1

5

2

2

6

D

4

2

5

E

6

2

F

15

6

5

3.Между населенными пунктами построены дороги, протяженность которых приведена в таблице. Отсутствие числа означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами В и F, не проходящего через пункт D. Передвигаться можно только по указанным дорогам.

A

B

C

D

E

F

A

6

3

1

5

B

6

2

7

12

C

3

2

5

D

1

2

E

7

5

4

F

5

12

2

4

4.Между населенными пунктами построены дороги, протяженность которых приведена в таблице. Отсутствие числа означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами В и F, проходящего через пункт D. Передвигаться можно только по указанным дорогам.

A

B

C

D

E

F

A

4

1

B

4

1

3

C

1

1

1

5

D

3

1

6

E

5

6

10

F

10

5. Между населенными пунктами построены дороги, протяженность которых приведена в таблице. Отсутствие числа означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами В и Е, проходящего через пункт F. Передвигаться можно только по указанным дорогам.

A

B

C

D

E

F

A

4

1

4

B

4

2

3

16

C

1

2

4

6

D

3

4

3

5

E

16

3

9

F

4

6

5

9


По теме: методические разработки, презентации и конспекты

«Профессиональное самоопределение и профессиональная ориентация как поиск и нахождение личностного смысла в выбираемой трудовой деятельности и более успешной социальной адаптации подростков с ограниченными возможностями здоровья»

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

Структурированный конспект как путь, подготовки обучающихся с ограниченными возможностями здоровья, к самообразованию

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

Разработка урока по теме: "Пути в графах"

Данный урок разработан для 9 класса. Цели урока: Обобщить и систематизировать знания о графах ,их видах, свойствах. Методы обучения: наглядный, исследовательский, проблемно-поисковый. Оборуд...

Подготовка к ЕГЭ по информатике. Тест на тему "Поиск путей в графе".

Этот материал по теме "Поиск путей в графе" позволит ученикам, сдающим ЕГЭ по информатике проверить свои знания....

10 класс. Проверочная. Графы. Поиск кол-ва путей

Проверочная. Графы. Поиск кол-ва путей...

Урок по теме "Поиск кратчайших путей в графе"

Урок по учебнику К.Ю. Полякова и Е.А. Еремина (углубленный уровень)...

Задача 13 ЕГЭ по информатике и способы ее решения. Количество путей в графе

В типичной задаче 13 из единого государственного экзамена по информатике даётся ориентированный граф и, как правило, просят найти количество путей из одной вершины графа в другую, удовлетвор...