Цикломатическое число графа. Построение остовного дерева связного графа.
Теория графов
Подграфы. Операции на графах
Подграфом графа 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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!