Дискретная математика ПМ / Пособие по Дискретной математике

Упражнения

Определить, что представляют собой последовательности вершин для графа, представленного на рисунке.

Для графа, приведенного на рисунке построить маршрут, проходящий через вершину а: 1) три раза; 2) два раза; 3) один раз. Какими свойствами обладает этот маршрут.

Рис.1 Рис.2 Рис.3

Для графа, приведенного на рисунке найти построить: 1) маршрут общего вида, 2) цепь, 3) простую цепь, 4) циклический маршрут общего вида, 5) цикл, 6) простой цикл.

Рис.1 Рис.2

Для графа, приведенного на рисунке найти: 1) расстояния между вершинами; 2) диаметр; 3) все диаметральные цепи; 4) расстояние от вершины до наиболее удаленной вершины; 5) центры; 6) все радиальные цепи.

Рис.1 Рис.2

Для графа, приведенного на рисунке указать разделяющее множество ребер при удалении которого из графа, он распадется на компоненты связности, с множествами вершин идля рис. 1), 2), 3); с множествами вершинидля рис. 4), 5), 6).

Является ли это множество разрезом? Если является, то указать множество, которое являться разрезом не будет. Если не является, то указать разрез.

Рис. 1 Рис.2

Рис. 3 Рис.4

Рис. 5 Рис.6

Для графа, приведенного на рисунке определить, будет ли он Эйлеровым, Гамильтоновым. Если да, то построить эйлеров, гамильтонов цикл.

Рис.1 Рис.2 Рис.3

Опредилить, какой из графов, представленных на рисунке, является эйлеровым, полуэйлеровым (или, что то же самое, эйлеровым циклом, эйлеровой цепью).

Убедится в том, что граф, приведенный на рисунке, эйлеров и найти эйлеров цикл, пользуясь алгоритмом Флери.

Определить, какой из графов, представленных на рисунке, является гамильтоновым, полугамильтоновым (или, что то же самое, гамильтоновым циклом, гамильтоновой цепью).

Рис.1 Рис.2 Рис.3

Какими свойствами обладает отношение связанности вершин н-графа на рисунке? Чему равно число связных компонент графа G?

Для четырех графов на рисунке определить расстояния между вершинами. Какие вершины являются центрами графов? Чему равны радиусы и диаметры графов?