Теория графов. Классификация графов. Основные определения. Две компоненты связности

ТЕОРИЯ ГРАФОВ

Введение

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

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

Возникновение теории графов принято датировать 1936 годом, когда появилась книга Денеша Кёнига «Теория конечных и бесконечных графов». Однако отдельные задачи по теории графов возникали и решались много раньше, например, Леонард Эйлер (1707 – 1782) в 1736 году сформулировал задачу о Кенигсбергских мостах:

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

             С                                  

А                            D                                     

B

Теорема: Необходимым и достаточным условием существования таких обходов в графе является его связность и четность степеней вершин.

Области применения теории графов: Химия. Химическая информатика. Электротехника.  Электроника. Молекулярная биология (ДНК). Психология. Социология. Программирование. Информатика и многие многие другие.

Классификация графов

Признак классификации	Графы
Ориентация (может быть или нет)	–  орграф –  неорграф –  смешанный граф
Взвешенность: структурная или функциональная	–  взвешенный функцией –  невзвешенный граф –  частично взвешенный

Виды весов:                                                                     Тип взвешенности: 

–арифметические числа                                                             – реберная       

–функции                                                                                      – вершинная

–логические                                                                                  – смешанный вариант

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

                  X – множество вершин графа, |X| = n,

E – множество ребер графа, |E| = m. E: XX.

           Совокупность множества Х вершин и множества Е связей между ними называется графом и обозначается G(X,E).

Пример: Все графы на 4 вершинах. G(X, E), где |X|=4.

Если у какой-либо вершины в графе нет ребер, то это граф с изолированной  вершиной.

(Обратите внимание на обозначения  C₄, P4, K4 – цикл, цепь, полный граф с четырьмя вершинами)!!!

1                 2                               1                2             

3                4    

G₁(4,0)                                         G₂                                                               G₃                                                               G₄                              

G₅  цепь P₄                                               G₆                                                                        G₇                                   G₈ (4,4) цикл C₄

G₉                                     G₁₀                                                      G₁₁

полный граф K₄

                                      x₁

                                                                   e₄                 G(4,6)

e₂

                                 x₄

      x₂                                                   e₆

e₅                       e₃                             x₂

           Если связь имеет направление, то она называется дугой, в противном случае – ребром.

                                                                                                                                 ребро e

дуга e

           Граф, у которого все связи являются ребрами, называется неографом.

               e₄

e₆        e₁

e₅   

e₃                                 e₂

           Граф с дугами называется ориентированным графом (орграфом).

e₃

 

e₂              e₁

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

                                                                                    e₁

                        а                                  в                      e₂

                                                                                                                     мультиграф G(6,20)

                                                                                                e₃

e₄

а, в – 2 вершины графа;

e₁,e₂,e₃,e₄ – кратные ребра, соединяющие вершины а и в.

           Ребро, оба конца которого связаны с одной и той же вершиной, называется петлей.

                                                   Петля

 

Вершина

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

дуга e₉                                            дуга e₈                             петля e₁

 

                                                                   ребро e₅                                ребро e₆

 

                                                                                                                                                      дуга e₃

              петля e₆                                                                                                               дуга e₂                            

         петля e₇

                                                                                                                                       дуга e₄                                                                                                                                                                   кратные

                       ребро e₃                                     

                ребро e₄                                                                                  ребро e₂

                    петля e₅                                                                                  ребро e₂                                              кратные    

           Две вершины называются смежными, если они соединяются некоторым ребром (дугой) графа, и два различные ребра (дуги) смежны, если они имеют общую вершину.

a            e₁            b

 

e₃                           e₂

c

           Вершина х_i инцидентна дуге (ребру) е_ij, если она является началом или концом дуги (ребра).

1                   e_{12                            2}

 

х₁ инцидентна дуге е₁₂, так как х₁ начало е₁₂.

х₂ инцидентна дуге е₁₂, так как х₂ конец е₁₂.

           Дуга (ребро) е_ij инцидентна вершине x_i, если она выходит из этой вершины или входит в нее.

                     x₁

e₁₂ инцидентна x_i.

e₁₂                                                                                                                                                                              

           Число ребер (дуг), инцидентных некоторой вершине х_i, называют степенью вершины (обозначение deg(x_i)).

                                                                  x₅

e₁₁

e₁₀

e₉

e₇                    x₁            e₅

e₈                                                                           x₄

e₂    e₁

e₆

e₄

x₂

Например степень вершины: x₁:6;

(ребра е₇, е₈, е₂, е₁, е₅, дуга е₇), степень вершины X₅:3;

(ребро e₁₁, дуга e₇ и т.д.)

           Для неорграфа сумма степеней вершин равна удвоенному числу его ребер: .

x_{1                   e1}    x₂                                              Ст. свободы x₁: 2

                                                               Ст. свободы x₂: 3

e₄                e₂                             Ст. свободы x₃: 2    

e₅                                         x₃                   Ст. свободы x₄: 3

e₃

x₄    

Неорграф G(4,5)

Сумма степеней вершин: S=2+3+2+3=10. Количество ребер n=5 (e₁, e₂, e₃, e₄, e₅). S=2n=2∙5=10.

           Для орграфа вводится понятие полустепени исхода (deg⁺) и полустепени захода (deg^-) вершины, что соответствует числу выходящих и входящих дуг соответственно.

полустепень исхода вершины е: 1

(одна выходящая дуга 10)

полустепень захода вершины е: 3

(3 входящие дуги :4,7,9)

полустепень исхода вершины а: 2

(2 выходящие дуги: 1, 2)

полустепень захода вершины а: 1

(одна заходящая дуга 10)

                                                                 a

1                                             2                   Орграф G(7,10)

g                                                                              b

10

9

8                                          e

5                3

7

4

f                         6             d                                   c

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

а                            b                                            b                                  c

                                                                                                                    

                                                      a                                                                              d

f                                    e

d                             c

Связный граф G₁(4,5)                                     Несвязнй граф G₂(6,4)

Несвязный граф G₂(6,4) состоит из двух компонент.

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

e

                                                 e₆                d

b    e₄           e₅

e₃         c

e₂        e₈             e₇

e₁

a

G(5, 8)

Маршрут из точки “a” в “b” (а – начальная вершина, b – конечная вершина): последовательность дуги e₇, вершины d, дуги e₆, вершины e, дуги e₅, вершины c, дуги e₃.

Маршрут называется цепью, если все его ребра (дуги) различны и простой цепью, если все его вершины различны.

           Замкнутый маршрут называется циклом (контуром), если все его вершины и ребра (дуги) различны и его длина l>2. Цикл (контур) называется простым, если все его вершины различны.

b

 

e₄                                  e₁

a                          e₅    c

e₃                       e₂

d

Маршрут b–e₁–c–e₂–d–e₅–b является замкнутым и его вершины (b,c,d) и ребра (e₁, e₂, e₅) различны, а длина маршрута равна l=3, следовательно данный маршрут можно назвать простым циклом.

           Вершина графа, после удаления которой увеличивается число компонент