Системы и сети - pismo.netnado.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Системы и сети - страница №1/5



МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ
Московский государственный институт электроники и математики

(Технический университет)

Кафедра «Вычислительные

системы и сети»


Методические указания к самостоятельным и семинарским занятиям по теории графов



Москва 2006




Составитель: доц., канд. тех. наук Л.Е.Захарова

УДК 519.1


Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах по теории графов в курсе дискретной математики студентами I (дневного) и II (вечернего) курсов специальности 22.0101.


Теория графов: Метод. указания к самостоятельным и семинарским занятиям по теории графов/ Моск. Гос. ин-т электроники и математики; Сост. Л.Е. Захарова. М., 2006. 30 с.

Ил. 3. Библиогр.: 5 назв.




Графы: основные понятия


Граф – это совокупность не пустого множества точек V, называемых вершинами, и множества X отрезков прямых, соединяющих вершины и называемых рёбрами. N- это граф с n вершинами и без рёбер, или, другими словами, это n изолированных вершин. Ребро графа называется петлёй, если оба конца его являются одной и той же вершиной. Рёбра называются кратными, если концы у них совпадают. Петли тоже могут быть кратными.

В псевдографе могут быть и кратные рёбра и петли. В мультиграфе могут быть только кратные рёбра. В графе, если это не оговаривается особо, нет ни петель, ни кратных рёбер.

Вершины графа называются смежными, если их соединяет ребро. Ребра графа смежны, если имеют общую вершину. Степенью вершины является число рёбер, для которых эта вершина является концом. Если степень вершины единица, то вершина называется висячей. Каждая петля увеличивает степень вершины на два.

Для графов приняты следующие обозначения: n – это число вершин в графе (n0), а m – это число рёбер в нём. В каждом псевдографе (мультиграфе, графе) сумма степеней всех вершин в нём равна 2m, так как вклад каждого ребра в эту сумму равен двойке.

Изоморфные графы отличаются друг от друга только нумерацией вершин. Изоморфный граф – это тот же самый граф, только по-другому нарисованный. В изоморфных графах числа вершин и рёбер и набор степеней вершин совпадают, но не наоборот. Например, существует два разных графа с n=5, m=6 и набором степеней вершин: 2 2 2 3 3, в одном вершины степени три смежны (имеют общее ребро), а в другом нет.

Маршрут в псевдографе – это последовательность, в которой чередуются вершины и рёбра, их соединяющие. Если нет кратных рёбер, то маршрут можно составить из одних вершин. Число рёбер в маршруте называется его длиной. Незамкнутый маршрут, в котором все рёбра различны, называется цепью. Цепь, в которой все вершины различны, называется простой цепью. Ребро – это простая цепь длиной единица.

Замкнутый маршрут, в котором все рёбра различны, называется циклом. Цикл, в котором все вершины различны, называется простым циклом. Петля – это простой цикл длины единица. Кратные рёбра образуют простой цикл длины два.

Если степени всех вершин графа больше единицы, то в графе существует хотя бы один цикл. Берём любую вершину, из неё выходят как минимум два ребра, выходим из этой вершины по любому из рёбер и попадаем в следующую вершину. У этой новой вершины степень как минимум два, выходим из неё по ребру, не совпадающему с тем, по которому в неё попали. Опять попадаем в новую вершину и так же выходим из неё по новому ребру. Поскольку число вершин в графе конечно, то рано или поздно попадём в вершину, в которой уже были, не обязательно это будет вершина, из которой мы начали маршрут, и получим цикл.

Подграфом графа называется граф, все вершины и рёбра которого содержатся среди вершин и рёбер графа. Подграф называется собственным, если он отличен от самого графа.

Псевдограф называется связным, если для каждой пары его вершин существует маршрут, их соединяющий. Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа графа. Число компонент связности у графа обозначается переменной p. У связного графа p=1, у N(графа с n изолированными вершинами) p=n.

