Алгоритм раскраски графа (точный) (стр. 2 из 4)
Множество вершин 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.
Программа нахождения максимально полного подграфа в произвольном графе реализована на языке VisualC. Программа имеет имя diskretka.exe
Программа содержит около 705 строк, исполняемый код программы (файл diskretka.exe) занимает 192 Кбайт оперативной памяти и примерно столько же на диске. Исходный текст программы на языке VisualC (файл diskretka.cpp) занимает 15.8 Кбайт памяти на диске.
В среде VisualC команда File-OpenWorkspace-diskretka.dsw
Запуск на выполнение – Ctrl+F5
Программа предназначена для нахождения максимально полного подграфа в произвольном графе.
Программа выполняет следующие функции:
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.6 Решение контрольных примеров
Пример 1:Случай, когда имеется несколько МПП в данном графе.
Найден первый МПП (выделен красным цветом).
Найден второй МПП (также выделен красным цветом).
Пример 2:Граф с одним МПП.
Найден максимально полный подграф(на рисунке красным цветом)
Пример 3: Граф, состоящий из нескольких компонент.
На основе трех контрольных примеров, мы получили верные результаты, что позволяет нам сделать вывод о правильной реализации алгоритма программы.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Методическое пособие по дискретной математике
2. Библиотека MSDN
3. Яблонский С.В. «Введение в дискретную математику»
4. Новиков Ф.А. «Дискретная математика для программиста»
Текст программы
// kursovojDlg.cpp : implementationfile
//
#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)