Теория графов и комбинаторика (СОДЕРЖАНИЕ)

 Лекция 3

            Путь в графе и связные компоненты графа. Цепи, простые цепи, циклы, простые циклы. Операции удаления вершины, удаления ребра, подразбиения ребра. Дерево и его особенности.          

            Пусть  - граф и, как обычно, .

Путь в графе - это символ вида

,

где .  Таким образом, среди вершин  и ребер  могут быть повторы. По символу пути на графической интерпретации графа можно воспроизвести «движение» от вершине к вершине, выбирая каждый раз очередное ребро в соответствии с указанием в пути.

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

вершины a₃ и a₅ связаны (путем ), а вершины a₄ и a₁ нет.

            Граф, в котором связанны любые две вершины, называется связным. Таким образом, выше приведен пример графа несвязного. Связной компонентой  графа называется такой его подграф, который является сам по себе графом связным и при этом совпадающим с любым другим содержащим его связным подграфом. Таким образом, связный граф обладает единственной связной компонентой - это он сам. А вот пример графа с тремя связными компонентами (имена вершин не имеют значения):

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

            Вот схематическое изображение простого цикла:

А вот схематическое изображение цикла, не являющегося простым:

            Удаление вершины.  Пусть  - граф и . Удалить вершину a из графа G - это значит построить новый граф , в котором  и  получается из B удалением всех ребер, инцидентных вершине a. Вот иллюстрация удаления вершины a из

графа:

До                                                    После       

        удаления вершины a                                удаления вершины a

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

До                                                  После

          удаления ребра  b                                 удаления ребра  b

            Подразбиение ребра. Пусть  - граф и . Выполнить подразбие-ние ребра b - это значит построить новый граф , в котором  (т.е. z -некая новая вершина) и . С графической точки зрения эта опе-рация означает «внесение в ребро новой вершины». Вот графическая иллюстрация:                                                                                            

                 До                                                             После                        

внесения вершины z                                             внесения вершины z  

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

А вот пример графа, не являющегося деревом:

            Если граф  является деревом и число его вершин равно p, то о числе его ребер можно сказать совершенно определенно: количество ребер равно . В каждом дереве имеется еще одна особенность: любые две вершины в дереве связаны и притом единственной простой цепью. Оба эти обстоятельства имеют несложные доказательства.

Лекция 4

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

            Пусть  - граф. Эйлеровым циклом в графе называется такой цикл, который содержит все ребра и все вершины этого графа. Напомним, что, по определению, в циклах не повторяются ребра. Таким образом, при наличии эйлерова цикла в графе этот граф можно

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

            Вот пример эйлерова графа:

А вот пример графа, не являющегося эйлеровым:

            Существует теорема (теорема Эйлера), полностью описывающая эйлеровы графы:

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

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

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

         Пусть  - связный граф и  - все его вершины нечетной степени на-помним, что в каждом графе число вершин нечетной степени четно). Тогда, если , то минимальное число цепей графа, содержащих в совокупности все его ребра, равно ; если же , то указанное минимальное число равно 1.

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

            построим новый граф , в котором  (т.е. добавляется одна новая вершина) и  (т.е. добавляется еще  ребер);

            заметим, что полученный граф  является связным и все его локальные степени уже четны; поэтому в нем существует некий эйлеров цикл ;

            осуществим обход по циклу , начав и закончив этот обход в вершине ; те  цепей, о которых идет речь в обсуждаемом утверждении, будут выделяться в процессе этого обхода так: обход начинается в вершине ; следовательно, следующей за  будет некая вершина из G; она и будет началом первой цепи; после некоторого пути надо будет вновь вернуться в ; первая цепь закончится в той вершине из G, из которой осуществится возвращение в ; затем по той…