Дискретная математика: графы и автоматы. Альпин Ю.А - 18 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

18 Глава 1. Неориентированные графы
Рис. 8
нет мостов, то есть, каждое ребро принадлежит циклу. Эйлеров граф
— это, конечно, лист. Нетрудно показать, что и гамильтонов граф —
лист. Но некоторые листы не эйлеровы и не гамильтоновы.
Мы покажем, что всякий связный граф есть, образно говоря, де-
рево с листами (а то, что мы назвали деревом, это, скорее, дерево
зимой, без листьев).
Назовём вершины u, v графа циклически-рёберно связанными, ес-
ли u = v, или существует (u, v)-маршрут, не содержащий мостов.
Циклически-рёберная связанность есть, очевидно, отношение эквива-
лентности. Классы этой эквивалентности порождают подграфы, яв-
ляющиеся листами. Будем называть эти подграфы, как и сами клас-
сы, листами графа. Докажите следующее несложное
Предложение 1. Каждый мост графа соединяет вершины из
разных листов, причём, если два листа соединены, то лишь одним
мостом.
В параграфе 1 введено понятие подграфа, и, в частности, подгра-
фа, порождённого подмножеством вершин. Введём понятие, в неко-
тором смысле двойственное понятию подграфа.
Пусть задано разбиение множества вершин графа G. Определим
факторграф графа G по данному разбиению следующим образом.
Вершины факторграфа — это классы разбиения, два класса считают-
ся смежными вершинами, если какие-нибудь вершины из этих клас-
сов смежны в G.
Упражнение 1. Что представляет собой факторграф по разби-
ению на компоненты?
Некоторые свойства графа наследуются факторграфом. Напри-
мер, нетрудно проверить, что справедливо
Предложение 2. Факторграф связного графа по любому разби-
ению — связный граф.
Основной результат этого параграфа:
18                                      Глава 1. Неориентированные графы




                               Рис. 8

нет мостов, то есть, каждое ребро принадлежит циклу. Эйлеров граф
— это, конечно, лист. Нетрудно показать, что и гамильтонов граф —
лист. Но некоторые листы не эйлеровы и не гамильтоновы.
    Мы покажем, что всякий связный граф есть, образно говоря, де-
рево с листами (а то, что мы назвали деревом, это, скорее, дерево
зимой, без листьев).
    Назовём вершины u, v графа циклически-рёберно связанными, ес-
ли u = v, или существует (u, v)-маршрут, не содержащий мостов.
Циклически-рёберная связанность есть, очевидно, отношение эквива-
лентности. Классы этой эквивалентности порождают подграфы, яв-
ляющиеся листами. Будем называть эти подграфы, как и сами клас-
сы, листами графа. Докажите следующее несложное
    Предложение 1. Каждый мост графа соединяет вершины из
разных листов, причём, если два листа соединены, то лишь одним
мостом.
    В параграфе 1 введено понятие подграфа, и, в частности, подгра-
фа, порождённого подмножеством вершин. Введём понятие, в неко-
тором смысле двойственное понятию подграфа.
    Пусть задано разбиение множества вершин графа G. Определим
факторграф графа G по данному разбиению следующим образом.
Вершины факторграфа — это классы разбиения, два класса считают-
ся смежными вершинами, если какие-нибудь вершины из этих клас-
сов смежны в G.
   Упражнение 1. Что представляет собой факторграф по разби-
ению на компоненты?
   Некоторые свойства графа наследуются факторграфом. Напри-
мер, нетрудно проверить, что справедливо
   Предложение 2. Факторграф связного графа по любому разби-
ению — связный граф.
     Основной результат этого параграфа:

Страницы