Алгебра
Английский
Биология
География
Геометрия
История
Русский
Обществознание
Физика
Химия
Информатика
Литература
МатематикаВопрос:
4. На рисунке изображён граф. a) Сколько кратчайших путей есть в этом графе из вершины А в вершину В? б) Сколько кратчайших путей из вершины А в вершину В проходит через вершину С?
Ответ:
a) Количество кратчайших путей из вершины А в вершину В: 2 (A-F-B и A-C-B).
б) Количество кратчайших путей из вершины А в вершину В, проходящих через вершину С: 1 (A-C-B).
Похожие
- 2. На рисунке изображён граф. a) Чему равна наименьшая из степеней его вершин? б) Какие вершины этого графа имеют наименьшую степень?
- 3. Нарисуйте какой-нибудь граф, у которого: a) пять вершин, степени которых равны 2, 2, 2, 3, 3; б) пять вершин, степени которых равны 2, 2, 3, 3, 4.
- 4. На рисунке изображён граф. a) Сколько кратчайших путей есть в этом графе из вершины А в вершину В? б) Сколько кратчайших путей из вершины А в вершину В проходит через вершину С?
- 5. В некотором графе 5 вершин, степени которых равны: 4; 2; 1; 3; 4.
- 6. В таблице указаны рейсы, которые выполняет авиакомпания «Аэросервис». a) Постройте граф, в котором вершины означают аэропорты, входящие в маршрутную сеть авиакомпании. Если два аэропорта соединены рейсом, то в графе соответствующие вершины должны быть соединены ребром.
