Алгоритм раскраски графа (точный) - Математика курсовая работа
Главная
Математика
Алгоритм раскраски графа (точный)
Алгоритм, использующий метод Магу-Вейссмана. Общие сведения, описание, вызов и загрузка, функциональное назначение и программный код программы. Описание логической структуры и инструкция пользователю, решение контрольных примеров раскраски графа.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
На тему: “Алгоритм раскраски графа (точный)"
В настоящей пояснительной записке приведено описание алгоритма раскраски графа (точный). Изложены вопросы проектирования структуры программы и данных. Разработаны схемы алгоритмов решения задачи. Разработана и отлажена программа, реализующая представленные алгоритмы на языке Visual C. Представлены результаты решения контрольных примеров, выполненные с помощью разработанной программы на ПК Intel core 2 Duo.
Пояснительная записка содержит 34 страницы, 5 рисунков, 4 использованных источника, приложения.
Графом,в общем случае, называются два множества, находящиеся между собой в некотором отношении: 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) называется максимальным внутренне устойчивым подмножеством (МВУП), или независимым подмножеством (НП), если добавление к нему любой вершины x j еХ делает его не внутренне устойчивым. Подмножество Y i будет определяться как х 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 ; X i X j =; i,jI={1,2,..,l}, (1)
таких, что внутри каждого подмножества X i не должно содержаться смежных вершин (X i -внутренне устойчивые подмножества).
Если каждому подмножеству х i поставить в соответствие определенный цвет, то вершины внутри этого подмножества можно окрасить в один цвет, вершины другого подмножества Х j - в другой цвет и т.д. до раскраски всех подмножеств.
В этом случае граф называется 1-раскрашиваемым. Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хроматическим числом (G).
Очевидно, что полный граф K n можно раскрасить только n цветами, следовательно, (К n ) =n. Для связного графа G= (Х,U) с числом ребер m, где (n-1)LoadIcon(IDR_MAINFRAME);
void CKursovojDlg::DoDataExchange(CDataExchange* pDX)
DDX_Control(pDX, IDC_BUTTON4, m_r1);
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);
BEGIN_MESSAGE_MAP(CKursovojDlg, CDialog)
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_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)
/////////////////////////////////////////////////////////////////////////////
// Add "About..." menu item to system menu.
// IDM_ABOUTBOX must be in the system command range.
ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
CMenu* pSysMenu = GetSystemMenu(FALSE);
strAboutMenu.LoadString(IDS_ABOUTBOX);
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
//------------------------------------------------------------------------------------------
for (int j=i+1 ; j0))
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
mass[masskol*s+j][0]=mass[masskol*s+j][0]+1;
mass[masskol*s+j][mass[masskol*s+j][0]]=umnf[i][s+1];
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
mass[masskol+j][0]=mass[masskol+j][0]+1;
mass[masskol+j][mass[masskol+j][0]]=umn[st1].x2;}
//------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------
for (int j=i+1 ; j0)&&(mass[i][1]>0)) if (((i>rask)&&(p!=rat))||(rat==rav))
for (int t=1; t40) {m_l3.AddString(str);str="";nea=0;}
for (int j=1; j40) {m_l3.AddString(str);str="";nea=0;}
for (int j=1; j0)&&(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;}
if (fff[i][j]!=0) {umnf[j][0]++; umnf[j][umnf[j][0]]=i;}
for (int j=1 ; j40) {m_l3.AddString(str);str="";nea=0;}
for (int j=1 ; j40) {m_l3.AddString(str);str="";nea=0;}
if (str[str.GetLength()-1]=='+') m_l3.AddString("0");
if ((mass[i][0]>0)&&(mass[i][1]>0))
for (int j=1; j30)&&(point.x<540)&&(point.y>160)&&(point.y<565))
dc.TextOut(point.x-8,point.y-8,buf);
else dc.TextOut(point.x-4,point.y-8,buf);
if ((point.xversh[i].x-15)&&(point.yversh[i].y-15))
if (paint==0) { paint=1; kolreb++; rebro[kolreb].n=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);
// TODO: Add your control notification handler code here
if (((rebro[t].n==i)&&(rebro[t].k==j))||((rebro[t].n==j)&&(rebro[t].k==i)))
// TODO: Add your control notification handler code here
// TODO: Add your control notification handler code here
// TODO: Add your control notification handler code here
// TODO: Add your control notification handler code here
Описание заданного графа множествами вершин 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
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Алгоритм раскраски графа (точный) курсовая работа. Математика.
Коммерческая деятельность на рынке лесопродукции
Любое Сочинение На Тему Интересная Встреча
Курсовая работа по теме Содержание, признаки и сущность государственного принуждения
Банк Рефератов Химии
Полугодовая Контрольная Работа 9 Класс
Реферат: Ве должно быть
Курсовая работа по теме Разработка управленческого решения для улучшения экономического положения ООО 'Командор'
Контрольная работа: Теория корпоративного управления
Реферат На Тему Восточный Крым В Творчестве Максимилиана Волошина
Биография Стародума Сочинение 8 Класс
Курсовая Работа На Тему Безработица В России
Магическое в романе М. Булгакова "Мастер и Маргарита"
Курсовая работа по теме Механизмы компрессора
Социальная Политика Государства В Российской Федерации Курсовая
Реферат По Технологии Окошке
Реферат На Тему Устройства Ввода И Вывода Информации
Доклад: Га дамер Ганс-Георг
Вступительная Контрольная Работа 5 Класс
Предпосылки И Причины Первой Мировой Войны Реферат
Реферат: Технология исследовательской деятельности
Управление юстиции Брестского облисполкома - Бухгалтерский учет и аудит отчет по практике
Берия Л.П. - нарком внутренних дел - История и исторические личности реферат
Роль права собственности в предпринимательской деятельности - Государство и право курсовая работа