Анализ графа. Рассмотрите описание графа G и ответьте на вопросы:
- Сколько вершин и сколько рёбер в данном графе?
- Является ли граф ориентированным или неориентированным?
- Является ли граф взвешенным или не взвешенным?
- Является ли данный граф связным?
- Выпишите все рёбра, инцидентные вершине B.
- Есть ли в графе петли?
- Есть ли в графе циклы? Если да, то приведите примеры.
- Является ли граф сетью?
Читаем рёбра с рисунка (со стрелками): B→C, C→D, D→B, C→E, D→E, B→E, E→A, A→B.
- Вершины: A, B, C, D, E —
вершин. Рёбер . - У рёбер есть стрелки, значит граф ориентированный.
- Числа (веса) на рёбрах не написаны, значит граф невзвешенный.
- От любой вершины можно дойти до любой другой, даже не учитывая направление стрелок, значит граф связный.
- Вершине B инцидентны рёбра: B→C, D→B, B→E, A→B.
- Ребра, которое начинается и заканчивается в одной вершине, нет, значит петель нет.
- Циклы есть: B→C→D→B и B→E→A→B.
- Сеть — это взвешенный граф, а этот граф невзвешенный, значит сетью он не является.
Сеть — взвешенный граф (на рёбрах стоят числа). Цикл — путь, который начинается и заканчивается в одной вершине.
вершин, рёбер - ориентированный
- невзвешенный
- связный
- B→C, D→B, B→E, A→B
- петель нет
- да: B→C→D→B, B→E→A→B
- не является сетью
На рисунке — схема дорог, связывающих населённые пункты A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из населённого пункта A в населённый пункт G?
Дороги: A→B, A→C, A→D, A→E, B→E, C→E, D→C, D→E, D→G, E→F, E→G, F→G.
Пусть
Число путей в вершину равно сумме чисел путей из её соседей, в которые ведут стрелки. Считают от конечной вершины к начальной.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Л, не проходящих через пункт Е?
Дороги: А→Б, А→В, А→Г, Б→Г, В→Г, Г→Д, Г→Е, Г→И, Д→Ж, Д→Е, Д→Л, Ж→Л, Е→Л, Е→И, Е→К, И→К, К→Л.
Пункт Е исключаем, то есть дороги в Е и из Е не используем. Остаются: А→Б, А→В, А→Г, Б→Г, В→Г, Г→Д, Г→И, Д→Ж, Д→Л, Ж→Л, И→К, К→Л.
Пусть
Чтобы путь не проходил через пункт, убираем этот пункт из графа и считаем пути в оставшемся графе.
