Путь и контур. Длина пути и контура. Графы связные, полные.

Определение. Последовательность дуг, при которой конец одной дуги является началом другой, называется путём.

 Если начальная и конечная точки пути совпадают, образуется контур.

Длиной пути (или контура) называют число дуг, которые его образуют.

 Петля – контур единичной длины.

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

 То есть будем применять термин “длина пути” не только к орграфам.

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

Определение. Граф называется связным, если любая пара вершин соединена маршрутом.

Несвязный граф состоит из нескольких отдельно связных графов.

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

Если полный граф Г имеет N вершин, то он обозначится через К_N. Легко видеть, что К_N имеет  N*(N–1) / 2       рёбер.

Определение. Простым графом называют граф, который не имеет петель или кратных рёбер.

Определение. Полный граф – это простой граф. Он однозначно задаётся числом своих вершин.

Определение. Полный граф с N вершинами является однородным степени (N–1), так как из каждой его вершины выходит (N–1) рёбер, ведущих к каждой из остальных (N–1) вершин.  

Определение. Полный ориентированный граф называется турниром.

Этот термин получил своё название от соревнований по круговой системе, графическое представление которых имеет структуру полного ориентированного графа.

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

В представлении турнира по круговой системе ориентированным графом, командам соответствуют вершины. Дуга (p₁, p₂) присутствует в графе, если соответствующая p₁ команда победила команду, представленную вершиной p₂.

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

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

Рис. 1.2

Пример турнира приведён на рис. 1.2. Участвующие в турнире команды можно ранжировать в соответствии с количеством очков. Количество очков команды соответствует числу побеждённых ею противников.

Введём определение последовательности очков турнира.

Последовательностью очков турнира на N вершинах называется последовательность (S1 , S2 , … , SN ), в которой каждое Sn – число дуг, исходящих из n-й вершины турнира.

1.5. Плоские и планарные графы

Определение. Планарный граф — граф , который может быть изображён на плоскости без пересечения рёбер.

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

Граф, который не является планарным, называется не планарным.

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

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

Можно также сказать, что граф, изоморфный плоскому графу, называется планарным. Например, все три изоморфных графа Г₁, Г₂, Г₃ на следующем рисунке планарные, но только Г₂, и Г₃ – плоские.

Планарный граф на рис.3а можно изобразить в виде изоморфных плоских графов (рис.1. 3б и рис. 1.3в):

Рис. 1.3а

Рис. 3б

Рис. 3в