2 Графы - лекции
.pdfЛЕКЦИЯ 11. НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ НА СЕТИ: АЛГОРИТМ ДЕЙКСТРЫ
В различных приложениях возникает следующая задача: найти кратчайший путь между некоторыми вершинами a и b сети.
Одним из лучших способов решения подобных задач является алго-
ритм Дейкстры9 (алгоритм расстановки меток). В процессе его работы вершинам сети присваивают метки d (xi ) , являющиеся оценками длины кратчайшего пути от вершины a к вершине xi .
Если вершина xi на некотором шаге получила метку d (xi ) , то в сети существует путь из a в xi длиной d (xi ) . Метка может находиться в одном из двух состояний: она временная или постоянная. Постоянность метки означает, что кратчайшее расстояние от a до xi найдено.
Алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути от a до b , на втором – сам кратчайший путь.
Этап 1. Нахождение длины кратчайшего пути Шаг 1. Присвоение вершинам начальных меток
Полагаем d (a) 0* и считаем эту метку постоянной (постоянные метки отметим звѐздочкой вверху нуля). Для остальных вершин полагаем
d (xi ) |
и считаем эти метки временными. То, что a – текущая вершина, |
|||
|
~ |
a . |
|
|
обозначим так: x |
|
|
||
|
Шаг 2. Изменение меток |
|
||
|
У каждой вершины xi |
с временной меткой, непосредственно следу- |
||
ющей за вершиной |
~ |
|
|
|
x , меняем еѐ метку в соответствии с правилом: |
||||
|
|
dнов. (xi ) |
~ |
~ |
|
|
min{ dстар. (xi ), d (x ) |
щ(x, xi )} . |
Шаг 3. Превращение метки из временной в постоянную
9 Едсгер Вибе Дейкстра (1930, Роттердам, Нидерланды – 2002, Нуенен, Нидерланды) – нидерландский математик, идеи которого повлияли на развитие компьютерной индустрии. В 1956 году принял участие в разработке ЭВМ X1, для оптимизации разводки плат которой был придуман алгоритм поиска кратчайшего пути на графе, известный как «алгоритм Дейкстры». В своих книгах Дейкстра отстаивал необходимость математического подхода к программированию, который предполагает предварительное точное математическое описание задачи и способа еѐ решения, доказательство правильности выбранного алгоритма и последующую реализацию алгоритма в виде максимально простой, структурированной программы, корректность которой должна быть доказана. По мнению Дейкстры, господствующий в компьютерной индустрии подход к программированию как к процессу достижения результата методом проб и ошибок («написать код – протестировать – найти ошибки – исправить – протестировать – …») порочен, поскольку стимулирует программистов не думать над задачей, а писать код, при этом совершенно не гарантирует корректность программ, которая не может быть доказана тестированием в принципе.
87
Из всех вершин с временными метками выбираем вершину x*j с наименьшим значением метки
|
|
d (x* ) |
min{ d (x |
j |
) | d (x |
j |
) временная}. |
||
|
|
j |
|
|
|
|
|
||
Превращаем эту метку в постоянную и полагаем |
~ |
* |
|||||||
x |
x j . |
||||||||
Шаг 4. Проверка на завершение первого этапа |
|
|
|||||||
~ |
b , то |
~ |
– длина кратчайшего пути от a до b . Иначе – |
||||||
Если x |
d (x ) |
происходит возвращение ко второму шагу.
Этап 2. Построение кратчайшего пути Шаг 5. Последовательный поиск дуг кратчайшего пути
~
Среди вершин, непосредственно предшествующих вершине x с постоянными метками, находим вершину xi , удовлетворяющую соотношению
|
~ |
~ |
|
|
d (x ) |
d (xi ) щ(xi , x ) . |
|
|
~ |
|
~ |
Включаем дугу (xi , x ) в искомый путь и полагаем |
x xi . |
||
Шаг 6. Проверка на завершение второго этапа |
|
||
Если |
~ |
|
|
x a , то кратчайший путь найден – его образует последова- |
тельность дуг, полученных на пятом шаге и выстроенных в обратном порядке. Иначе – возвращаемся к пятому шагу.
►Пример. Найти минимальный путь из вершины x1 в вершину x6 сети, заданной матрицей весов, по алгоритму Дейкстры.
|
|
x1 x2 |
x3 |
x4 |
x5 |
x6 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
x1 |
9 |
|
6 |
11 |
|
|
|
x2 |
|
8 |
|
|
|
|
|
x3 |
|
|
|
6 |
9 . |
|
|
x4 |
5 |
7 |
|
6 |
|
|
|
x5 |
6 |
|
|
|
4 |
|
|
x6 |
|
|
|
|
|
|
Решение. Изобразим сеть, заданную матрицей |
|
(рис. 1): |
|||||
x4 ( |
,6*) |
x3 ( |
,13*) |
|
|
||
|
|
x2 |
|
|
|
|
|
x1 |
( |
,9*) |
|
x6 |
|
|
|
|
|
|
|
|
|||
(0*) |
|
|
|
|
( |
,15*) |
|
|
|
|
|
|
|
|
x5 ( ,11*)
88
Рис. 1
Этап 1
Шаг 1. Полагаем d (x1 ) |
0 |
* |
, |
~ |
|
|
x1 . |
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
d (x2 ) |
d (x3 ) |
d (x4 ) |
|
d (x5 ) |
|
|
d (x6 ) |
|
. |
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Итерация 1 |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
~ |
|
|
x1 с |
Шаг 2. Множество вершин, непосредственно следующих за x |
|
|
||||||||||||||||||||||||||
временными |
метками |
~ |
|
|
|
|
|
|
|
, x5} . Пересчитываем |
временные |
метки |
||||||||||||||||
S |
{x2 , x4 |
|||||||||||||||||||||||||||
этих вершин: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
d (x |
2 |
) |
|
min{ |
, 0* |
9} |
9 , |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
d (x |
4 |
) |
|
|
min{ |
, 0* |
6} |
6 , |
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
d (x ) |
|
|
|
min{ |
, 0* |
11} |
11 . |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 3. Одна из временных меток превращается в постоянную: |
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
min{ 9, |
, 6, 11, |
|
} |
6 |
* |
d (x4 ) , |
~ |
x4 . |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
x |
|
|
|
|
|||||||||||||||||
Шаг 4. |
x4 |
|
~ |
b |
x6 |
, возвращаемся на второй шаг. |
|
|
|
|
||||||||||||||||||
|
x |
|
|
|
|
|||||||||||||||||||||||
|
~ |
|
|
|
|
|
|
|
|
|
|
|
|
Итерация 2 |
|
|
|
|
|
|
|
|||||||
Шаг 2. |
{x2 , x3 , x5}, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
S |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
d (x |
2 |
) |
|
min{ 9, 6* |
5} |
9 , |
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
d (x ) |
|
|
min{ |
, 6* |
7} |
13 , |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
d (x ) |
|
|
min{ 11, 6* |
6} |
11. |
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 3. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
min{ d (x |
2 |
), d (x ), d (x ), d (x |
6 |
)} |
min{ 9, 13, 11, |
} |
9* d (x |
2 |
) , |
|||||||||||||||||||
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
~ |
x2 . |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|||
Шаг 4. x2 |
|
x6 , возвращаемся на второй шаг. |
|
|
|
|
|
|
|
|||||||||||||||||||
|
~ |
|
|
|
|
|
|
|
|
|
|
|
|
Итерация 3 |
|
|
|
|
|
|
|
|||||||
Шаг 2. |
{x3}, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
S |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
d (x ) |
|
|
min{ 13, 9* |
8} |
13 . |
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 3. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
min{ d (x ), d (x ), d (x |
6 |
)} |
min{ 13, 11, |
} |
11* |
d (x ) , |
|
|
|
||||||||||||||||||
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
~ |
x5 . |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|||
Шаг 4. x5 |
|
x6 , возвращаемся на второй шаг. |
|
|
|
|
|
|
|
|||||||||||||||||||
|
~ |
|
|
|
|
|
|
|
|
|
|
|
|
Итерация 4 |
|
|
|
|
|
|
|
|||||||
Шаг 2. |
{x6}, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
S |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
d (x6 ) |
|
|
|
min{ |
, 11* |
4} |
15 . |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
89 |
Шаг 3.
|
|
|
min{ d (x ), d (x |
6 |
)} |
|
min{ 13, 15} |
13* |
d (x ) , |
||||||||||
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
~ |
x3 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
Шаг 4. x3 |
x6 , возвращаемся на второй шаг. |
|
|
|||||||||||||||
|
|
~ |
|
|
|
|
|
|
|
|
Итерация 5 |
|
|
|
|
||||
|
Шаг 2. |
{x6}, |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
S |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
d (x |
6 |
) |
|
|
min{ 15, 13* 9} |
15 . |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шаг 3. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
min{ d (x |
6 |
)} |
min{ 15} |
|
15* , |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
~ |
x6 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
Шаг 4. x6 |
t |
|
x6 , конец первого этапа. |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Этап 2 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
Итерация 1 |
|
|
|
|
||||
|
Шаг 5. Составим множество вершин, непосредственно предшеству- |
||||||||||||||||||
ющих |
~ |
с постоянными метками |
~ |
|
|
|
|
|
|||||||||||
x x6 |
S {x3 , x5}. Проверим для этих двух |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
~ |
|
|
|
|
|
~ |
|
|
|
вершин выполнение равенства d (x ) |
|
d (xi ) щ(xi , x ) : |
|
||||||||||||||||
|
~ |
|
|
* |
4 d (x5 ) щ(x5 |
, x6 ) , |
|
|
|
|
|||||||||
|
d (x ) 15 11 |
|
|
|
|
|
|||||||||||||
|
~ |
|
|
|
* |
9 d (x3 ) щ(x3 |
, x6 ) . |
|
|
|
|
||||||||
|
d (x ) 15 13 |
|
|
|
|
|
|||||||||||||
|
Включаем дугу (x5 , x6 ) в кратчайший путь. |
|
~ |
x5 . |
|
||||||||||||||
|
|
x |
|
||||||||||||||||
|
Шаг 6. |
~ |
a x1 , возвращаемся на пятый шаг. |
|
|||||||||||||||
|
x |
|
|||||||||||||||||
|
|
~ |
|
|
|
|
|
|
|
|
Итерация 2 |
|
|
|
|
||||
|
Шаг 5. |
{x1, x4}. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
S |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
~ |
|
|
* |
|
11 d (x1 ) щ(x1 , x5 ) , |
|
|
|
|
|||||||||
|
d (x ) 11 0 |
|
|
|
|
|
|
||||||||||||
|
~ |
|
|
* |
|
6 d (x4 ) щ(x4 , x5 ) |
|
|
|
|
|
||||||||
|
d (x ) 11 6 |
|
|
|
|
|
|
|
|||||||||||
|
Включаем дугу (x1 , x5 ) в кратчайший путь. |
~ |
x1 . |
|
|||||||||||||||
|
|
x |
|
||||||||||||||||
|
Шаг 6. |
~ |
a |
|
|
x1 , завершаем второй этап. |
|
|
|
|
|||||||||
|
x |
|
|
|
|
|
|
||||||||||||
|
Кратчайший путь от x1 |
|
до x6 |
построен: |
|
x1 |
x5 |
x6 . Его длина |
|||||||||||
(вес) равна 15. ◄ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
90
ЛЕКЦИЯ 12. ПЛАНАРНОСТЬ ГРАФОВ
Графы плоские и планарные. Ранее отмечалось, что один и тот же граф можно изобразить по-разному. Например, на рис. 1 представлено изображение одного и того же графа, так как в обоих случаях содержится одна и та же информация о вершинах, дугах и их взаимных связях.
x4 |
x2 |
x3 |
|
x1 |
|
|
x1 |
x4 |
x3 |
|
|
|
x2 |
|
Рис. 1 |
Это свойство графов называется изоморфностью. Оно используется, например, при ответе на вопросы:
–можно ли схему какого-либо электронного устройства изобразить на плоскости без пересечений проводников?
–можно ли сделать проект участка железноили автодорожного полотна без пересечений?
Такие вопросы приводят к понятию плоского графа.
Плоским называется граф, вершины которого являются точками плоскости, а рѐбра – непрерывными линиями без самопересечений и никакие два из них не имеют общих точек кроме инцидентной им вершины.
Любой граф, изоморфный плоскому, называется планарным.
На рис. 2 изображены планарный (слева) и плоский (справа) графы.
91
x1 |
x2 |
x3 |
x1 |
x2 |
x3 |
x7 |
x6 |
x5 |
x4 |
x7 |
x6 |
x5 |
x4 |
Рис. 2
Другими словами, если граф можно изобразить на плоскости так, что его рѐбра не пересекаются, он – планарный, иначе – непланарный.
Гранью планарного графа называется максимальное множество точек плоскости, каждую пару которых можно соединить плоской кривой, не пересекающей рѐбер этого графа. Например, плоский граф на рис. 2 имеет восемь граней.
Границей грани называется множество вершин и рѐбер, принадлежащих этой грани. Заметим, что граница каждой грани является циклом.
Существует теорема (Эйлера), с помощью которой можно ответить на вопрос «является ли планарным связный граф, имеющий n вершин, m рѐбер, f граней?»
Теорема Эйлера. Для всякого связного планарного графа верно равенство
n m f 2 ,
где n , m , f – число вершин, рѐбер, граней (соответственно) планарного графа.
Например, для куба имеем: 8-12+6=2 (рис. 3).
x2 |
x3 |
x6 |
x7 |
x1 |
x4 |
x1 |
x2 |
x7 |
x8 |
|
|
|
|
x4 |
x3 |
x6 |
x5 |
x5 |
x8 |
|
|
Рис. 3
92
Имеется несколько критериев планарности и найдены эффективные алгоритмы нахождения плоского графа, изоморфного данному планарному (алгоритмы плоской укладки графа).
Чтобы познакомиться с ними, рассмотрим несколько определений. Порядком графа называется число его вершин графа.
Простым называется граф без петель и кратных рѐбер.
Полным называется простой граф, в котором каждые две вершины смежные. Обозначение полных графов порядка n 1, 2, 3, 4 (рис. 4): Kn .
К1 |
К2 |
К3 |
К4 |
|
|
Рис. 4
Граф, множество вершин которого можно разбить на две части (доли) так, чтобы концы каждого ребра принадлежали разным частям, называется двудольным. Обозначение: K p, q , где p и q – число вершин в раз-
ных долях. На рис. 5 изображены двудольные графы K1, 4 и K3, 3 .
93
К1, 4 |
К3, 3 |
Рис. 5
Если при этом любые две вершины, входящие в разные доли, смежны, граф называется полным двудольным.
Подразбиением ребра называется добавление на него новой вершины, в результате чего оно заменяется двумя рѐбрами.
Два графа называются гомеоморфными, если они могут получиться из третьего подразбиением его рѐбер.
На рис. 6 изображены исходный граф G и два гомеоморфных графа
G1 и G2 .
G |
G1 |
G2 |
Рис. 6
94
|
|
|
|
a |
Теорема |
Понтрягина10- |
|
|
|
Куратовского11. Граф планарен тогда и |
|
|
f |
|
только тогда, когда он не содержит под- |
e |
j |
b |
|
|
|
|
||
|
|
|
i |
h |
|
|
|
d |
c |
|
|
|
|
Рис. 8 |
К5 |
|
К3,3 |
|
|
|
Рис. 7 |
|
|
|
графов, гомеоморфных K5 |
или K3, 3 . |
|
|
|
Графы K5 и K3, 3 являются основными непланарными (рис. 7). Эквивалентная форма критерия планарности содержит
Теорема 1. Граф планарен тогда и только тогда, когда в нѐм нет подграфов, стягиваемых (то есть получаемых последовательностью отождествлений12 вершин, связанных рѐбрами) к графам K5 или K3, 3 .
►Пример. Докажем, что граф Петерсена (рис. 8) – непланарный.
10Лев Семѐнович Понтрягин (1908, Москва – 1988, Москва) – советский математик, академик АН СССР, Герой Социалистического Труда. В 14 лет потерял зрение в результате несчастного случая. Окончил МГУ. С 1939 года заведующий отделом Математического института им. В. А. Стеклова АН СССР, одновременно с 1935 года профессор МГУ. В топологии открыл общий закон двойственности и в связи с этим построил теорию характеров непрерывных групп; получил ряд результатов в теории гомотопий (классы Понтрягина). В теории колебаний главные результаты относятся к асимптотике релаксационных колебаний. В теории управления — создатель математической теории оптимальных процессов, в основе которой лежит т. н. принцип максимума Понтрягина; имеет фундаментальные результаты по дифференциальным играм.
11Казимир Куратовский (1896, Варшава – 1980, Варшава) – польский математик. В 1913 году поступил в Университет Глазго, однако из-за начавшейся Первой мировой войны прервал обучение и продолжил его в Варшавском университете, который окончил, защитив диссертацию в 1921 году. В 1927-1933 годах преподавал во Львовской Политехнике, затем вернулся в Варшавский университет и с 1934 до 1952 год возглавлял в нѐм отделение математики. С 1952 года член Польской академии наук, в 1957—1968 годах еѐ вице-президент. С 1948 до 1967 года возглавлял Институт математики Польской академии наук. Ведущей областью научных интересов Куратовского была топология.
12Пусть х1 и х2 – две произвольные вершины графа G, а G1=G\{x1}\{x2}. К G1 присоединим новую вершину y1, соединив еѐ ребром с каждой из вершин, входящих в объединение окружений вершин x1 и x2 в графе G. Построенный граф G1 получен из G отождествлением вершин x1 и x2.
95
Для этого нужно показать, что он содержит подграф, гомеоморфный K3, 3 . Пусть верхними вершинами будут e , f , g , нижними – j , a , i . Со-
единим каждую верхнюю вершину с каждой нижней (рис. 9). Видим, что вершина c не нужна, поэтому еѐ и рѐбра ей инцидентные удаляем. Остальные рѐбра пока присутствуют. Теперь можно удалить вершины h , b , d , формируя рѐбра ( f , j) , (a, g) , (e, i) соответственно, и получить граф, гомеоморфный предыдущему (рис. 10). Но последний граф можно изобразить как K3, 3 . Значит, исходный граф содержит подграф, гомео-
морфный K3, 3 . Поэтому граф Петерсена – непланарный. ◄
Наименьшее число рѐбер непланарного графа, удаление которых приводит его к планарному, называется числом планарности или искажѐнностью (обозначается sk ). Известно, что
sk Cn2 3n 6 , n 3.
Толщиной t непланарного графа называется наименьшее число его планарных подграфов, объединение которых даѐт сам граф.
Толщина графа равна минимальному числу плоскостей l , при котором граф G разбивается на плоские части Gi , i 1, 2, ..., l . Ясно, что тол-
|
|
d |
|
|
|
e |
f |
g |
e |
f |
g |
|
|
|
|||
h |
|
|
|
||
|
|
|
|
|
|
|
b |
|
|
|
|
j |
a |
i |
j |
a |
i |
|
Рис. 9 |
|
|
Рис. 10 |
|
щина планарного графа равна единице. Для толщины связного графа с n вершинами и m рѐбрами найдены оценки:
|
t |
|
m |
|
, |
|
|
|
|
|
|
|
|||
|
|
3n |
6 |
|
|||
|
t |
m 3n |
7 |
|
, |
||
|
|
|
|
|
|
||
|
3n |
6 |
|
|
|||
|
|
|
|
|
|||
где |
– целая часть числа, а |
1 . |
|
|
|
|
96