Помогите!!! сколько существует различных путей для разных графов:-из начальной точки А в...

0 голосов
63 просмотров

Помогите!!! сколько существует различных путей для разных графов:-из начальной точки А в конечную точку И,-из начальной точки А в конечную точку К, НЕ проходящих через Е(задание на прикрепленном фото не нужно,нужен только рисунки графов)


image

Информатика (36 баллов) | 63 просмотров
Дан 1 ответ
0 голосов

Как-то так... )))

Первая картинка (из начальной точки А в конечную точку И)

Вторая картинка (из начальной точки А в конечную точку К, НЕ проходящих через Е)


Каждой вершине, начиная с начальной (A), поставим индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь).


Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).


Индекс В равен 3 (предков у В три – вершина A, вершина Б и вершина Г; 1 + 1 + 1 = 3).


И т.д.


Исключаем из подсчёта вершину Е для второго задания.


image
image
(1.7k баллов)
0

спасибо огромноее!!!