% (c) by Tabaldyew

\def\ver{LaTeX2e}
\ifx\ver\fmtname\else
\newlinechar`^^J
\message{^^J^^JThis document only for^^J}
\message{Only for LaTeX 2 epsilon^^J}
\message{*** Press Enter ***^^J}
\read-1to\line \nonstopmode\read-1to\line\fi

\documentclass{article}
\usepackage{emlines2}
\begin{document}
\section{Постановка задачи}
\begin{enumerate}
\item Составить алгоритм нахождения хроматического числа графа.
\item Использовать данный алгоритм для правильной раскрасски рёбер графа.
\end{enumerate}

\section{Алгоритм}
\subsection{Отделяем от матрицы компонеты связности}
Для отделения компонент связности используется массив mask.
Его элементы имеют три состояния.
\begin{itemize}
\item[undef] не обработаные элементы
\item[work] выделеные в данный момент элементы
\item[done] элементы раскраска которых уже найдена
\end{itemize}
\begin{itemize}
\item На первом этапе отбрасываются вершины не имеющие рёбер.
\begin{verbatim}
enum topStat{undef,work,done}*mask;	mask=new(topStat[tsize]);
for(x=0; x<tsize; x++)
{
	for(y=0; y<tsize; y++) {if(topMatrix.Get(x,y)!=0xffff) break;}
	if(y==tsize) mask[x]=done; else mask[x]=undef;
}
\end{verbatim}

\item
Находим первую не обработаную вершину.
\begin{verbatim}
for(first=0; first<tsize; first++) {if(mask[first]==undef) break;}
	if(first==tsize) return;
\end{verbatim}

\item
Находим все вершины связанные с данной вершиной
\begin{verbatim}
n=0; bool loop;		// отделяем компонету связности графа
do{
	loop=false;
	for(x=0; x<tsize; x++)
	{
		if (mask[x]!=work) continue;
		for(y=x+1; y<tsize; y++)
		{
			if(mask[y]==undef && topMatrix.Get(x,y)!=0xffff)
			{
				mask[y]=work;
				n++;
				loop=true;
				if(y+1>last) last=y+1;
			}
		}
	}
}while(loop);
\end{verbatim}
Элементы first и last Содержат первый и последний элемент выделенной
компоненты связности. (это необходимо для того чтобы в не просматривать
в дальнейшем лишние элементы, а работать только в нужно диапазоне матрицы).

\item Находим раскрасску для выделенных таким образом вершин.
\item Помечаем обработаные вершины как обработаные
\begin{verbatim}
for(n=0; n<tsize; n++) {if(mask[n]==work) mask[n]=done;}
\end{verbatim}
\end{itemize}


\subsection{Преобразование матрицы}
Для выделенной компоненты связности происходит преобразование матрицы смежности.
Составляется новая матрица вершинами которого становится рёбра исходного графа.
\begin{verbatim}
for(n=0; n<tsize; n++) { if(mask[n]!=work) continue;	// выворачиваем матрицу наизнанку
for(a=0; a<tsize; a++) { WORD x=topMatrix.Get(n,a); if(x==0xffff) continue;
for(b=0; b<tsize; b++) {
	WORD y=topMatrix.Get(b,n);
	if (y!=0xffff) matrix.Set(back[x],back[y],true);
}}}
\end{verbatim}


\subsection{Прямой перебор}
Производится прямой перебор всех вариантов раскраски. Во время перебора
цвет отдельной вершины не превышает номер самой вершины. Кроме того
отбрасываются варианты в которых цвет вершины равен уже найденому количеству
цветов.

\begin{verbatim}
void Nucleus::FindSub(int depth)
{
	int n,m;
	if(depth==matrix.GetSize())
	{
		for(n=m=0; n<matrix.GetSize(); n++)
			{ if(buffer[n]>m) m=buffer[n]; }
		if (m<MinColors)
			{ memcpy(result,buffer,depth*sizeof(WORD)); MinColors=m; }
		return;
	}
	for(n=0; n<=depth; n++)
	{
		if(n==MinColors) break;
		for(m=0; m<depth; m++)
		{
			if(matrix.Get(m,depth) && buffer[m]==n) break;
		}
		if(m<depth) continue;
		buffer[depth]=n;
		FindSub(depth+1);
		if(MinColors==estimate) return;
	}
}
\end{verbatim}


\subsection{Эвристики}
Перед началом грубого перебора программа пытается упростить граф.
То есть уменьшить его размер и сократить таким образом количество
перебираемых вариантов.

\subsubsection{Удаление хвостов}
\begin{picture}(252.00,95.00)
\special{em:linewidth 0.4pt}
\emline{62.00}{17.00}{0}{30.00}{56.00}{1}
\emline{61.00}{95.00}{2}{30.00}{56.00}{3}
\emline{61.00}{95.00}{4}{96.00}{55.00}{5}
\emline{62.00}{17.00}{6}{96.00}{55.00}{7}
\special{em:linewidth 1.4pt}
\emline{150.00}{67.00}{8}{96.00}{55.00}{9}
\emline{200.00}{55.00}{10}{150.00}{67.00}{11}
\emline{252.00}{59.00}{12}{200.00}{55.00}{13}
\special{em:linewidth 0.4pt}
\put(30.00,56.00){\circle*{4}}
\put(40.00,46.00){\makebox(0,0)[cc]{0}}
\put(96.00,55.00){\circle*{4}}
\put(106.00,45.00){\makebox(0,0)[cc]{1}}
\put(61.00,95.00){\circle*{4}}
\put(71.00,85.00){\makebox(0,0)[cc]{2}}
\put(62.00,17.00){\circle*{4}}
\put(72.00,07.00){\makebox(0,0)[cc]{3}}
\put(150.00,67.00){\circle*{4}}
\put(160.00,57.00){\makebox(0,0)[cc]{4}}
\put(200.00,55.00){\circle*{4}}
\put(210.00,45.00){\makebox(0,0)[cc]{5}}
\put(252.00,59.00){\circle*{4}}
\put(262.00,49.00){\makebox(0,0)[cc]{6}}
\end{picture}
Вершину номер (6)
(а следовательно и вершины (4)(5))
 можно просто исключить из грубого перебора, поскольку
её цвет можно найти отдельно и на общую раскраску графа её цвет не
влияет. Сама эвристика сводится лишь к поиску вершин имеющих одну всяз.

\subsubsection{Уничтожение одинаковых вершин}
Находим в заданном графе две вершины, которые не связанны
между собой и в то же время связанны с одинаковым набором вершин.
Одну из таких вершин можно удалить до начала перебора, поскольку
таким вершинам можно всегда присваивать одинаковый цвет.
\par
\begin{picture}(185.00,178.00)
\emline{93.00}{93.00}{0}{75.00}{19.00}{1}
\emline{75.00}{178.00}{2}{93.00}{93.00}{3}
\emline{75.00}{178.00}{4}{75.00}{19.00}{5}
\emline{185.00}{32.00}{6}{75.00}{19.00}{7}
\emline{185.00}{32.00}{8}{93.00}{93.00}{9}
\emline{185.00}{32.00}{10}{75.00}{178.00}{11}
\emline{184.00}{122.00}{12}{75.00}{19.00}{13}
\emline{184.00}{122.00}{14}{75.00}{178.00}{15}
\emline{184.00}{122.00}{16}{93.00}{93.00}{17}
\put(75.00,19.00){\circle*{9}}
\put(85.00,9.00){\makebox(0,0)[cc]{0}}
\put(93.00,93.00){\circle*{9}}
\put(103.00,83.00){\makebox(0,0)[cc]{1}}
\put(75.00,178.00){\circle*{9}}
\put(85.00,168.00){\makebox(0,0)[cc]{2}}
\put(185.00,32.00){\circle*{9}}
\put(185.00,32.00){\circle{13}}
\put(195.00,22.00){\makebox(0,0)[cc]{3}}
\put(184.00,122.00){\circle*{9}}
\put(184.00,122.00){\circle{13}}
\put(194.00,112.00){\makebox(0,0)[cc]{4}}
\end{picture}

В указанном примере вершина номер (3), может не участвовать в грубом переборе.

\subsubsection{Сокращение путей}
Cокращение длинных цепочек вершин.

\begin{picture}(212.00,133.00)
%\special{em:linewidth 0.01pt}
%\emline{212.00}{84.00}{0}{73.00}{82.00}{1}
%\special{em:linewidth 1.0pt}
\emline{168.00}{133.00}{2}{212.00}{84.00}{3}
\emline{117.00}{133.00}{4}{212.00}{84.00}{5}
\emline{168.00}{133.00}{6}{73.00}{82.00}{7}
\emline{117.00}{133.00}{8}{73.00}{82.00}{9}
\emline{168.00}{133.00}{10}{117.00}{133.00}{11}
\emline{170.00}{15.00}{12}{212.00}{84.00}{13}
\emline{98.00}{13.00}{14}{73.00}{82.00}{15}
\emline{98.00}{13.00}{16}{170.00}{15.00}{17}
%\special{em:linewidth 0.4pt}
\put(73.00,82.00){\circle*{4}}
\put(83.00,72.00){\makebox(0,0)[cc]{0}}
\put(212.00,84.00){\circle*{4}}
\put(222.00,74.00){\makebox(0,0)[cc]{1}}
\put(117.00,133.00){\circle*{4}}
\put(127.00,123.00){\makebox(0,0)[cc]{2}}
\put(168.00,133.00){\circle*{4}}
\put(178.00,123.00){\makebox(0,0)[cc]{3}}
\put(170.00,15.00){\circle*{4}}
\put(180.00,5.00){\makebox(0,0)[cc]{4}}
\put(98.00,13.00){\circle*{4}}
\put(108.00,3.00){\makebox(0,0)[cc]{5}}
\end{picture}

В данном примере вершины (4) и (5) можно искючить из перебора, соеденив
вершины (0) и (1) напрямую. А цвет вершин (4) и (5) указать после перебора.
Цвет вершины (4) можно взять из вершины (0).
Цвет вершины (5) можно взять из вершины (1).

Сама процедура поиска сводится к поиску двух вершин имеющих две связи
и связанных между собой.

\subsubsection{Дополнительный распад}
Находим рёбра, которые не являются составляющими циклов и удаление
которых приведёт  распаду графа на два не связанных между собой подграфа.
После удаления поиск цветов ведётся для каждой компоненты отдельно.
А после поиска ведётся стыковка разделёных компонент.
Если связь между компонетами состоит из одного ребра и цвета вершин
на стыке совпадает, то для одной из компонент производится циклический
сдвиг цветов.

\begin{picture}(305.00,93.00)
\emline{163.00}{60.00}{0}{129.00}{30.00}{1}
\emline{163.00}{60.00}{2}{127.00}{93.00}{3}
\emline{127.00}{93.00}{4}{88.00}{65.00}{5}
\emline{129.00}{30.00}{6}{88.00}{65.00}{7}
\emline{269.00}{22.00}{8}{233.00}{60.00}{9}
\emline{305.00}{53.00}{10}{269.00}{22.00}{11}
\emline{265.00}{93.00}{12}{305.00}{53.00}{13}
\emline{265.00}{93.00}{14}{233.00}{60.00}{15}
\emline{233.00}{60.00}{16}{163.00}{60.00}{17}
\put(88.00,65.00){\circle*{4}}
\put(98.00,55.00){\makebox(0,0)[cc]{0}}
\put(129.00,30.00){\circle*{4}}
\put(139.00,20.00){\makebox(0,0)[cc]{1}}
\put(127.00,93.00){\circle*{4}}
\put(137.00,83.00){\makebox(0,0)[cc]{2}}
\put(163.00,60.00){\circle*{4}}
\put(173.00,50.00){\makebox(0,0)[cc]{3}}
\put(233.00,60.00){\circle*{4}}
\put(243.00,50.00){\makebox(0,0)[cc]{4}}
\put(269.00,22.00){\circle*{4}}
\put(279.00,12.00){\makebox(0,0)[cc]{5}}
\put(305.00,53.00){\circle*{4}}
\put(315.00,43.00){\makebox(0,0)[cc]{6}}
\put(265.00,93.00){\circle*{4}}
\put(275.00,83.00){\makebox(0,0)[cc]{7}}
\end{picture}

В данном примере удаляется связь (3) - (4).


\subsection{Оценочная функция}
Программа находит в графе подграф в котором каждые две вершины
попарно связанны между собой. Поскольку раскрасска графа у которого все
вершины всязанны между собой равна количеству вершин графа, то
расскраска весго графа также не может быть меньше чем число вершин
данного подграфа. И поиск расскраски графа будет остановлен, если
найдена раскраска с таким количеством цветов.

\begin{verbatim}
void Nucleus::Estimate(int n, int depth)
{
	stack[depth]=n; int m;
	for(m=0; m<depth; m++)
	{
		if(stack[m]==n) continue;
		if(matrix.Get(n,stack[m])) return;
		if(matrix.Get(stack[m],n)) return;
	}
	depth++; if(depth>minRes) minRes=depth;
	for(m=n+1; m<size; m++)
	{
		Estimate(m,depth);
	}
}
\end{verbatim}


\section{Cистема данных}
В чистом виде граф хранится ввиде двух списков структур.
Списка вершин (координаты X Y Z).
и Списка связей (номера соеденяемых вершин, цвет ребра,
относительный радиус кривизны).

Непосредственно перед поиском списки преобразуются в матрицы.
\begin{verbatim}
for(n=0; n<lsize; n++) topMatrix.Set(graph->GetLINK(n),n);
\end{verbatim}

В качестве матриц используться специальный процедуры.
После иницализации которых информация хранится ввиде BSP-деревьев.
Если количество элементов в матрице переходит некое пороговое значение,
то BSP-дерево перестраивается в трегольную матрицы (доступ
к элементам которого осуществляется по формуле $\frac{y\cdot (y-1)}2+x$).

\section{Оценка сложности}
\begin{enumerate}
\item
Сложность алгоритма создающего матрицу смежности зависит только от числа берёр
в графе $\displaystyle O(L)$ - где L число рёбер.
\item
Сложность процедуры грубого перебора равна количеству перебираемых вариантов
$\displaystyle O(Q!)$ - где Q это число вершин в графе.
\item
Сложность процедуры удаления хвостов $\displaystyle O(Q)$ - где Q - количество вершин.
\item
Сложность процедуры удаления одинаковых вершин $\displaystyle O(\frac{Q(Q-1)}2\cdot Q)=\frac{Q^2(Q-1)}2$ 
- где Q количество вершин, $\displaystyle \frac{Q(Q-1)}2$ количество попарно 
сравниваемых вершин, Q - стоимость сравнения.
\item
Сложность процедуры сокращения путей $\displaystyle O(\frac{Q(Q-1)}2)$ - где Q количество вершин.
\item
Сложность процедуры дополнительного распада $\displaystyle O(Q^3)$ - где Q количество вершин.
\item
Сложность оценочной функции $\displaystyle O(\frac{Q(Q-1)}2)$
\end{enumerate}

Итого общая сложность алгоритма в худшем случае не превышает $\displaystyle O(Q!)$.

\end{document}
