Файл: Точек, являющихся образом множества объектов, и множества линий.docx

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Калининградский государственный технический университет»


О.М. ТОПОРКОВА
ОСНОВЫ ТЕОРИИ ГРАФОВ

Калининград

Издательство ФГБОУ ВО «КГТУ»

2020

Оглавление

1. Граф и его характеристики

1. Основные понятия

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

Используются разные способы обозначения графа, например:

1. 
   G=,
   

где Х={x_i} - множество точек, элементы которого называют вершинами графа (носитель графа),

R= {r_j=(x_i,x_k)|x_i,x_kX} – множество линий, соединяющих точки (сигнатура графа): линии представляют неупорядоченную или упорядоченную пару элементов множества Х: в первом случае линия называется ребром графа, во втором - дугой;

2. 
   G=,
   

где Х={x_i} – вершины графа,

H={h(x_i)={x_j}|x_i,x_jX} – множество образов (окружение) вершины x_i.

Некоторые понятия графа:

1. 
   порядок графа n - число вершин;
   
2. 
   размер графа m- число линий. Если различные линии соответствуют одним и тем же парам вершин графа, они называются кратными;
   
3. 
   петля - линия, соединяющая вершину саму с собой;
   
4. 
   концевые точки (концы) линии – вершины, между которыми проходит линия; в этом случае линия инцидентнасвоим концевымвершинам, которые, в свою очередь, инцидентнылинии;
   
5. 
   степень (валентность) вершины δ - число линий, инцидентных вершине;
   
6. 
   если линия является дугой r_j=(x_i,x_k), то:
   

---

• 
  x_i - начальная вершина, или исток, дуги (дуга выходит из вершины x_i), в этом случае говорят о положительной инцидентности вершины, а число дуг, исходящих из нее, называют полустепенью вершины δ⁺;
  
• 
  x_k конечная вершина, или сток, дуги (дуга входит в вершину x_k), в этом случае говорят об отрицательной инцидентности вершины, а число дуг, заходящих в нее, также называют полустепенью вершины и обозначают δ^-;
  

7. 
   смежные вершины - концевые точки одной линии;
   
8. 
   смежные линии - линии, имеющие общую вершину;
   
9. 
   маршрут (x_i, x_j) - последовательность смежных линий, соединяющих вершины x_i и x_j , количество линий - длина маршрута l. Длину минимального маршрута называют расстоянием. Маршрут может быть:
   

• 
  простым, если при его обходе каждая промежуточная вершина встречается не более 1 раза;
  
• 
  цепью, если при его обходе каждая линия встречается не более одного раза;
  
• 
  открытым, если его концевые вершины различны;
  
• 
  замкнутым, если его концевые вершины совпадают;
  
• 
  циклом – когда он является замкнутой цепью;
  

10. 
    переход ν(x_i, x_j) - последовательность смежных вершин цепи, соединяющей несмежные вершины графа x_iи x_j,.
    

Виды графов:

1. 
   смешанный - среди линий есть и дуги, и ребра;
   
2. 
   простой (обыкновенный) - не имеет ни петель, ни кратных линий;
   
3. 
   псевдограф - имеет кратные линии и петли;
   
4. 
   ориентированный граф (орграф) – его линии являются либо дугами, либо петлями;
   
5. 
   неориентированный граф (неограф) – его линии являются только ребрами либо петлями;
   
6. 
   связный - любые две вершины можно соединить маршрутом, т.е. каждая вершина графа достижима;
   
7. 
   эйлеров- все вершины его достижимы и степень каждой вершины есть четное число;
   
8. 
   полный – все вершины смежны между собой;
   
9. 
   пустой - любые две его вершины несмежные (это граф без линий);
   
10. 
    подграф - порождён из некоторого графа подмножеством его вершин вместе с инцидентными им линиями;
    
11. 
    частичный граф - порождён из некоторого графа подмножеством его линий вместе с инцидентными им вершинами;
    
12. 
    суграф – порожден из некоторого графа подмножеством его линий, но использует все его вершины;
    
13. 
    остов, или дерево, - суграф без циклов, петель и кратных ребер;
    
14. 
    взвешенный граф - его линии или вершины имеют дополнительные (весовые) характеристики
    

---

---

1.2. Описание графа

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

Списки

Пусть есть неограф на рисунке:



Список отображений для него:

.

Список отношений: R={r₁(v₁,v₃), r₂(v₂,v₃), r₃(v₂,v₃), r₄(v₂,v₄), r₅(v₄,v₄)}.

Пусть есть орграф:



Список отображений для него:

,

Список отношений: R={r₁(x₁,x₂), r₂(x₂,x₃), r₃(x₃,x₄), r₄(x₄,x₂), r₅(x₅,x₁), r₆(x₅,x₂), r₇(x₅,x₃)}.

Матрица инцидентности

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

Для неографа отношение принадлежности вершины графа его ребру определяют по формуле:



В каждой строке матрицы количество единиц равно двум, так как это есть концевые вершины ребра, а в каждом столбце - степени вершины - δ. Если граф содержит петлю относительно вершины x_i, то в строке соответствующего отношения будет «1» только для вершины x_i.

В таблице приведена матрица инцидентности для графа предыдущего примера:

---

	v1	v2	v3	v4
r1	1	0	1	0
r2	0	1	1	0
r3	0	1	1	0
r4	0	1	0	1
r5	0	0	0	1

Для орграфа отношение инцидентности определяют по формуле:



В каждой строке должны быть один символ «+1» и один «–1», а в каждом столбце сумма «+1» равна полустепени исхода вершины x_i, а сумма «–1» – полустепени захода вершины x_i.

Таблица описывает матрицу инцидентности орграфа:

	x1	x2	x3	x4	x5
r1	+1	-1	0	0	0
r2	0	+1	-1	0	0
r3	0	-1	0	0	+1
r4	0	0	+1	0	-1
r5	0	0	+1	-1	0
r6	0	-1	0	+1	0
r7	-1	0	0	+1	0

---