Лес – это граф без циклов. Дерево – это связный граф без циклов. Лес, таким образом, состоит из p деревьев. Полный граф содержит все возможные рёбра между n вершинами и обозначается K. Число рёбер у полного графа равно m=n(n-1)/2. В дереве m=n-1, а в лесе m=n-p, так как каждое дерево леса отнимает единицу от числа вершин n.

В двудольном графе вершины разделяются на две доли (n=n1+n2), а рёбра существуют только между вершинами из разных долей. Двудольный граф может быть полным и не полным. В полном двудольном графе, которой обозначается K, существуют все возможные ребра между вершинами из разных долей. Число рёбер в полном двудольном графе равно n1n2.

Граф называется регулярным (или однородным) если все вершины в нём имеют одну и ту же степень. Если из графа удалить вершину вместе с ребрами, для которых она является концом, то получим подграф графа. Вершина графа называется разделяющей, если её удаление увеличивает количество компонент связности.
Задания по графам


Н.

Доказать, что если в графе без петель и кратных ребер min степеней вершин не меньше

(n-1)/2, то граф связен. Доказывать от обратного: посчитать max числа вершин и их max степень в двух компонентах связности.



Ю.

Доказать, что если в псевдографе существует ровно 2 вершины нечётной степени, то существует цепь, соединяющая их.



У.

Дополнение графа – это граф с те ми же вершинами, но с рёбрами, которых нет в самом графе. Имеем граф без петель и кратных рёбер и его дополнение. Доказать, а) что хотя бы один из этих графов связен; б) если в графе более 4-х вершин, то хотя бы в одном из графа и его дополнения есть цикл. (Дерево – граф без циклов, у него m=n-1).



Р.

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

Э.

Пусть у графа без петель и кратных рёбер n вершин и p компонент связности. Доказать, что m (число рёбер) (n-p)m(n-p)(n-p+1)/2. (Для нижней оценки рассмотреть лес из p деревьев, а для верхней – (p-1) изолированную вершину и полный граф с (n-p+1) вершинами.) Вывести отсюда, что если у n-вершинного графа (n>1) m>(n-2)(n-1)/2, то он связен (p=1)

Т.

Доказать, что если в мультиграфе степень каждой вершины больше единицы, то в нём есть цикл. А в псевдографе?

И.

Выяснить, какие наборы степеней вершин могут быть у 6-вершинных связных графов без петель и кратных рёбер, имеющих 7 рёбер и содержащих вершину степени два и вершину степени три. Для каждого допустимого набора степеней вершин построить пример соответствующего графа.

Ь.

Сколько существует попарно неизоморфных графов без петель и кратных рёбер, в которых: а) n=6 m=11; б) n=7 m=18; в) n=8 m=24.

П.

Доказать, что если из связного мультиграфа удалить произвольное ребро, содержащееся в некотором цикле, то новый мультиграф будет также связен. А псевдограф и граф?



G.

Известно, что 6-вершинные графы G и H не имеют петель и кратных рёбер, двусвязны (граф k-связен, если при удалении любых (k-1) вершин получается связный граф), содержат по 10 рёбер и степень одной вершины в каждом из них равна d1 (1d15), а степени всех остальных вершин – d2 (d2

М.

Доказать, что в мультиграфе всякий замкнутый маршрут нечётной длины l (l>2) содержит простой цикл. Справедливо ли аналогичное утверждения для маршрутов чётной длины?

Д.

Изобразить все попарно неизоморфные 6-вершинные графы без петель и кратных рёбер, состоящие а) из 4 компонент; б) из 3 компонент; в) из одной компоненты и имеющие 7 рёбер и ровно 2 висячие вершины.

Ц.

Граф (без петель и кратных рёбер) называется самодополнительным, если он изоморфен своему дополнению. Дополнение графа – это граф с те ми же вершинами, но с рёбрами, которых нет в самом графе. Показать, что число вершин в самодополнительном графе либо кратно четырем (равно 4z, z>0) либо равно 4z+1 (z>-1).

Ш.

