Элементы теории графов и их технические приложения - 7 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

7
Следует иметь в виду, что смежность есть отношение между однородными
элементами графа, тогда как инцидентность является отношением между
разнородными элементами.
Множество всех вершин графа G, смежных с некоторой вершиной v,
называется окружением вершины v и обозначается N
G
(v) или N(v).
Обычно граф представляется диаграммой, состоящей из точек и линий,
соединяющих некоторые из этих точек. При этом точки соответствуют вершинам
графа, а соединяющие пары точек линии – ребрам. Часто эту диаграмму и называют
графом.
В качестве примера рассмотрим (5,6) граф (рис. 4). Для него множество
вершин VG ={1,2,3,4,5} и множество ребер EG={{1,2}, {1,5}, {2,3}, {2,4}, {2,5},
{4,5}}. Вершины 1 и 2 смежны, а
1 и 3 не смежны. Вершина 1 и ребро {1,2}
инциденты. Окружение вершины 2 есть N(2)={1,3,4,5}.
Рис. 4
Граф G называется полным, если любые две его вершины смежны
(соединены ребром). Полный граф порядка n обозначается символом К
n
, число
ребер в таком графе равно С
2
n
=
2
)1n(n
−
. На рис. 5 изображены полные графы К
1
, К
2
,
К
3
, К
4
, К
5
.
Рис. 5
Граф называется пустым, если в нем нет ребер. Пустой граф порядка n
обозначается О
n
. Для задания полного графа достаточно знать число его вершин.
Набор подмножеств множества S называется покрытием множества S, если
объединение этих подмножеств совпадает с S. Покрытие называется разбиением,
если никакие два из входящих в него подмножеств не пересекаются. Граф
называется двудольным, если существует такое разбиение множества его вершин на
две части, что концы каждого
ребра принадлежат разным частям. Если при этом
любые две вершины, входящие в разные доли, смежны, то граф называется полным
двудольным. Полный двудольный граф, доли которого состоят из p и q вершин,
обозначается символом К
p,q
. При p=1 получаем звезду К
1,q
. На рис. 6 изображены
звезда К
1,5
и полный двудольный граф К
3,3
.

Страницы