Алгоритм раскраски графа (точный)
Алгоритм, использующий метод Магу-Вейссмана. Общие сведения, описание, вызов и загрузка, функциональное назначение и программный код программы. Описание логической структуры и инструкция пользователю, решение контрольных примеров раскраски графа.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 20.12.2009 |
| Размер файла | 350,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
45
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Кафедра САПР
Пояснительная записка
к курсовому проекту по дисциплине
“Дискретная математика”
На тему: “Алгоритм раскраски графа (точный)"
Выполнил: студентка гр. 06ВА-1
Молоткова Е.
Принял: к.т.н., доцент Валько А.Ф.
Пенза 2007г.
СОДЕРЖАНИЕ
- Аннотация
- 1. Теоретическая часть
- 2. Алгоритм, использующий метод Магу - Вейссмана
- 2.2 Разработанный алгоритм
- 3. Описание программы
- 3.1 Общие сведения
- 3.2 Вызов и загрузка
- 3.3 Функциональное назначение
- 3.4 Описание логической структуры программы
- 3.5 Инструкция пользователю
- 3.6 Решение контрольных примеров
- Заключение
- СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
- ПРИЛОЖЕНИЕ
Аннотация
В настоящей пояснительной записке приведено описание алгоритма раскраски графа (точный). Изложены вопросы проектирования структуры программы и данных. Разработаны схемы алгоритмов решения задачи. Разработана и отлажена программа, реализующая представленные алгоритмы на языке Visual C. Представлены результаты решения контрольных примеров, выполненные с помощью разработанной программы на ПК Intel core 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; XiXj=; i,jI={1,2,..,l}, (1)
таких, что внутри каждого подмножества Xi не должно содержаться смежных вершин (Xi-внутренне устойчивые подмножества).
Если каждому подмножеству хi поставить в соответствие определенный цвет, то вершины внутри этого подмножества можно окрасить в один цвет, вершины другого подмножества Хj - в другой цвет и т.д. до раскраски всех подмножеств.
В этом случае граф называется 1-раскрашиваемым. Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хроматическим числом (G).
Очевидно, что полный граф Kn можно раскрасить только n цветами, следовательно, (Кn) =n. Для связного графа G= (Х,U) с числом ребер m, где (n-1)<m<n(n-1)/2 верхняя оценка хроматического числа (G) определяется как
(G)
Нижней оценкой (G) является число вершин в наибольшем полном подграфе графа G,т.е. его плотность. Известно утверждение, что для любого графа (G)<1+max (xi),где хi Х, iI={1,2,...,n},(xi)- локальная степень вершины хi.Приводятся также следующие оценки:
(G)n2/(n2-m2); (G)n+1-(Gд),
где Gд= К\G ( дополнение графа G до полного К).
Задача раскраски вершин (поиска хроматического числа) графа может быть решена точными или приближенными алгоритмами.
К точным алгоритмам относятся: алгоритм, использующий метод Магу - Вейсмана; алгоритмы, основанные на рассмотрении максимальных r - подграфов и алгоритмы на основе методов целочисленного линейного программирования.
К приближенный алгоритмам раскраски относятся алгоритмы, основанные на упорядочивании множества вершин графов , последовательном удалении из графа вершин, имеющих максимальную степень и на анализе подмножеств смежности вершин.
2.1 Точные алгоритмы
Алгоритм, использующий метод Магу - Вейссмана
1. Для графа G (Х,U) построим семейство МВУП F={Fj}, где j= 1,... ,1; 1 - число МВУП.
1. 2. Составим матрицу
Cij=
3. Для. каждой вершины графа G =(Х,U) по матрице С находим суммы тех FjF, в которые она входит, и записываем произведение этих сумм.
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 Х по матрице С составим суммы тех FjF, в которые оно входит и запишем произведение этих сумм
ПС=(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 Вызов и загрузка
В среде Visual C команда 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 virtual function overrides
//{{AFX_VIRTUAL(CAboutDlg)
protected:
virtual void DoDataExchange(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
}
void CAboutDlg::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 a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CKursovojDlg::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 to system menu.
// IDM_ABOUTBOX must be in the system command range.
ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
ASSERT(IDM_ABOUTBOX < 0xF000);
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. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE);// Set big icon
SetIcon(m_hIcon, FALSE);// Set small icon
// TODO: Add extra initialization here
return TRUE; // return TRUE unless you set the focus to a control
}
//------------------------------------------------------------------------------------------
void CKursovojDlg::ud(void)
{
int q;
int min,buf;
for (int u=0 ; u<masskol*2; u++)
for (int i=1 ; i<mass[u][0] ; i++)
{
min=i;
for (int j=i+1 ; j<mass[u][0]+1 ; j++)
if (mass[u][j]<mass[u][min]) min=j;
if (i!=min)
{
buf= mass[u][i];
mass[u][i] = mass[u][min];
mass[u][min]= buf;
}
}
for (int i=0 ; i<masskol*2 ; i++)
for (int y=0 ; y<masskol*2 ; y++)
if (i!=y)
{
q=0;
if ((mass[i][0]==mass[y][0])&&(mass[i][0]>0))
for (int k=1; k<mass[y][0]+1; k++)
if (mass[i][k]==mass[y][k]) q++;
if (q==mass[y][0])
{
mass[y][0]=-1;
}
}
for (i=0 ; i<masskol*2 ; i++)
for (int y=0 ; y<masskol*2 ; y++)
if (i!=y)
{
q=0;
if ((mass[i][0]+1)==mass[y][0])
for (int j=1; j<mass[i][0]+1; j++)
for (int k=1; k<mass[y][0]+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<masskol*2 ; i++)
{
q=0;
for (int j=1; j<mass[i][0]+1; j++)
for (int k=1; k<mass[i][0]+1; k++)
if (j!=k)
if (mass[i][j]==mass[i][k]) q=k;
if (q!=0)
{
for ( j=1; j<mass[i][0]+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<kolv+1 ; i++)
{
k=umnf[i][0];
for (int s=1; s<k; s++)
for (int ki=0 ; ki<masskol ; ki++)
for (int j=0; j<100; j++)
mass[masskol*s+ki][j]=mass[ki][j];
for (s=0 ; s<k; s++)
for (int j=0; j<masskol; 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<1000 ; i++)
if (mass[i][0]!=0) masskol++;
for ( i=0 ; i<masskol ; i++)
for (int j=0; j<100; j++)
mass[masskol+i][j]=mass[i][j];
for (int j=0 ; j<masskol ; 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<kolv+1; u++)
for (int i=1 ; i<umnf[u][0] ; i++)
{
min=i;
for (int j=i+1 ; j<umnf[u][0]+1 ; j++)
if (umnf[u][j]<umnf[u][min]) min=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<kolv+1 ; i++)
for (int j=1; j<kolv+1 ; j++)
if (i!=j)
if (umnf[i][0]==umnf[j][0])
{
k=0;
for (int t=1 ; t<umnf[i][0]+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<colvo+1 ; i++)
for (int j=1; j<colvo+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<1000 ; 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<mass[i][0]+1 ; t++)
{
nea=0;
for (int u=1; u<fff[mass[i][t]][0]+1; u++)
if (fff[mass[i][t]][u]!=0)
{
kp=0;
for (int y=1; y<pr[0]+1; y++)
if (pr[y]==u) kp=1;
if (kp==0) {
pr[0]++; pr[pr[0]]=u;
CRect MyRectangle(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);
else dc.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<kolv+1 ; i++)
for (int j=1; j<kolv+1 ; j++)
if (matsm[i][j]==1)
{
if (i<j)
{
colvo++;
umn[colvo].x1=i;
umn[colvo].x2=j;
} else
{
colvo++;
umn[colvo].x1=j;
umn[colvo].x2=i;
}
}
for ( i=1; i<1000 ; i++)
for (int j=1; j<100 ; j++)
mass[i][j]=0;
prov();
str="";
m_l3.ResetContent();
int nea=0;
for ( i=1; i<colvo+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<colvo+1; i++)
if (umn[i].x1>-1) perem(i);
ud();
str="";
int kp=0;
for ( i=0; i<1000 ; i++)
if (mass[i][0]>0)
{
nea=1;
if (kp>0) str+="+";
kp++;
for (int j=1; j<mass[i][0]+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<1000 ; i++)
for (int j=1; j<100 ; j++)
fff[i][j]=0;
m_l2.ResetContent();
colf=0;
for ( i=0; i<1000 ; i++)
if (mass[i][0]>0)
{
if (kolv!=mass[i][0])
{
colf++;
fff[colf][0]=0;
for (int t=1; t<kolv+1 ; t++)
{
nea=0;
for (int j=1; j<mass[i][0]+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<fff[1][0]+1 ; i++)
{
for (int j=1 ; j<colf+1; j++)
{
itoa(fff[j][i],ch,10);
str+=ch;
str+=" ";
}
m_l2.AddString(str);
str="";
}
for ( i=1; i<1000 ; i++)
for (int j=1; j<100 ; j++)
mass[i][j]=0;
for ( i=1; i<1000 ; i++)
for (int j=1; j<100 ; j++)
umnf[i][j]=0;
for ( i=1; i<colf+1; i++)
for (int j=1; j<fff[i][0]+1; j++)
if (fff[i][j]!=0) {umnf[j][0]++; umnf[j][umnf[j][0]]=i;}
provf();
str="";
for ( i=1 ; i<kolv+1 ; i++)
if (umnf[i][0]>0)
{
nea=1;
str+="(";
kp=0;
for (int j=1 ; j<umnf[i][0]+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<umnf[1][0]+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<1000 ; i++)
if (mass[i][0]>0)
{
nea=1;
if (kp>0) str+="+";
kp++;
for (int j=1; j<mass[i][0]+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<1000 ; i++)
if ((mass[i][0]>0)&&(mass[i][1]>0))
{
for (int j=1; j<mass[i][0]+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<mass[i][0]+1 ; t++)
{
nea=0;
for (int u=1; u<fff[mass[i][t]][0]+1; u++)
if (fff[mass[i][t]][u]!=0)
{
kp=0;
for (int y=1; y<pr[0]+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(UINT nID, LPARAM lParam)
{
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
{
CAboutDlg dlgAbout;
dlgAbout.DoModal();
}
else
{
CDialog::OnSysCommand(nID, lParam);
}
}
// If you add a minimize button to your dialog, you will need the code below
// to draw the icon. For MFC applications using the document/view model,
// this is automatically done for you by the framework.
void CKursovojDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // device context for painting
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<kolreb+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<kolv+1; i++)
{
char buf[3];
CRect MyRectangle(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);
else dc.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 the cursor to display while the user drags
// the minimized window.
HCURSOR CKursovojDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}
void CKursovojDlg::OnButton1()
{
// TODO: Add your control notification handler code here
UpdateData(TRUE);
m_nach.EnableWindow(false);
k();
m_r1.EnableWindow(true);
}
void CKursovojDlg::OnRadio1()
{
// TODO: Add your control notification handler code here
radio=1;
}
void CKursovojDlg::OnRadio2()
{
// TODO: Add your control notification handler code here
radio=2;
}
void CKursovojDlg::OnStatic1()
{
}
void CKursovojDlg::OnLButtonDown(UINT nFlags, CPoint point)
{
// TODO: Add your message handler code here 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);
CRect MyRectangle(point.x-rad,point.y-rad,point.x+rad,point.y+rad);
//Нарисовать круг
SetBkMode(dc,TRANSPARENT);
if ((point.x>30)&&(point.x<540)&&(point.y>160)&&(point.y<565))
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);
else dc.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<kolv+1 ; i++)
if ((point.x<versh[i].x+15)&&(point.x>versh[i].x-15)&&(point.y<versh[i].y+15)&&(point.y>versh[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 notification handler code here
m_l1.ResetContent();
for (int i=0 ; i<1000; i++)
for (int j=0 ; j<100; j++)
{
matsm[i][j]=0;
mass[i][j]=0;
fff[i][j]=0;
umnf[i][j]=0;
}
for ( i=1 ; i<kolv+1 ; i++)
{
for (int j=1 ; j<kolv+1 ; j++)
{
if (i==j) matsm[i][j]=0;
else
{
matsm[i][j]=0;
for (int t=1; t<kolreb+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 notification handler code here
kolv=0;
kolreb=0;
rav=0;
for (int i=0 ; i<1001; i++)
for (int j=0 ; j<101; 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 notification handler code here
raskr();
}
void CKursovojDlg::OnButton5()
{
// TODO: Add your control notification handler code here
CKursovojDlg::OnOK();
}
void CAboutDlg::OnOK()
{
// TODO: Add extra validation here
CDialog::OnOK();
}
void CKursovojDlg::OnButton6()
{
// TODO: Add your control notification handler code here
CAboutDlg M;
M.DoModal();
}
Подобные документы
Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Алгоритм построения минимального остовного дерева. Последовательность выполнения алгоритма Прима, его содержание и назначение. Процедура рисования графа. Порядок составления и тестирования программы, ее интерфейс, реализация и правила эксплуатации.
курсовая работа [225,0 K], добавлен 30.04.2011Алгоритм перехода к графическому представлению для неориентированного графа. Количество вершин неориентированного графа. Чтение из матрицы смежностей. Связи между вершинами в матрице. Задание координат вершин в зависимости от количества секторов.
лабораторная работа [34,0 K], добавлен 29.04.2011Применение интервальных графов. Алгоритмы распознавания интервальных графов: поиск в ширину, поиск в ширину с дополнительной сортировкой, лексикографический поиск в ширину, алгоритм "трех махов". Программа задания единичного интервального графа.
курсовая работа [1,5 M], добавлен 10.02.2017Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Понятие и внутренняя структура графа, его применение и матричное представление (матрица инциденций, разрезов, цикломатическая, Кирхгофа). Специальные свойства и признаки графов, решение оптимизационных задач. Венгерский алгоритм, матричная интерпретация.
курсовая работа [664,6 K], добавлен 24.12.2013Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Остовное дерево связного неориентированного графа. Алгоритм создания остовного дерева, его нахождение. Сущность и главные особенности алгоритма Крускала. Порядок построения алгоритма Прима, вершина наименьшего веса. Промежуточная структура данных.
презентация [140,8 K], добавлен 16.09.2013Понятие матрицы достижимости и связности. Операция удаления вершины из графа. Алгоритм выделения компонент сильной связности. Разработка и листинг программы на языке Turbo Pascal, осуществляющей вычисление матрицы достижимости по заданному алгоритму.
курсовая работа [584,3 K], добавлен 26.04.2011Понятия и определения орграфа и неориентированного графа, методы решения. Неориентированные и ориентированные деревья. Подробное описание алгоритмов нахождения кратчайших путей в графе: мультиграф, псевдограф. Матрица достижимостей и контрдостижимостей.
курсовая работа [251,0 K], добавлен 16.01.2012
