ебучая теория

/*Обход графа: поиск в глубину
Поиск в глубину позволяет обойти все вершины графа по одному разу, переходя от вершины к вершине по ребрам.
Поиск в глубину реализуется рекурсивным алгоритмом:
Пусть выбрана некоторая не рассмотренная ранее вершина A
Перебираем все исходящие из A ребра, при этом:
если ребро ведет в не рассмотренную ранее вершину B, то продолжаем поиск рекурсивно от B
после обработки B возвращаемся в A и продолжаем перебирать исходящие из A ребра
если все ребра из A проверены, то либо возвращаемся к вершине, из которой мы пришли в A (если такая есть), либо выбираем любую ранее не проверенную вершину и выполняем алгоритм от нее.
Граф 𝐺={𝑉,𝐸} связный, если для любой пары вершин 𝑣,𝑤 𝜖 𝑉 существует соединяющий их маршрут, проходящий по ребрам.
Поиск в глубину разбивает множество ребер 𝐸 на 2 подмножества: древесные (от текущей вершины к непроверенной) и обратные (к уже проверенной вершине). Древесные ребра образуют дерево (связный граф без циклов), для которого определен порядок обхода вершин при поиске в глубину.
Компоненты связности неориентированного графа это максимальные (по включению вершин) связные подграфы.
Для выделения компонент связности используем поиск в глубину, внеся следующие изменения:
добавим в класс MGraph целую переменную comptotal, в которой будет вычисляться число компонент
изменим процесс формирования массива R: R[i] будет хранить номер компоненты (от 1), включающую вершину i (R[i]=0, если вершина i еще не просмотрена).
Приводимые далее методы cdeep и  get_comp – это модификации методов deep и DFS.


 Обход графа: поиск в ширину
Поиск в ширину обычно используется для проверки, существует ли маршрут из некоторой вершины-источника v в целевую вершину w, проходящий по ребрам графа.
В процессе поиска вершины помещаются в очередь для просмотра. Начальная очередь содержит только v.
Пусть u – текущая извлекаемая из очереди вершина.
Рассмотрим все ребра (u,x), при этом возможны варианты:
x просмотрена или находится в очереди – изменений нет,
x=w – маршрут найден, алгоритм завершается
x добавляется в очередь.
Если w не найдена, то после обработки всех ребер (u,x) из очереди выбирается следующая текущая вершина u, и поиск продолжается.
Если очередь закончилась, то маршрута из v в w нет.
При поиске в ширину можно не только определить, существует ли маршрут из v в w, но и вычислить его минимальную длину (минимальное число пройденных ребер). Для этого нужно вычислять уровни просмотренных вершин (массив Lev[0…n-1]):
вершина-источник v имеет уровень 1, начальные значения для остальных вершин Lev[i]=0 (это означает, что вершина i еще не рассмотрена),
если Lev[u]=a, существует ребро (u,x) и Lev[x]=0, то для x устанавливается значение уровня Lev[x]=a+1,
если Lev[w]>0, то существует, по крайней мере, один маршрут, и кратчайший маршрут содержит Lev[w]-1 ребро.
Функция для поиска в ширину имеет 1 параметр – номер v (от 0) вершины-источника. Поиск закончится, когда будут просмотрены все вершины, достижимые из v.
Для всех вершин графа будем формировать и возвращать массив уровней вершин Lev.
Если в результате поиска Lev[w]=0 для некоторой вершины w, то w не достижима из v.
Для организации очереди используем класс IQueue (очередь целых чисел) из раздела «Структуры и классы».


Задача раскраски графов
Задан неориентированный граф   с   вершинами.
Раскрасить вершины   в   цветов – это значит найти такое отображение  , что   ребра   выполняется   (т.е. смежные вершины имеют разные цвета).
Граф называется  -раскрашиваемым, если для него существует хотя бы одна раскраска в   цветов.
Характеристикой любого графа   является его хроматическое число   – минимальное число цветов, необходимое для раскраски  . Обычно требуется найти именно минимальную раскраску вершин в   цветов.

Поиск минимальной раскраски по методу ветвей и границ:
1. Каким-то образом определяется начальная раскраска с числом цветов   (например,  , вершина   красится в цвет  ). Далее эта раскраска считается текущей минимальной.
2. Вершина 1 красится в цвет 1 (начало формирования текущей раскраски).
3. Пусть в текущей раскраске первые   вершин уже покрашены в   цветов. Для вершины   проверяется возможность ее покраски в цвета  , и для каждого допустимого варианта раскраска продолжается рекурсивно.
4. Если в текущей раскраске покрашено   вершин и использовано   цветов, то поиск продолжается, только если нужны все решения.
5. Текущая раскраска   вершин, содержащая   цветов, становится текущей минимальной.

В приведенном ниже алгоритме используются переменные (для связи с предыдущим описанием используем нумерацию вершин и цветов от 1):
Pmin[1…n] – текущая минимальная раскраска,
zmin – число различных цветов в Pmin,
Pcur[1…n] – текущая раскраска,
zmax – максимальное число цветов, используемых на текущем шаге,
zcur – число различных цветов в Pcur на текущем шаге,
С – матрица смежности.
*/