Деревья. Эйлеровы графы. Полный граф, двудольный граф.

Графом называют систему некоторых объектов, вместе с некоторыми парами этих объектов изображающую отношение между ними. Графы служат для изображения схем, химических формул и т.д. Полным графом называется граф без кратных ребер, в котором любые две вершины соединены ребром. Двудольным графом называется граф, вершины которого разбиты на два не пересекающихся класса и , а ребра связывают вершины разных классов. n – мерным единичным кубом называется граф, вершинами которого служат все наборы длины n из нулей и единиц, а ребра соединяют вершины, которые различаются ровно в одном компоненте. Граф называется связным, если он не имеет изолированных вершин. Ребро e произвольного графа называется циклическим, если оно принадлежит хотя бы одному элементарному циклу в графе и ациклическим в противоположном случае. Справедливы следующие утверждения: 1) если из связного графа удалить циклическое ребро, то он останется связным; 2) если из связного графа удалить ациклическое ребро, то он станет не связным. Связный граф без циклов называется деревом. Любой граф без цикла называется лесом. Все ребра дерева ациклические. Дерево обладает следующими свойствами: 1) при удалении любого ребра перестает быть деревом; 2) число ребер на единицу меньше числа вершин; 3) любые две вершины связаны единственной элементарной цепью; 4) после добавления ребра появляется цикл. В любом дереве существуют концевые вершины. Если в связном графе последовательно удалять циклические ребра до тех пор пока это возможно, то получается дерево называемое остовом этого графа. Все ребра остова называются хордами.

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

Т. к. каждая вершина простого цикла имеет в нём чётную степень, то можно доказать Т. Эйлера.

Теорема Эйлера. Для того чтобы конечный связный граф был эйлеровым, необходимо и достаточно, чтобы он был четным.

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

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

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

Можно также доказать, что:

1) в любом графе число вершин нечетной степени четно;

2) Элеровых графов почти нет, т.е.

Из теоремы Эйлера можно вывести интересное следствие. В произвольном связном графе G раздвоим каждое ребро е = (v1, v2), т.е. заменим его парой кратных ребер e^', e" с теми же вершинами. Степень каждой вершины удвоится и станет четной. В полученном четном графе G, существует эйлеров цикл (а если ребра e^', e" ориентировать в противоположных направлениях, то каждая вершина будет равновесной и существует эйлеров контур). Если рассмотреть его как обход графа gi, снова склеить пары e^', e" в одно ребро, то в первоначальном графе G эта траектория будет (уже не простым) циклом, проходящим через каждое свое ребро ровно два раза (причем в противоположных направлениях). Итак, в каждом связном графе существует цикл, содержащий ровно 2 раза каждое ребро графа, что можно трактовать как соответствующий обход лабиринта с возвращением в начало обхода.

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

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться:

Популярное:

1. Заочная форма обучения (полный срок)
2. Поощрительные баллы - 5 балл за полный объем СРС (за качественное выполнение и всесторонний анализ определенного вопроса, за выполнение в установленные сроки), за посещения всех занятий.