2_понятия и определения. Лекция Основные понятия графов, элементы графов

• Название: Лекция Основные понятия графов, элементы графов
• Дата: 08.01.2019
• Размер: 112.91 Kb.
• Имя файла: 2_понятия и определения.docx
• Тип: Лекция; #62813

Лекция 2 . Основные понятия графов, элементы графов

и их определения

ГрафомG=(V,X)называется пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек.

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

Если задан граф G= (V,X),тоV–конечное непустое множество его вершин, X– множествоего ребер.

Примеры графов:




г
G₄

Пусть дан граф G= (V,X), где  V ={A,B,C,D…} - конечное непустое множество его вершин, X(A,B) –его ребра.

Порядок графа - это число вершин в графе.

Размер графа - это число его рёбер.

Ребро называется  инцидентнымпо отношению к тем вершинам, которые оно соединяет.

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

Два ребра называются смежными,если они имеют общую вершину.

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


A
Задача 1: дан граф G


Х₄

Х₂

Х₃

Х₁

B




D




C

1. 
   Множество вершин - V ={A,B,C,D} 
   
2. 
   Множество инцидентных ребер – X₁(A,D), X₂(A,B), X₃ (B,C)
   
3. 
   Смежные вершины – A и D, A и B, B и C
   
4. 
   Смежные ребра X₁ и X_2, X₂ и X₃
   
5. 
   Ребро-петля X₄(С,С)
   
6. 
   Порядок графа – 4
   
7. 
   Размер графа - 4
   

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

Количество одинаковых пар вида X(A,B) называется кратностью ребра (A,B).

Степенью вершины называется число, равное числу ребер, инцидентных этой вершине. Степень вершины обозначается символом обозначается deg(A) (от англ.degree - степень).

Если вершине инцидентна петля, то степень ее равна двум: оба конца такого ребра приходят в эту вершину.

Вершина называется изолированной, если степень ее равна нулю.

Граф называется нуль-графом, если он состоит из изолированных вершин.

Вершина графа называется висячей, если степень ее 1.

Задача 2: дан граф G

5. 
   Множество вершин - V ={A,B,C,D,E,F} 
   
6. 
   Множество инцидентных ребер – X₁(A,B) X₂(A,B)_, X₃(C,E), X₄(C,D), X₅(C,C), X₆(D,B) X₇(D,F)
   
7. 
   Смежные вершины – A и C , A и B, B и D, C и D, D и F.
   
8. 
   Смежные ребра X₁ и X_3, X₁ и X₆, X₂ и X_3, X₂ и X_6, X₄ и X₆, X₄ и X_3, X₇ и X_4, X₇ и X₆
   

E

Х₅

E

A



C




Х₂₁

Х₁

Х₄

Х₃



Х₇

D

Х₆

В

5. 
   Ребро-петля X₅(С,С)
   
6. 
   Кратные ребра X₁(A,B) X₂(A,B).
   
7. 
   Кратность ребра AB равна 2.
   
8. 
   Изолированная вершина Е.
   
9. 
   Висячая вершина F.
   
10. 
    Степени вершин: Deg(A)=3, Deg(B)=3, Deg(C)=4, Deg(D)=3, Deg(E)=0, Deg(F)=1
    
11. 
    Размер графа – 7
    
12. 
    Порядок графа - 6
    

Теорема1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа.

где n- число вершин; m - число рёбер графа.

Пример. Пусть граф содержит 5 ребер, тогда степень этого графа равна r=5·2=10

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

Теорема 2.Число нечетных вершин любого графа – четно.

Следствие.Невозможно начертить граф с нечетным числом нечетных вершин.

Задача 3. В графе G(V,X) определить:

• висячие вершины;

• число ребер;

• определить степени всех вершин с указанием их четности или нечетности;

• доказать, что Теорема 1 верна на данном примере.

• Проверить теорему 2 на данном примере

C

D

F

H

G



E

B
A

V={A,B,C,D,E,F,G,H}

• 
  Висячие: A, B, E, G, H
  
• 
  число ребер m=7
  
• 
  Нечетные вершины:
  

Deg(A)=1, Deg(B)=1, Deg(E)=1, Deg(G)=1, Deg(F)=3, Deg(H)=1

Четные вершины:

Deg(C)=4, Deg(D)=2

∑ Deg(V_i)=1*5+3+4+2=14, а число ребер m= 7. По теореме1 ∑ Deg(V_i)=2* m, т.е. 2*7=14. Теорема верна.

• 
  Число нечетных вершин 6 – четное число.
  

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

Пример



Задача 4. Изобразить полный граф G(V,X), где: V=3;4;6. Определить количество ребер каждого графа и степени вершин.

Таким образом, полный граф определяется только своими вершинами. Пусть число вершин полного графа равно n. Тогда степень любой вершины Deg(V)=n-1. Это понятно из примера, т.к. каждая вершина соединяется с остальными.

Теорема 3Число ребер в полном графе порядка равно .

Доказательство

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

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

Пример. Дан граф G_1. Изобразить его дополнение до полного графа G₂


G₂

G₁

G₁


Следствие. Дополнением полного графа будет являться нуль-граф и наоборот.