Таблицы Брадиса

Заметим, что у нас в

Заметим, что у нас в

Элементы математики в задачах - Г. А. Мерзон

Заметим, что у нас в ориентированном графе разрешаются дуги из вершины в себя саму (петли), несколько дуг из одной вершины в другую (кратные дуги), «встречные» дуги (из А в В и из В в А).

То, что раньше называлось графом, мы теперь будем называть неориентированным графом.

ш Выше мы даем два определения ориентированного графа — фор­мальное и неформальное, призванные дополнять друг друга в том

Теория графов 2

смысле, что формальное определение нужно для строгих обоснова­ний решений задач, а неформальное используется в процессе реше­ния задачи и при описании сути дела.

Задача 9. Дайте (формальные!) определения пути и цикла в ориен­тированном графе.

Решение. Путем в ориентированном графе Г называется последова­тельность ребер (упорядоченных пар (а1, Ь1),..., (ап, Ьп)), такая что каждая пара (аі, Ьі) является подмножеством множества ребер Е и, кроме того, вершины аі и Ьі—1 совпадают для любого і = 2,..., п.

Циклом в ориентированном графе Г называется путь (а1, Ь1),... ..., (ап, Ьп), в котором совпадают вершины а1 и Ьп.

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

Задача 10. Какие из следующих графов сильно связны?

 

Ответ. Первый, третий и шестой, что видно из рисунка.

Определение 3. Ориентированный граф называется связным, если он окажется связным неориентированным графом после того, как мы сотрем стрелки с его дуг.

Задача 11. а) Приведите пример связного, но не сильно связного ориентированного графа.