Цикломатическое число графа. Построение остовного дерева связного графа.

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

Подграфы. Операции на графах

Подграфом графа G(V,E) называется граф, все вершины и ребра которого содержатся среди вершин и ребер исходного графа G(V,E).

Определим некоторые операции на графах.

Удаление или добавление ребра.

Удаление вершины. Из множества вершин удаляем выбранную вершину, а из множества ребер все инцидентные ей ребра.

Стягивание ребра. Отождествляем (стягиваем) вершины инцидентные выбранному ребру.

Добавление вершины (разбиение ребра). Выберем некоторое ребро (u,v) из множества ребер и удалим его. В множество вершин добавим новую вершину w, а в множество ребер новые ребра (u,w) и (w,v).

Объединение графов. Объединением графов и называется граф .

Пересечение графов. Пересечением графов и ( ) называется граф .

Связность. Компоненты связности. Маршруты и пути

Маршрут в графе - это последовательность вершин и рёбер , где любые два "соседа" инцидентны. Рёбра и вершины в маршруте могут повторяться. Если начальная и конечная вершины совпадают, то маршрут называется замкнутым. Если все вершины и рёбра маршрута различны, то он называется цепью. Замкнутая цепь - это цикл. Длина маршрута равна числу входящих в него рёбер.

Граф G(V,E) называется связным, если для любых его вершин существует соединяющий их маршрут. Компонентой связности называется максимальный связный подграф графа G(V,E). Число компонент связности графа обозначается k(G).

Ориентированный граф G(V, ) называется сильно связным, если для любых его вершин u и v существуем путь из u в v и путь из v в u.

В этом случае говорят, что вершины u и v достижимы друг из друга.

Если для любых двух вершин u и v графа G(V, ) существует маршрут из u в v или из v в u, то граф называется связным или односторонне связным.

Вершина, удаление которой увеличивает число компонент связности, называется точкой сочленения. Ребро, удаление которого увеличивает число компонент связности, называется перешейком (мостом).

Эйлеровы и гамильтоновы графы

Цикл в графе называется эйлеровым, если он проходит через каждое ребро графа ровно один раз. Граф называется эйлеровым, если в нем есть эйлеров цикл.

Теорема. Граф является эйлеровым тогда и только тогда, когда граф связный и все вершины имеют четную степень.

Теорема. Ориентированный граф является эйлеровым тогда и только тогда, когда он сильно связный и для любой его вершины имеет место равенство: = .

Свое название эйлеровы графы получили в честь Л.Эйлера, который первым рассмотрел такие графы в 1736 году в своей знаменитой работе о кенигсбергских мостах. Этой работой Эйлер, по существу, положил начало новому разделу математики - теории графов.

Задача о кенигсбергских мостах состояла в следующем. На реке Прегель в Кенигсберге было два острова, соединенных между собой и с берегами семью мостами, как показано на рисунке:

Спрашивается, можно ли, начиная с некоторого места суши, обойти все мосты ровно по одному разу и вернуться в начальную точку? Эйлер предложил рассмотреть следующий граф:

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

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

Указанные названия циклов связаны с именем Уильяма Гамильтона, который в 1859 году предложил следующую игру головоломку:

Требуется, переходя по очереди от одной вершины додекаэдра к другой вершине по его ребру, обойти все 20 вершин по одному разу и вернуться в начальную вершину.

Отметим, что придумано еще много других развлекательных и полезных задач, связанных с поиском гамильтоновых циклов. Сформулируем две из них:

1. Кампанию из нескольких человек требуется рассадить за круглым столом таким образом, чтобы по обе стороны от каждого сидели его знакомые.

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

2. (Задача о шахматном коне.) Можно ли, начиная с произвольного поля шахматной доски, обойти конем последовательно все 64 поля по одному разу и вернуться в исходное поле?

Несмотря на внешнее сходство задач об эйлеровых и гамильтоновых циклах, оказалось, что эффективных критериев существования гамильтоновых циклов ( в отличии от эйлеровых) не существует.

Деревья и леса

Связный граф без циклов называется деревом.

Граф без циклов называется лесом.

Теорема. T(V,E) - дерево тогда и только тогда, когда T(V,E) - связный граф и |E|=|V| - 1.

Теорема. В любом дереве имеется не менее двух висячих вершин.

Цикломатическое число графа. Построение остовного дерева связного графа.

Остовным деревом связного графа G(V,E) называется любой его подграф, содержащий все вершины G и являющийся деревом.

На рисунке приведены два графа G и по одному из их остовных деревьев T.

Число ребер, которое необходимо удалить для получения остова, называется цикломатическим числом графа G и обозначается .

Теорема. Цикломатическое числом графа G(V,E) не зависит от последовательности удаления ребер и имеет место формула:

= |E|| - |V|+k(G),

где k(G) - число компонент связности.

Дата добавления: 2020-12-22; просмотров: 90; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!