28: "Информационно-коммуникационные технологии", Моделирование и формализация. Количество путей в графе.

Решать задачи по теме

Основные понятия и определения

Справочная информация:

  • Графы — графические информационные модели для отображения систем. Объекты системы изображаются вершинами, а связи между ними — линиями (рёбрами).
  • У взвешенного графа вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер.
  • Цепь — это путь по вершинам и рёбрам графа, в который любое ребро графа входит только один раз (например, С-D-E).
  • Цикл — цепь, начальная и конечная вершины которой совпадают (например, С-D-E-C).
  • Сеть — граф с циклом.
  • Дерево — граф иерархической системы (между любыми двумя вершинами дерева существует единственный путь). Вершина верхнего уровня называется корнем.

Примеры и задачи

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

Схема дорог для задачи 9-1

Решение:

Будем последовательно искать количество путей из вершины А во все остальные вершины графа, записывая возле каждой вершины в скобках количество путей из А до этой вершины. Для начальной вершины А количество путей всегда равно 1. Каждая входящая в вершину стрелка добавляет столько путей, сколько указано в начале этой стрелки (у вершины, из которой она выходит). Начинать нужно с вершин, у которых все входящие стрелки уже имеют числа.

  • Вершины Б, Г, Ж, И — по одной входящей стрелке, в начале которой написано 1 (сюда можно попасть одним способом, один путь).
  • Вершина В — две входящих стрелки с числами 1, в эту вершину \(1+1=2\) пути.
  • Вершина Д — две входящих стрелки с числами 1 и 2, в эту вершину \(1+2=3\) пути.
  • Вершина Е — две входящих стрелки с числами 2 и 1, в эту вершину \(2+1=3\) пути.
  • Вершина З — две входящих стрелки с числами 3 и 3, в эту вершину \(3+3=6\) путей.
  • Вершина К — четыре входящих стрелки с числами 6, 3, 1 и 1, всего \(6+3+1+1=11\) путей.
Решение задачи 9-1

Ответ: 11 путей.

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

Схема дорог для задачи 9-2

Решение:

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

  • Вершина Б — одна входящая стрелка, в начале которой написано 1 (в эту вершину 1 путь).
  • Вершина В — две входящих стрелки с числами 1, в эту вершину \(1+1=2\) пути.
  • Вершины Г, Д — по одной входящей стрелке, в начале которых написано 2 (в эти вершины 2 пути).
  • Вершина Е — две входящих стрелки с числами 2 и 2, в эту вершину \(2+2=4\) пути.
  • Вершина Ж — две входящих стрелки с числами 2 и 2, в эту вершину \(2+2=4\) пути.
  • Вершина З — три входящих стрелки с числами 2, 4 и 4, всего \(2+4+4=10\) путей.
Схема дорог для задачи 9-2

Ответ: 10 путей.

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

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

Схема дорог для задачи 9-3Решение задачи 9-3

Решение:

  • Вершины Б, Д — одна входящая стрелка, в начале которой написано 1 (в эту вершину 1 путь).
  • Вершина В — две входящих стрелки с числами 1, в эту вершину \(1+1=2\) пути.
  • Вершина Г — две входящих стрелки с числами 1 и 2, в эту вершину \(1+2=3\) пути.
  • Вершина Е — две входящих стрелки с числами 1 и 2, в эту вершину \(1+2=3\) пути.
  • Вершина Ж — две входящих стрелки с числами 3 и 1, в эту вершину \(3+1=4\) пути.
  • Вершина З — две входящих стрелки с числами 3 и 4, всего \(3+4=7\) путей.
  • Вершина Л — одна входящая стрелка, в начале которой написано 7 (всего 7 путей).
Решение задачи 9-3

Ответ: 7 путей.

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

Схема дорог для задачи 9-4

Решение:

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

  • Вершины Б, Д — одна входящая стрелка, в начале которой написано 1 (в эту вершину 1 путь).
  • Вершина В — две входящих стрелки с числами 1, в эту вершину \(1+1=2\) пути.
  • Вершина Г — три входящих стрелки с числами 2, 1 и 1, в эту вершину \(2+1+1=4\) пути.
  • Вершина Ж — одна входящая стрелка, в начале которой написано 4 (в эту вершину 4 пути).
  • Вершина З — две входящих стрелки с числами 4 и 4, всего \(4+4=8\) путей.
  • Вершина К — одна входящая стрелка, в начале которой написано 4 (в эту вершину 4 пути).
  • Вершина Л — три входящих стрелки с числами 8, 4 и 4, всего \(8+4+4=16\) путей.
Решение задачи 9-4

Ответ: 16 путей.

Заключение

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

Автор: С. В. Чайченков, МБОУ Грушевская СОШ

Наверх

Решать задачи по теме