Сколько существует попарно неизоморфных графов без петель и кратных рёбер, в которых: а) n=6 m=7 и p=2 (p – число компонент связности); б) n=8 и сумма степеней всех вершин >52?






Е.

Сколько существует попарно неизоморфных 6-вершинных графов без петель и кратных рёбер с набором степеней вершин: 2, 2, 3, 3, 3, 5?

Л.

Доказать, что n>2 n-вершинный связный граф без петель и кратных рёбер, содержащий (n-1) вершин с неравными друг другу степенями.

Б.

nj – число вершин степени j в графе. Построить все попарно неизоморфные графы без петель и кратных рёбер, у которых: а) n2=1 n3=n4=2 (n=5); б) n2=3 n3=2 n4=1 (n=6).

Х.

Вершина называется разделяющей, если после её удаления в графе увеличивается число компонент связности. Доказать, что если вершина является разделяющей в графе, то она не является разделяющей в дополнении графа. Дополнение графа – это граф с те ми же вершинами, но с рёбрами, которых нет в самом графе.

О.

Индукцией по n доказать, что связный псевдограф с n вершинами содержит не менее

(n-1) рёбер (n>0).



Ы.

Граф называется самодополнительным, если он изоморфен своему дополнению. Дополнение графа – это граф с те ми же вершинами, но с рёбрами, которых нет в самом графе. Расстояние между вершинами – это длина кратчайшей цепи, соединяющей их. Диаметр графа – это max расстояний в нём. Доказать, что диаметр самодополнительного графа не меньше 2 и не больше 3.



Ж.

Сколько существует попарно неизоморфных, не имеющих петель и кратных рёбер, кубических (все вершины степени 3) графов с 6 вершинами? c 8?

К.

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

С.

Доказать, что всякий связный псевдограф, имеющий не менее двух вершин, содержит вершину, не являющуюся разделяющей. Висячие вершины в графе – не разделяющие. Если их в графе нет, то удалять из циклов рёбра до тех пор, пока они не появятся.

Ч.

Граф (без петель и кратных рёбер) называется самодополнительным, если он изоморфен своему дополнению. Дополнение графа – это граф с те ми же вершинами, но с рёбрами, которых нет в самом графе. Доказать, что среди 4-вершинных графов самодополнительным является один, а среди 5-вершинных – два.

Г.

Построить все попарно неизоморфные 5-вершинные графы, не имеющие петель, кратных рёбер и изолированных вершин.

Ъ.

Граф (без петель и кратных рёбер) называется самодополнительным, если он изоморфен своему дополнению. Дополнение графа – это граф с те ми же вершинами, но с рёбрами, которых нет в самом графе. Доказать, что самодополнительный граф связен.





Я.

В двудольном графе вершины разделяются на две доли (n=n1+n2), а рёбра существуют только между вершинами из разных долей. Доказать, что если в двудольном графе без кратных рёбер m>((n-1)/2) и n>1, то граф связен. Доказывать от обратного, посчитать для p=2 число рёбер в двух полных двудольных графах.

З.

Существует ли 6-вершинный граф без петель и кратных рёбер с набором степеней вершин: 2, 2, 2, 4, 5, 5?

В.

Изобразить все попарно неизоморфные 4-вершинные графы без петель и кратных рёбер.



S.

Известно, что графы G и H не имеют петель и кратных рёбер, двусвязны (граф k-связен, если при удалении любых (k-1) вершин получается связный граф), содержат 6 вершин и 8 рёбер каждый. У графа G имеется 2 вершины степени 2, а у H – 4 степени 3. Изоморфны ли G и H?

Ф.

Дополнение графа – это граф с те ми же вершинами, но с рёбрами, которых нет в самом графе. Расстояние между вершинами – это длина кратчайшей цепи, соединяющей их. Диаметр графа – это max расстояний в нём. Доказать, что если граф несвязен, или его диаметр не меньше 3, то диаметр дополнения графа не больше 3.





следующая страница >>