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

Конечная вершина - вершина орграфа, которой инцидентны только заходящие дуги Пример: пусть D - (V,X) - ориентированный граф,

V = {V„V₂,J''₃}, Х = {х, = {V₂,V_]},x₂ ={V₃,V_i}} , тогда V, конечная вершина.

>^v

Изолированная вершина - вершина, которая не имеет инцидентных ребер.

Пример: пусть D = (V,X) - ориентированный граф,

V = {V,V₂,V₃.V₄}, X = {х, ={V₂,V₃},х₂ ={V_3,V2}}, тогда V„ V₄ -

изолированные вершины.

Степень вершины - число инцидентных ребер, S(X).

Пример: пусть G = (X.R) - граф, изображенный на рисунке.

Тогда S(х₁) = 2. S(х₂) = 1, S(x₃) = 1 - соответственно степени   ^

вершин х₁, х₂, х₃.

Псевдограф - граф с кратными ребрами и петлями. Пример: пусть D = (V,X) - ориентированный граф, X = {х, = {У_гУ₂},х₂={У_],У₂},х₃ ={V_l,V₂},x₄ ={У₂,У₂}}. Тогда D = (У. X) - ориентированный псевдограф.

Пустой граф - граф G = (X,R). в котором R = ф.

Пример: пусть G = (X,R) - граф, изображенный на рисунке. Он

является пустым, т.к. R = ф, X = {х,,х₂,х₃}

о

Х₂

Полный граф - граф G = (X.R), в котором любая пара вершин инцидентна единственному ребру. Обозначается К _р, где р = \Х\, гри этом \R\ = 0,5р(р -1).

Пример: приведенный на рисунке граф является полным, т.к. это шдно из определения и р = 4, при этом выполняется

Мультиграф - граф. в котором имеются кратные (параллельные) ребра. !3%льтиграф - это псевдограф без петель.

'Пример: пусть D~(V,X) - ориентированный граф, V = {V_vV₂},

X - {х, = {F,. V₂},x₂ = {F,,V₂}}. Тогда D = (V,X) - ориентированный мультиграф.

Однородный граф - граф. все вершины которого имеют одну и ту же степень.

Пример: следующие графы, приведенные на рисунке, являются однородными со степенью вершин S(X) = 2. (рис. (а) и (б))

              1

1

б)

Матрица смежности - квадратная матрица А = {a_lt} является матрицей смежности графа G . если при а. =1 в графе G вершины х, и х_; соединены / ребрами, при а, = 0 вершины х, и х, в G несмежны.

Пример: для орграфа D. изображенного на рисунке, приведем матрицу смежности:

v₃

Матрица инцидентности орграфа G = (X,R) - прямоугольная матрица М = {т_п}, т_ч = 1 ,если вершина х, является началом дуги г _t; т_ч - -1, если вершина х₍ является концом дуги г .; т_п = 0. если вершина х,

Пример: для орграфа, приведенного в примере для матрицы смежности, составим матрицу инцидентности:

Два графа G - (X,U) и L- (X',U') являются изоморфными, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.

Пример-: следующие графы, приведенные на рисунке, изоморфны:

Маршрут длины Н - чередующаяся последовательность х_],u,х₂,...,и_н,х_н+] вершин х, и ребер и_j, обладающих тем свойством, что пара соседних элементов инцидентна.                                                                                                                      

Пример: последовательность V_lx_tV₂x,V₁x_jV, - маршрут длины соединяющий вершины F, и V* в графе, приведенном на рисунке.                            

Замкнутый маршрут - маршрут, у которого начальная вершина совпадает с конечной.

Простая цепь - цепь, в которой все вершины различны.

Пример: для ориентированного графа D = (V,X), приведенного выше в примере с цепью,

i]x₁l\x₄J^/₃ и Vх₂У^х₄¥~ - простые цепи из V, в V, длины 2.

Цикл - цепь, у которой начальная и конечная вершина

совпадают.

Пример: пусть G = (X,R) - граф, показанный на

Xi

рисунке, тогда х,г,х₂г₂х_?г₃х_] - цикл.

Простой цикл - простая цепь, у которой концевые вершины совпадают.

Х4 Гз Хз клеров цикл - это цепь, содержащая все ребра графа в точности один раз. у которой

Х4

1ЛЬТОНОВ цикл - это простая цепь.

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

/Пример: приведенный на рисунке граф имеет Гамильтонов * цикл: (10,6,7,5.4,3,2,8.9,1,10).

Путь (ориентированная цепь) - цепь орграфа G . в которой ориентация дуг (ребер)

совпадает.                                                                                                                          пример: для ориентированного графа, приведенного на                         рисунке, имеем путь из V, в V₃ длины 3: V,x_lV_lx₂V₂x₄V₃.                                             

П ростой путь - путь, не содержащий повторяющихся вершин. Пример: для ориентированного графа, приведенного на рисунке, имеем простой путь из V, в V₄: V_jx_lV₂x₂V₃x₄V₄.

Контур - путь, у которого начальная и конечная вершины совпадают.

Пример: для ориентированного графа, приведенного на                                          

рисунке, имеем контур: V_lx_lF_lx₂F₂x₃F₂x₄F₃x₅V₃x₆V_]                                          

-ДО хч V₂

Простой контур - контур, не содержащий повторяющихся вершин.

Пример: для ориентированного графа, изображенного на рисунке, имеем простой контур: F^x₂V₃x₃F₄x₄F₅x₅F₂                               

Подграф графа G = (X,R) - граф G’ = {X',R’), для которого X' с! и две вершины в G'

Ч “Y

Пример: пус гь G = (X, R) - исходный граф, показанный на рисунке (а), тогда G' = (X'.R'),- некоторый подграф графа G = (X,R) (рисунок (б))

(б)

МП

Су граф графа G = (X.R) - граф G' - (X.R') содержит то же множество вершин, что и

граф G и R' с R .

Пример: пусть G-(X,R) - некоторый                                          --'Т--.

исходный граф. показанный на рисунке (а),                                      Г~ ~~У «<Г

тогда G' = (X. R') - некоторый суграф графа                                                             "

G = (X.R)( б).

О)                   (б)

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

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

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

Компонента связности графа - максимальный подграф графа G . в котором все вершины попарно достижимы.

Пример: у графа, показанного на рисунке, три компоненты связности.                                                                         ,Д                           F

/ \ /

Сильная компонента орграфа G максимальный подграф орграфа G , в                                 у.                                -у_

котором любая пара вершин сильно                                                 V-,                  ц у.-, связана.                                                                 Vi> \"''"S'

Пример: у орграфа, изображенного на                                 j \ / V]*³

пятнур ТПИ ЬТ\ЛТГТГ>ТТР«Х1.Т Г-МТТТ^НПЙ                                            т-

vf

Вершина V_] ориентированного графа называется достижимой из вершины V₂. если существует путь с началом в \\ и концом в V₂.

Пример: в приведенном на рисунке орграфе вершина F, является достижимой из вершины F₃.

ViX

t                                V’

--------------

V₅                 V₄

Минимальная длина простой цепи с началом в \\ и концом в F, называется расстоянием между этими вершинами.

Пример: в графе, изображенном на рисунке, расстояние между вершинами V_i и V_] равно трем.

"Vi

Смешанный граф - это граф, содержащий как дуги, так и ненаправленные ребра. Пример: граф. показанный на рисунке, является смешанным.

XI

Vi^

Х2

- Хз

N,V₄

Вершина V инцидентна дуге х тогда и только тогда, когда V является