МИНИСТЕРСТВООБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙФЕДЕРАЦИИ
ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
КафедраСАПР
Пояснительнаязаписка
ккурсовому проекту по дисциплине
“Дискретнаяматематика”
На тему: “Алгоритм раскраски графа(точный)"
Выполнил: студентка гр.06ВА-1
Молоткова Е.
Принял: к.т.н., доцент ВалькоА.Ф.
Пенза2007г.
СОДЕРЖАНИЕ
Аннотация
1. Теоретическая часть
2. Алгоритм, использующий метод Магу — Вейссмана
2.2 Разработанный алгоритм
3. Описание программы
3.1 Общие сведения
3.2 Вызов и загрузка
3.3 Функциональное назначение
3.4 Описание логической структуры программы
3.5 Инструкция пользователю
3.6 Решение контрольных примеров
Заключение
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ
Аннотация
В настоящейпояснительной записке приведено описание алгоритма раскраски графа (точный).Изложены вопросы проектирования структуры программы и данных. Разработаны схемыалгоритмов решения задачи. Разработана и отлажена программа, реализующаяпредставленные алгоритмы на языке Visual C. Представлены результаты решенияконтрольных примеров, выполненные с помощью разработанной программы на ПК Intelcore 2 Duo.
Пояснительнаязаписка содержит 34 страницы, 5 рисунков, 4 использованных источника, приложения.
1. Теоретическая часть
Графом, в общемслучае, называются два множества, находящиеся между собой в некоторомотношении: G=(V, Е), где V – множество вершин, Е – множество связей между ними.Вершины графа изображаются точками, а связи между ними – линиями произвольнойконфигурации.
Связьнеупорядоченной пары вершин называется ребром, упорядоченной- дугой. Граф, укоторого все вершины соединены дугами называется ориентированным. Граф, укоторого все вершины соединены ребрами называется неориентированным, если вграфе присутствуют и ребра и дуги, то такой граф называется смешанным.
Две вершиныназываются смежными, если они определяют дугу (ребро), и две дуги называютсясмежными, если они имеют общую вершину. Вершина инцидентна дуге (ребру), еслиона является началом или концом этой дуги(ребра). Аналогично, дуга (ребро)инцидентна вершине, если она входит или выходит из этой вершины. Числодуг(ребер), инцидентных некоторой вершине, называют локальной степенью даннойвершины.
Граф, в которомлюбая пара вершин соединена ребром называется полным. Полный граф обычнообозначают через Кn (n – число вершин в графе).
Число реберполного графа m=n*(n-1)/2. Полный подграф G`=(X`,U`)графа G=(Х,U), X`εXназывается максимальным полным подграфом (МПП) или кликой, если этот подграфне содержится в большем (по числу вершин) полном подграфе.
Максимальныйполный подграф, содержащий наибольшее число вершин из всех МПП графа называетсянаибольшим полным подграфом (НПП). Число вершин наибольшего полного подграфаназывается плотностью графа – φ(G). Если две любые вершины подмножества X` графа G(Х,U), где X`εX не смежны, то подмножество X` называетсявнутренне устойчивым.
Подмножествоψi X графа G(Х,U) называется максимальным внутренне устойчивымподмножеством (МВУП), или независимым подмножеством (НП), если добавление кнему любой вершины xjεХ делает его не внутренне устойчивым. Подмножество Yiбудет определяться как хjεψi (Гхj uψi =)
МВУПразличаются по числу входящих в них элементов. МВУП, содержащее наибольшеечисло элементов (вершин), называют наибольшим (предельным). Мощность НВУП(число вершин наибольшего ВУП) называется числом внутренней устойчивости
h (G) = |mах ψi |, где ψiεψ, ψ-семейство всех МВУП.
Числовнутренней устойчивости называет также неплотностью графа.
Задачиопределения наибольших полных подграфов и НВУП являются дополнительными друг кдругу. Наибольшему полному подграфу графа G=(Х,U)соответствует наибольшее ВУП в графе G=(Х,U), где Uполн\U, Uполн – множество ребер полного графа, построенного на n вершинах.Аналогичные рассуждения могут быть сделаны и для максимальных НП и МВУП.
Все эти задачиотносятся к так называемым NP полным задачам, временная сложность которыхэкспоненциальна относительно входа (числа вершин или ребер графа).
Согласно классификациивсех задач теории графов по их сложности, приведенной в основополагающей работеЭ. Рейнгольда и других, задачи определения МВУП и МПП (нахождение клик) графапо сложности относятся к четвертому классу задач, для которых не существует ине может существовать точного полиноминального алгоритма, так как задачи этогокласса обязательно экспоненциальные относительно входа. Задачи определения НППи МВУП (наибольшей клики) относятся к третьему классу, для которого открытиеполиноминального алгоритма возможно.
2.Алгоритмы раскраски вершин графа
Раскраскойвершин графа Gназывается разбиение множества вершин Х на l непересекающихсяподмножеств Х1, Х2, ..., Хl; ХÈХI; XiÇXj=Æ; i,jÎI={1,2,..,l}, (1)
таких, чтовнутри каждого подмножества Xi не должно содержаться смежных вершин (Xi-внутренне устойчивыеподмножества).
Если каждомуподмножеству хi поставить в соответствие определенный цвет, товершины внутри этого подмножества можно окрасить в один цвет, вершины другогоподмножества Хj — в другой цвет и т.д. до раскраски всех подмножеств.
В этом случаеграф называется 1-раскрашиваемым. Наименьшее число подмножеств, на котороеразбивается граф при раскраске, называется хроматическим числом c(G).
Очевидно, чтополный граф Kn можно раскрасить только n цветами, следовательно, c(Кn) =n. Для связного графа G= (Х,U) с числом ребер m, где (n-1)
c(G)/>
Нижнейоценкой c(G) является число вершин внаибольшем полном подграфе графа G, т.е. его плотность. Известно утверждение, что для любогографа c(G)
c(G)³n2/(n2-m2); c(G)£n+1-c(Gд),
где Gд= К\G ( дополнение графа G до полного К).
Задачараскраски вершин (поиска хроматического числа) графа может быть решена точнымиили приближенными алгоритмами.
К точнымалгоритмам относятся: алгоритм, использующий метод Магу – Вейсмана; алгоритмы,основанные на рассмотрении максимальных r — подграфов и алгоритмына основе методов целочисленного линейного программирования.
Кприближенный алгоритмам раскраски относятся алгоритмы, основанные на упорядочиваниимножества вершин графов, последовательном удалении из графа вершин, имеющихмаксимальную степень и на анализе подмножеств смежности вершин.
2.1 Точные алгоритмы
Алгоритм, использующий метод Магу — Вейссмана
1. Для графа G (Х,U) построим семейство МВУПF={Fj}, где j= 1,… ,1; 1 — числоМВУП.
1. 2. Составимматрицу
Cij=/>
3. Для.каждой вершины графа G =(Х,U) по матрице С находим суммы тех FjÎF, в которые она входит, и записываем произведение этих сумм.
4. Раскрываемскобки по правилам булевой алгебры и выбираем слагаемое, состоящее изнаименьшего числа сомножителей.
Рассмотримработу описанного алгоритма на примере графа (рис.16).Согласно алгоритму Магу — Вейссмана для поиска семейства МВУП составим произведение
ПG = (X1 +Х2) (Х1+ХЗ) (Х2+ХЗ) (Х2+Х5) (Х2+Х7) (ХЗ+Х5) (ХЗ+Х6) (ХЗ+X7)*
(Х4+Х5)(Х4+Х6) (Х4+Х7) = (Х1+Х2ХЗ)*(Х2+ХЗХ5Х7) (ХЗ+Х5Х6Х7) (Х4++Х5Х6Х7) =(Х1Х2+Х1ХЗХ5Х7+Х2ХЗ+Х2ХЗХ5Х7) (ХЗХ4+ХЗХ5Х6Х7+Х4Х5Х6X7++Х5ХбХ7)=Х1Х2Х3Х4+Х1Х2Х5ХбХ7+Х1Х3Х4Х5X7+Х1Х3Х5Х6Х7+Х2ХЗХ4+
+Х2ХЗХ5Х6Х7. Рi= Х1Х2ХЗХ4 поглощаетсяподмножеством Р5 =Х2ХЗХ4.
Используяусловие, что в ПG в качестве сомножителей будут вершины Х\Рj получаем следующеесемейство
МВУП F={F1,F2,F3,F4,F5}: F1=X\{X1,X2,X5,X6,X7}={X3,X4}; F2={X2,X6}; F3={X2,X4}; F4={X1,X5,X6,X7}; F5={X1,X4}.
Составляемматрица C
/>
Для каждойвершины Хi Î Х по матрице С составим суммы тех FjÎF, в которые оно входит и запишем произведение этих сумм
ПС=(F4+F5)(F2+F3)F1*(F1+F3+F5)F4*(F2+F4)F4=(F2+F3F4)F1F4=F1F2F4+F1F3F4.
Каждое издвух полученных слагаемых содержит в неявном виде все вершины графа G =(Х,U), Таким
образом, дляраскраски требуется минимум 3 цвета. Раскроем слагаемые и удалим дублирующиевершины.
В результатеполучаем два варианта решения:
F1F2F4={ХЗ, Х4; Х2; Х1, Х5, Х6, Х7} или
F1F2F4={ ХЗ, Х4; Х2X6; Х1, Х5, Х7};
F1F3F4={X3;X2, Х4; Х1, Х5, Х6, Х7}
или F1F3F4={XЗ,X4;X2;X1,X5,Xб,X7}.
Первый ипоследний варианты совпали. Получены три различных варианта минимальнойраскраски вершин графа.
/>2.2 Разработанный алгоритм
Разработанныйалгоритм работает на основе операций с матрицей смежности.
Данныйалгоритм реализуется следующим образом:
За основу беретсяматрица смежности M для данного графа G.
Затемсоздается массив A, в каждой строке которого содержится множество вершин A[i].первым элементом этого множества является вершина Xi0, номер которой совпадаетс номером строки. Остальные члены этого множества – все вершины данного графаG, смежные первой вершине из этого множества.
Далее с этиммассивом A проводятся следующие манипуляции:
Множествовершин A[i] в каждой строке просматривается, начиная со второго элемента Xi1этого множества A[i], и по матрице смежности M устанавливается, смежна лиданная вершина Xij всем предыдущим вершинам из множества A[i], начиная с первой– Xi0. Если обнаруживается, что одна из вершин Xij при рассмотрении не смежна сдругими вершинами Xik (k=0,j-1) этого множества A[i], то она удаляется из этогомножества. Продолжается рассмотрение остальных вершин Xij до тех пор, покамножество не рассмотренных вершин не станет пустым. Таким образом, из данногомножества вершин A[i], смежных с первой вершиной этого множества – Xi0 будут удаленывсе те вершины, которые не смежны всем остальным вершинам этого множества A[i].Таким образом, оставшееся множество вершин A[i] будет являться максимальнымполным подграфом от первой вершины этого множества Xi0.
Послерассмотрения одного множества A[i] в массиве A рассматриваются следующие, потой же схеме. Из них также удаляются вершины. В конечном счече будет полученмассив A, в каждой i-й строке которого будет содержаться максимально полныйподграф A[i], возможный от i-й вершины Xi0.
На следующем шагеалгоритма будет создан еще один массив B, содержащий множество целых чисел.Каждый i-й элемент B[i] этого множества B представляет собой количество вершинв соответствующем максимально полном подграфе A[i]. Например если 3-й элементданного множества равен 5, это означает, что максимально полный подграф,построенный от 3-ей вершины состоит из 5 вершин, включая 3-ю. множество вершин{X30..X34}, которые составляют этот подграф A[3] является мнжеством вершин в 3строке массива A.
После того,как были созданы массивы A и B, создается линейный список С, каждый элементкоторого содержит множество вершин X, составляющих уникальный наибольший полныйподграф графа G.
Очевидно, чтомассив A будет содержать в себе одиаковые множества вершин. Единственнымотличием этих множеств друг от друга будет то, что первый элемент каждоготакого множества будет отличен от первого элемента такого же множества,находящегося в массиве A.
Например, еслив массиве A имеется следующее множество вершин, состовляющее полный подграф: {2,4,5,7},что означает, что во 2 строке массива А содержится это множество вершин,состоящее из 4 элементов, массив В содержит 4 одинаковых элемента – 4 поадресам 2,4,5,7. Однако это означает, что в 4, 5 и 7 строках массива А будетсодержаться то же самое множество вершин.
Во времяформирования списка С этот факт учитывается.
Списокформируется следующим образом: в массиве В ищется максимальный элемент bmax.Это целое число, показывающее размер наибольшего полного подграфа графа G.Затем просматривается массив В. И если соответствующий элемент B[i]по адресу iравен bmax, то создается новый элемент в списке, в него заносится наибольшийполный подграф из массива А по адресу i. Проводится дальнейший просмотр массиваВ и ищутся другие подграфы, содержащие bmax вершин. Если таковые находятся (аони обязательно находятся) то на этом этапе выполняется проверка, не добавленоли уже это множество вершин A[i] в список НПП. Проверка осуществляетсяследующим образом: список С просматривается сначала, и каждое множество вершин,содержащееся в элементе этого списка сравнивается с множеством A[i]. Еслиобнаруживается, что такое множество A[i] уже содержится в списке С, то онопропускается, происходит дальнейшее рассмотрение массива В. В противном случае,если такое множество не было найдено в списке, то создается еще одна ячейкасписка С и в нее записывается множество A[i].
Таким образом,после того, как закончится рассмотрение массива В, то есть будут рассмотренывсе возможные НПП и уникальные будут добавлены в список С, полученный список Сбудет содержать в себе все возможные НПП для данного графа G.
3. Описание программы
3.1 Общиесведения
Программанахождения максимально полного подграфа в произвольном графе реализована наязыке Visual C. Программа имеет имя diskretka.exe
Программасодержит около 705 строк, исполняемый код программы (файл diskretka.exe) занимает192 Кбайт оперативной памяти и примерно столько же на диске. Исходный текстпрограммы на языке Visual C (файл diskretka.cpp) занимает 15.8 Кбайт памяти на диске.
3.2 Вызови загрузка
В среде VisualCкоманда File àOpen Workspace àdiskretka.dsw
Запуск навыполнение – Ctrl+F5
3.3 Функциональноеназначение
Программапредназначена для нахождения максимально полного подграфа в произвольном графе.
Программавыполняет следующие функции:
1. Построение произвольного(неориентированного, ориентированного) графа с помощью мыши.
2. Добавление вершин и ребер в ужесуществующий граф, применение данных изменений.
3. Построение матриц смежности иинцидентности графа, поиск всевозможных максимально полных подграфов(еслитаковых имеется несколько) и реализован механизм покадрового просмотра найденныхподграфов.
В даннойпрограмме реализован лог событий (то, что происходит, в данный момент).
3.4 Описаниелогической структуры программы
Программаразбита на отдельные функциональные части – подпрограммы, которыераспределяются по отдельным уровням иерархии. Каждая из подпрограмм решаеттолько свою небольшую задачу по преобразованию данных, что позволяет упроститьпроцесс написания и отладки программы в целом. Далее приводится описания назначениявсех функций.
1. Функция WinMain является главнойфункцией программы, из которой производится вызов остальных функций.
2. Функция ABOUTDLG является функцийвсплывающего окна «О программе»
3. find_gr – функция ищет наиболее полныйподграф от текущей(переданной) вершины и возвращает массив подграфов
4. find_podgraf – функция созданияконечного списка наибольших полных подграфов(с наибольшим кол-вом вершин).
5. Функция cr_matr — функция создания ивывода матриц смежности и инцидентности.
6. Функция paint_podgraf — рисует подграфв области, выделенной для графа. Передается номер графа, который надонарисовать и список наибольших полных подграфов.
7. paint_mouse — процедура рисования графамышью.
8. MAINDLG — оконная процедура главногоокна программы.
Целью этапапроектирования программы является разработка алгоритмов решения поставленнойзадачи, т.е. разработка формальной последовательности действий, обеспечивающейполучение требуемых результатов для заданных исходных данных. На этом этаперешаются следующие задачи:
1. разработка алгоритма основнойпрограммы;
2. разработка детальных алгоритмовотдельных подпрограмм.
3.5 Инструкция пользователю.
Для работы сданной программой
необходимовыбрать инструмент:
вершина (флажокв диалоговой части окна «Что рисуем?»)
ребро (в этомже окне)
выбрать типрисуемого графа
ориентированный(флажокв диалоговой части окна «Тип графа»)
неориентированный(вэтом же окне)
нажать кнопку«приступить» и начать постреоние графа щелчком мыши в области «Собственно граф.Чертить здесь!»
нажать кнопки«применить изменения»à «Выполнить задачу!»
Дляредактирования графа
нажать кнопку«приступить» и начать редактирование графа(добавление вершин и ребер)
послеокончания редактирования нажать кнопки «применить изменения»à «Выполнить задачу!».
Для выхода изпрограммы жмем «Выход».
Входные ивыходные данные
Даннаяпрограмма является полностью динамической. Она не нуждается во внешнихисточниках данных. Входными данными служат вводимые в ходе выполнения программывершины и соединяющие их ребра.
3.6 Решениеконтрольных примеров
Пример1: Случай, когда имеется несколько МПП в данном графе.
Найден первыйМПП (выделен красным цветом).
Найден второйМПП (также выделен красным цветом).
/>
Пример 2: Графс одним МПП.
Найденмаксимально полный подграф(на рисунке красным цветом)
/>
Пример 3:Граф, состоящий из нескольких компонент.
/>
Заключение
На основе трехконтрольных примеров, мы получили верные результаты, что позволяет нам сделатьвывод о правильной реализации алгоритма программы.
СПИСОК ИСПОЛЬЗОВАННОЙЛИТЕРАТУРЫ
1. Методическое пособиепо дискретной математике
2. Библиотека MSDN
3. Яблонский С.В.«Введение в дискретную математику»
4. Новиков Ф.А.«Дискретная математика для программиста»
ПРИЛОЖЕНИЕ
Текстпрограммы
// kursovojDlg.cpp: implementation file
//
#include «stdafx.h»
#include «kursovoj.h»
#include «kursovojDlg.h»
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
int radio=0;
int kolv=0;
int paint=0;
int kolreb=0;
struct rebro1
{
int n,k;
};
struct versh1
{
int x,y;
};
struct umn1
{
int x1,x2;
};
versh1 versh[1000];
rebro1 rebro[2000];
int matsm[1000][1000];
umn1 umn[1000];
int mass[1000][100];
int fff[1000][100];
int colvo;
int masskol;
int colf,columnf;
int umnf[1000][100];
int rask,rat;
int rav=0;
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About
class CAboutDlg: public CDialog
{
public:
CAboutDlg();
// Dialog Data
//{{AFX_DATA(CAboutDlg)
enum { IDD = IDD_ABOUTBOX };
//}}AFX_DATA
// ClassWizard generated virtualfunction overrides
//{{AFX_VIRTUAL(CAboutDlg)
protected:
virtual voidDoDataExchange(CDataExchange* pDX); // DDX/DDV support
//}}AFX_VIRTUAL
// Implementation
protected:
//{{AFX_MSG(CAboutDlg)
virtual void OnOK();
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};
CAboutDlg::CAboutDlg():CDialog(CAboutDlg::IDD)
{
//{{AFX_DATA_INIT(CAboutDlg)
//}}AFX_DATA_INIT
}
voidCAboutDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CAboutDlg)
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
//{{AFX_MSG_MAP(CAboutDlg)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CKursovojDlg dialog
CKursovojDlg::CKursovojDlg(CWnd* pParent/*=NULL*/)
: CDialog(CKursovojDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CKursovojDlg)
//}}AFX_DATA_INIT
// Note that LoadIcon does not require asubsequent DestroyIcon in Win32
m_hIcon =AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
voidCKursovojDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CKursovojDlg)
DDX_Control(pDX, IDC_BUTTON4, m_r1);
DDX_Control(pDX, IDC_LIST3, m_l3);
DDX_Control(pDX, IDC_LIST2, m_l2);
DDX_Control(pDX, IDC_LIST1, m_l1);
DDX_Control(pDX, IDC_STATIC1, m_n1);
DDX_Control(pDX, IDC_BUTTON3, m_sbros);
DDX_Control(pDX, IDC_BUTTON2,m_primizm);
DDX_Control(pDX, IDC_BUTTON1, m_nach);
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CKursovojDlg, CDialog)
//{{AFX_MSG_MAP(CKursovojDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
ON_BN_CLICKED(IDC_RADIO1, OnRadio1)
ON_BN_CLICKED(IDC_RADIO2, OnRadio2)
ON_BN_CLICKED(IDC_STATIC1, OnStatic1)
ON_WM_LBUTTONDOWN()
ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
ON_BN_CLICKED(IDC_BUTTON4, OnButton4)
ON_BN_CLICKED(IDC_BUTTON5, OnButton5)
ON_BN_CLICKED(IDC_BUTTON6, OnButton6)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CKursovojDlg message handlers
BOOL CKursovojDlg::OnInitDialog()
{
CDialog::OnInitDialog();
// Add «About...» menu item tosystem menu.
// IDM_ABOUTBOX must be in the systemcommand range.
ASSERT((IDM_ABOUTBOX & 0xFFF0) ==IDM_ABOUTBOX);
ASSERT(IDM_ABOUTBOX
CMenu* pSysMenu = GetSystemMenu(FALSE);
if (pSysMenu != NULL)
{
CString strAboutMenu;
strAboutMenu.LoadString(IDS_ABOUTBOX);
if (!strAboutMenu.IsEmpty())
{
pSysMenu->AppendMenu(MF_SEPARATOR);
pSysMenu->AppendMenu(MF_STRING,IDM_ABOUTBOX, strAboutMenu);
}
}
// Set the icon for this dialog. Theframework does this automatically
// when the application's main window isnot a dialog
SetIcon(m_hIcon, TRUE);// Set big icon
SetIcon(m_hIcon, FALSE);// Set smallicon
// TODO: Add extra initialization here
return TRUE; // return TRUE unless youset the focus to a control
}
//------------------------------------------------------------------------------------------
void CKursovojDlg::ud(void)
{
int q;
int min,buf;
for (int u=0; u
for (int i=1; i
{
min=i;
for (int j=i+1; j
if (mass[u][j]
if (i!=min)
{
buf= mass[u][i];
mass[u][i] = mass[u][min];
mass[u][min]= buf;
}
}
for (int i=0; i
for (int y=0; y
if (i!=y)
{
q=0;
if((mass[i][0]==mass[y][0])&&(mass[i][0]>0))
for (int k=1; k
if (mass[i][k]==mass[y][k]) q++;
if (q==mass[y][0])
{
mass[y][0]=-1;
}
}
for (i=0; i
for (int y=0; y
if (i!=y)
{
q=0;
if ((mass[i][0]+1)==mass[y][0])
for (int j=1; j
for (int k=1; k
if (mass[i][j]==mass[y][k]) q++;
if (q==mass[i][0])
{
mass[y][0]=-1;
}
}
}
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
void CKursovojDlg::perre(void)
{
int q;
for (int i=0; i
{
q=0;
for (int j=1; j
for (int k=1; k
if (j!=k)
if (mass[i][j]==mass[i][k]) q=k;
if (q!=0)
{
for ( j=1; j
if (j>=q) mass[i][j]=mass[i][j+1];
mass[i][0]=mass[i][0]-1;
}
}
}
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
void CKursovojDlg::peremf(int st1)
{
int k;
masskol=2;
for (int i=2; i
{
k=umnf[i][0];
for (int s=1; s
for (int ki=0; ki
for (int j=0; j
mass[masskol*s+ki][j]=mass[ki][j];
for (s=0; s
for (int j=0; j
if (mass[masskol*s+j][0]>0)
{
mass[masskol*s+j][0]=mass[masskol*s+j][0]+1;
mass[masskol*s+j][mass[masskol*s+j][0]]=umnf[i][s+1];
}
k=masskol;
masskol=1000;
perre();
ud();
masskol=k*umnf[i][0];
}
masskol=1000;
perre();
ud();
}
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
void CKursovojDlg::perem(int st1)
{
int k=0;
masskol=0;
for (int i=0; i
if (mass[i][0]!=0) masskol++;
for ( i=0; i
for (int j=0; j
mass[masskol+i][j]=mass[i][j];
for (int j=0; j
{
if (mass[j][0]>0){
mass[j][0]=mass[j][0]+1;
mass[j][mass[j][0]]=umn[st1].x1;}
if (mass[masskol+j][0]>0){
mass[masskol+j][0]=mass[masskol+j][0]+1;
mass[masskol+j][mass[masskol+j][0]]=umn[st1].x2;}
}
perre();
ud();
}
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
void CKursovojDlg::provf(void)
{
int min,buf;
for (int u=0; u
for (int i=1; i
{
min=i;
for (int j=i+1; j
if (umnf[u][j]
if (i!=min)
{
buf= umnf[u][i];
umnf[u][i] = umnf[u][min];
umnf[u][min]= buf;
}
}
int k;
for (int i=1; i
for (int j=1; j
if (i!=j)
if (umnf[i][0]==umnf[j][0])
{
k=0;
for (int t=1; t
if(umnf[i][t]==umnf[j][t]) k++;
if (k==umnf[i][0]) umnf[j][0]=-1;
}
}
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
void CKursovojDlg::prov(void)
{
int k;
for (int i=1; i
for (int j=1; j
if (i!=j)
{
k=0;
if((umn[i].x1==umn[j].x1)&&(umn[i].x2==umn[j].x2)) umn[j].x1=-1;
if((umn[i].x2==umn[j].x1)&&(umn[i].x1==umn[j].x2)) umn[j].x1=-1;
}
}
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
void CKursovojDlg::raskr(void)
{
const int rad=15;
CClientDC dc(this);
//Создать новое перо
CPen MyNewPen;
MyNewPen.CreatePen(PS_SOLID, 1,RGB(0,0,0));
CBrush br;
br.CreateSolidBrush(RGB(0,200,200));
//Выбрать перо
CPen* pOriginalPen;
CBrush* pbr;
pOriginalPen=dc.SelectObject(&MyNewPen);
pbr=dc.SelectObject(&br);
//Нарисовать круг
SetBkMode(dc,TRANSPARENT);
int kp,nea;
char buf[3];
int pr[1000];
int p=rat;
rat++;
if (rat==rav+1) {rask=-1; rat=1;}
for (int i=0; i
if((mass[i][0]>0)&&(mass[i][1]>0)) if(((i>rask)&&(p!=rat))||(rat==rav))
{
pr[0]=0; p=rat; rask=i;
for (int t=1; t
{
nea=0;
for (int u=1; u
if (fff[mass[i][t]][u]!=0)
{
kp=0;
for (int y=1; y
if (pr[y]==u) kp=1;
if (kp==0) {
pr[0]++; pr[pr[0]]=u;
CRectMyRectangle(versh[u].x-rad,versh[u].y-rad,versh[u].x+rad,versh[u].y+rad);
dc.Ellipse(&MyRectangle);
itoa(u,buf,10);
if (u>9)
dc.TextOut(versh[u].x-8,versh[u].y-8,buf);
elsedc.TextOut(versh[u].x-4,versh[u].y-8,buf);}
}
br.DeleteObject();
br.CreateSolidBrush(RGB(rand(),rand(),rand()));
pbr=dc.SelectObject(&br);
}
}
UpdateData(TRUE);
m_l3.SetCurSel(m_l3.GetCount()-1-rav+rat);
}
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
void CKursovojDlg::k(void)
{
CString str;
char ch[5];
for (int i=1; i
for (int j=1; j
if (matsm[i][j]==1)
{
if (i
{
colvo++;
umn[colvo].x1=i;
umn[colvo].x2=j;
} else
{
colvo++;
umn[colvo].x1=j;
umn[colvo].x2=i;
}
}
for ( i=1; i
for (int j=1; j
mass[i][j]=0;
prov();
str="";
m_l3.ResetContent();
int nea=0;
for ( i=1; i
if (umn[i].x1!=-1)
{
nea=1;
str+="(x";
itoa(umn[i].x1,ch,10);
str+=ch;
str+="+x";
itoa(umn[i].x2,ch,10);
str+=ch;
str+=")";
if (str.GetLength()>40){m_l3.AddString(str);str="";nea=0;}
}
if (nea!=0) m_l3.AddString(str);
mass[0][0]=1;
mass[1][0]=1;
mass[0][1]=umn[1].x1;
mass[1][1]=umn[1].x2;
masskol=2;
for ( i=2; i
if (umn[i].x1>-1) perem(i);
ud();
str="";
int kp=0;
for ( i=0; i
if (mass[i][0]>0)
{
nea=1;
if (kp>0) str+="+";
kp++;
for (int j=1; j
if (mass[i][j]>0){str+=«x»;
itoa(mass[i][j],ch,10);
str+=ch;}
if (str.GetLength()>40){m_l3.AddString(str);str="";nea=0;}
}
if (nea!=0) m_l3.AddString(str);
for ( i=1; i
for (int j=1; j
fff[i][j]=0;
m_l2.ResetContent();
colf=0;
for ( i=0; i
if (mass[i][0]>0)
{
if (kolv!=mass[i][0])
{
colf++;
fff[colf][0]=0;
for (int t=1; t
{
nea=0;
for (int j=1; j
if((mass[i][j]>0)&&(mass[i][j]==t)) nea=1;
if (nea==0) { fff[colf][0]++;fff[colf][fff[colf][0]]=1;}
else { fff[colf][0]++;fff[colf][fff[colf][0]]=0;}
}
}
}
m_l2.ResetContent();
str="";
for ( i=1; i
{
for (int j=1; j
{
itoa(fff[j][i],ch,10);
str+=ch;
str+=" ";
}
m_l2.AddString(str);
str="";
}
for ( i=1; i
for (int j=1; j
mass[i][j]=0;
for ( i=1; i
for (int j=1; j
umnf[i][j]=0;
for ( i=1; i
for (int j=1; j
if (fff[i][j]!=0) {umnf[j][0]++;umnf[j][umnf[j][0]]=i;}
provf();
str="";
for ( i=1; i
if (umnf[i][0]>0)
{
nea=1;
str+="(";
kp=0;
for (int j=1; j
{
if (kp!=0) str+="+";
kp++;
str+=«F»;
itoa(umnf[i][j],ch,10);
str+=ch;
}
str+=")";
if (str.GetLength()>40){m_l3.AddString(str);str="";nea=0;}
}
masskol=0;
if (nea!=0) m_l3.AddString(str);
for (int j=1; j
if (umnf[1][j]!=0)
{
mass[masskol][0]=1;
mass[masskol][1]=umnf[1][j];
masskol++;
}
peremf(1);
str="";
kp=0;
for ( i=0; i
if (mass[i][0]>0)
{
nea=1;
if (kp>0) str+="+";
kp++;
for (int j=1; j
if (mass[i][j]>0){str+=«F»;
itoa(mass[i][j],ch,10);
str+=ch;}
if (str.GetLength()>40){m_l3.AddString(str);str="";nea=0;}
}
if (str[str.GetLength()-1]=='+')m_l3.AddString(«0»);
if (nea!=0) m_l3.AddString(str);
str="";
rav=0;
int pr[1000];
for ( i=0; i
if((mass[i][0]>0)&&(mass[i][1]>0))
{
for (int j=1; j
if (mass[i][j]>0){str+=«F»;
itoa(mass[i][j],ch,10);
str+=ch;}
str+="={";
pr[0]=0;
rav++;
for (int t=1; t
{
nea=0;
for (int u=1; u
if (fff[mass[i][t]][u]!=0)
{
kp=0;
for (int y=1; y
if (pr[y]==u) kp=1;
if (kp==0) {
pr[0]++; pr[pr[0]]=u;
if (nea>0) str+=",";
nea++;
str+=«x»;
itoa(u,ch,10);
str+=ch;}
}
str+=";";
}
str+="}";
m_l3.AddString(str);
str="";
}
rask=-1; rat=0; raskr();
}
//------------------------------------------------------------------------------------------
void CKursovojDlg::OnSysCommand(UINTnID, LPARAM lParam)
{
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
{
CAboutDlg dlgAbout;
dlgAbout.DoModal();
}
else
{
CDialog::OnSysCommand(nID, lParam);
}
}
// If you add a minimize button to yourdialog, you will need the code below
// to draw the icon. For MFCapplications using the document/view model,
// this is automatically done for you bythe framework.
void CKursovojDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // device context forpainting
SendMessage(WM_ICONERASEBKGND, (WPARAM)dc.GetSafeHdc(), 0);
// Center icon in client rectangle
int cxIcon =GetSystemMetrics(SM_CXICON);
int cyIcon =GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() — cxIcon + 1) / 2;
int y = (rect.Height() — cyIcon + 1) /2;
// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CDialog::OnPaint();
}
const int rad=15;
CClientDC dc(this);
//Создать новое перо
CPen MyNewPen;
MyNewPen.CreatePen(PS_SOLID, 1,RGB(0,0,0));
CBrush br;
br.CreateSolidBrush(RGB(200,200,200));
//Выбрать перо
CPen* pOriginalPen;
CBrush* pbr;
pOriginalPen=dc.SelectObject(&MyNewPen);
pbr=dc.SelectObject(&br);
//Нарисовать круг
SetBkMode(dc,TRANSPARENT);
for (int j=1; j
{
dc.MoveTo(versh[rebro[j].n].x,versh[rebro[j].n].y);
dc.LineTo(versh[rebro[j].k].x,versh[rebro[j].k].y);
}
for (int i=1; i
{
char buf[3];
CRectMyRectangle(versh[i].x-rad,versh[i].y-rad,versh[i].x+rad,versh[i].y+rad);
dc.Ellipse(&MyRectangle);
itoa(i,buf,10);
if (i>9)
dc.TextOut(versh[i].x-8,versh[i].y-8,buf);
elsedc.TextOut(versh[i].x-4,versh[i].y-8,buf);
}
if (rav!=0)
{
int k,l;
k=rask;
l=rat;
raskr();
rask=k;
rat=l;
}
}
// The system calls this to obtain thecursor to display while the user drags
// the minimized window.
HCURSOR CKursovojDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}
void CKursovojDlg::OnButton1()
{
// TODO: Add your control notificationhandler code here
UpdateData(TRUE);
m_nach.EnableWindow(false);
k();
m_r1.EnableWindow(true);
}
void CKursovojDlg::OnRadio1()
{
// TODO: Add your control notificationhandler code here
radio=1;
}
void CKursovojDlg::OnRadio2()
{
// TODO: Add your control notificationhandler code here
radio=2;
}
void CKursovojDlg::OnStatic1()
{
}
void CKursovojDlg::OnLButtonDown(UINTnFlags, CPoint point)
{
// TODO: Add your message handler codehere and/or call default
CDialog::OnLButtonDown(nFlags, point);
const int rad=15;
CClientDC dc(this);
//Создать новое перо
CPen MyNewPen;
MyNewPen.CreatePen(PS_SOLID, 1,RGB(0,0,0));
CBrush br;
br.CreateSolidBrush(RGB(200,200,200));
//Выбрать перо
CPen* pOriginalPen;
CBrush* pbr;
pOriginalPen=dc.SelectObject(&MyNewPen);
pbr=dc.SelectObject(&br);
CRectMyRectangle(point.x-rad,point.y-rad,point.x+rad,point.y+rad);
//Нарисовать круг
SetBkMode(dc,TRANSPARENT);
if((point.x>30)&&(point.x160)&&(point.y
if (radio==1)
{
char buf[3];
kolv++;
dc.Ellipse(&MyRectangle);
itoa(kolv,buf,10);
if (kolv>9)
dc.TextOut(point.x-8,point.y-8,buf);
elsedc.TextOut(point.x-4,point.y-8,buf);
versh[kolv].x=point.x;
versh[kolv].y=point.y;
}
if ((radio==2)&&(kolv>1))
{
for(int i=1; i
if((point.xversh[i].x-15)&&(point.yversh[i].y-15))
if (paint==0) { paint=1; kolreb++;rebro[kolreb].n=i;}
else if (i!=rebro[kolreb].n)
{
paint=0;
rebro[kolreb].k=i;
dc.MoveTo(versh[rebro[kolreb].n].x,versh[rebro[kolreb].n].y);
dc.LineTo(versh[rebro[kolreb].k].x,versh[rebro[kolreb].k].y);
Invalidate(TRUE);
}
}
}
void CKursovojDlg::OnButton2()
{
char ch[2];
CString str;
// TODO: Add your control notificationhandler code here
m_l1.ResetContent();
for (int i=0; i
for (int j=0; j
{
matsm[i][j]=0;
mass[i][j]=0;
fff[i][j]=0;
umnf[i][j]=0;
}
for ( i=1; i
{
for (int j=1; j
{
if (i==j) matsm[i][j]=0;
else
{
matsm[i][j]=0;
for (int t=1; t
if(((rebro[t].n==i)&&(rebro[t].k==j))||((rebro[t].n==j)&&(rebro[t].k==i)))
matsm[i][j]=1;
}
itoa(matsm[i][j],ch,10);
str+=ch;
str+=" ";
}
m_l1.AddString(str);
str="";
}
m_nach.EnableWindow(true);
}
void CKursovojDlg::OnButton3()
{
// TODO: Add your control notificationhandler code here
kolv=0;
kolreb=0;
rav=0;
for (int i=0; i
for (int j=0; j
{
//versh[1000];
//rebro[2000];
matsm[i][j]=0;
//umn[1000];
mass[i][j]=0;
fff[i][j]=0;
umnf[i][j]=0;
}
m_r1.EnableWindow(false);
Invalidate(TRUE);
}
void CKursovojDlg::OnButton4()
{
// TODO: Add your control notificationhandler code here
raskr();
}
void CKursovojDlg::OnButton5()
{
// TODO: Add your control notificationhandler code here
CKursovojDlg::OnOK();
}
void CAboutDlg::OnOK()
{
// TODO: Add extra validation here
CDialog::OnOK();
}
void CKursovojDlg::OnButton6()
{
// TODO: Add your control notificationhandler code here
CAboutDlg M;
M.DoModal();
}