Курсовая работа: Программа решения задачи о графах
👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Федеральное государственное образовательное учреждение
высшего профессионального образования
"Саровский государственный физико-технический институт"
ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ
Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. Эта теория тесно связана также со многими разделами математики, среди которых — теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Достоверно и то, что теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем, достойных внимания самых искушенных математиков.
Граф G состоит из конечного непустого множества V, содержащего р вершин *), и заданного множества X, содержащего q неупорядоченных пар различных вершин из V. Каждую пару *= {ut v} вершин в X называют ребром графа G и говорят, что х соединяет uhv. Мы будем писать x=uv и говорить, что и v — смежные вершины (иногда это обозначается uadjv); вершина и ребро х инцидентны, так же как v и х. Если два различных ребра хну инцидентны одной и той же вершине, то они называются смежными. Граф с р вершинами и q ребрами называется (pt ф-графом. A,0)-граф называется тривиальным. Граф полностью определяется или его смежностями, или его инциденциями. Указанную информацию о графе удобно представлять в матричной форме. Действительно, с данным графом, помеченым соответствующим образом, связаны несколько матриц, в том числе матрица смежностей, матрица инциденций, матрица циклов и матрица коциклов. Часто эти матрицы удается использовать при выявлении определенных свойств графа. Классическим результатом о графах и матрицах является матричная теорема о деревьях, в которой дается число остовов любого помеченного графа. В данной главе рассматриваются также матроиды, связанные с матрицами циклов и матрицами коциклов.
Матрицей смежностей A = ||а(i,j)|| помеченного графа G с р вершинами называется (рхр)-матрица, в которой а(i,j)=\9 если вершина vt смежна с uj9 и а(i,j)~0 в противном случае. Таким образом, существует взаимно однозначное соответствие между помеченными графами с р вершинами и симметрическими бинарными (рхр)т матрицами с нулями на диагонали.
1. Матрица смежностей инвариантного и полного графа
2. Составление матрицы смежностей инвариантного графа
3. Составление матрицы смежностей полного графа
Матрицей смежностей A = ||а(i,j)|| для некоторого помеченного графа G с р вершинами называется (рхр)-матрица, в которой а(i,j)=1 если вершина v i
смежна с v j
и а(i,j)=0 в противном случае. Таким образом, существует взаимно однозначное соответствие между помеченными графами с р вершинами и симметрическими бинарными (рхр) – матрицами с нулями на диагонали.
Рисунок 1 Помеченный граф и его матрица смежностей
Матрицей смежностей B = ||b(i,j)|| для инварианта помеченного графа G с р вершинами называется (рхр)-матрица, в которой b(i,j)=1 если a(i,j)=0 и b(i,j)=0 в противном случае.
Рисунок 2 Инвариант помеченного граф и его матрица смежностей
Матрицей смежностей C = ||c(i,j)|| для полного графа G с р вершинами называется (рхр)-матрица, в которой с(i,j)=0 если i=j и c(i,j)=1 в противном случае.
Рисунок 3 Полный граф и его матрица смежностей
Курсовая работа выполнена с помощью программы Microsoft VisualC++ 6.0, одной из наиболее передовых, мощных и современных сред разработки Windows-приложений с богатым инструментарием разработки приложений. Средства работы с контекстом устройства позволяет быстро справиться с задачей и выдать графическое отображение результатов.
После запуска программы, программа ищет файл с описанием графа Graph.dat
Далее выбираются следующие пиктограммы окна
1. Отображение графа по его матрице смежностей
6. Перестраивает исходный граф в полный граф
Теперь выберем последнюю пиктограмму
В результате выполнения работы был изучен алгоритм решения задачи поиска инвариантного и полного графа. На основе алгоритма реализована программа с графическим интерфейсом пользователя. Также реализован удобный редактор графа и вывод полученных результатов в простой и понятной форме.
- Холзенер С.
X71 VisualC++ 6: Учебный курс – СПб: Питер, 2001 – 576 с: ил.
- Дж. Макконнел. Анализ алгоритмов. Вводный курс – Москва: Техносфера, 2002 – 304 с.
- Тимофеев В. В.С++ как он есть. Самоучитель. – М.: ООО ≪Бином-Пресс≫,2004 г. – 366с.:ил.
// Graph.h: interface for the CGraph class.//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_GRAPH_H__8C8860CB_4D3F_4F0B_9B81_66289DCC2354__INCLUDED_)
#define AFX_GRAPH_H__8C8860CB_4D3F_4F0B_9B81_66289DCC2354__INCLUDED_
CGraphV() : pt(CPoint(0,0)), Title(_T("")){};
CGraphV& operator = (const CGraphV& gV){
CGraphE() : state(FALSE),len(0.0){};
CGraphE& operator = (const CGraphE& gE){
void SetV(int m_Vpos, CPoint pt, CString m_Title);
void SetE(int i, int j, double m_len);
void SetRand(int A_space, int B_space, int m_Len, double m_p);
void Show(CDC *pDC, COLORREF c = RGB(0,0,0));
void SetCurV(int m_cur) { curV = m_cur;};
void AddV(CPoint pt, CString m_Title);
CGraph& operator = (const CGraph& g){
for(i=0;i= m_p) SetE(i / COUNT, i % COUNT, m_Len*rand()/RAND_MAX);
else {E[i].state = FALSE;E[i].len = 0.0;}
void CGraph::Show(CDC *pDC, COLORREF c)
int i=0, j=0, fn = V_count*V_count;
pDC->Ellipse(V[i].pt.x-sz,V[i].pt.y-sz,V[i].pt.x+sz,V[i].pt.y+sz);
pDC->TextOut(V[i].pt.x,V[i].pt.y,V[i].Title);
pt1 = V[i/V_count].pt; pt2 = V[i%V_count].pt;
//pDC->TextOut((pt1.x+pt2.x)/2,(pt1.y+pt2.y)/2,str);
fwrite(&V_count,sizeof(V_count),1,file);
fwrite(&V[i].pt.x,sizeof(V[i].pt.x),1,file);
fwrite(&V[i].pt.y,sizeof(V[i].pt.y),1,file); len = V[i].Title.GetLength();
fwrite(&E[i].state,sizeof(E[i].state),1,file);
fwrite(&E[i].len,sizeof(E[i].len),1,file);
fread(&V[i].pt.x,sizeof(V[i].pt.x),1,file);
fread(&V[i].pt.y,sizeof(V[i].pt.y),1,file);
fread(&buf[0],len,1,file); buf[len] = 0;
fread(&E[i].state,sizeof(E[i].state),1,file);
fread(&E[i].len,sizeof(E[i].len),1,file);
void CGraph::MoveV(int m_x, int m_y)
if(j != indexV) {g.E[i1*(V_count-1)+j1] = E[i*V_count+j];j1++;}
void CGraph::AddV(CPoint pt, CString m_Title)
CGraphV *V1 = new CGraphV[V_count+1];
CGraphE *E1 = new CGraphE[(V_count+1)*(V_count+1)];
for(i=0;iIsKindOf(RUNTIME_CLASS(CKursovikMinDoc)));
return (CKursovikMinDoc*)m_pDocument;
/////////////////////////////////////////////////////////////////////////////
// CKursovikMinView message handlers
void CKursovikMinView::OnFileSave()
// TODO: Add your command handler code here
CFileDialog dlg(FALSE,"dat","*.dat");
void CKursovikMinView::OnFileOpen()
// TODO: Add your command handler code here
CFileDialog dlg(TRUE,"dat","*.dat");
void CKursovikMinView::OnLButtonUp(UINT nFlags, CPoint point)
// TODO: Add your message handler code here and/or call default
CScrollView::OnLButtonUp(nFlags, point);
void CKursovikMinView::OnMouseMove(UINT nFlags, CPoint point)
// TODO: Add your message handler code here and/or call default
CScrollView::OnMouseMove(nFlags, point);
void CKursovikMinView::OnRButtonUp(UINT nFlags, CPoint point)
// TODO: Add your message handler code here and/or call default
if((fabs(m_graph.V[i].pt.x-point.x) < 10) && (fabs(m_graph.V[i].pt.y-point.y) < 10))
CScrollView::OnRButtonUp(nFlags, point);
void CKursovikMinView::OnKeyUp(UINT nChar, UINT nRepCnt, UINT nFlags)
// TODO: Add your message handler code here and/or call default
//default: MessageBox("key = "+nChar); break;
CScrollView::OnKeyUp(nChar, nRepCnt, nFlags);
void CKursovikMinView::OnEditDialog()
// TODO: Add your command handler code here
void CKursovikMinView::OnEditMakefullgraph()
// TODO: Add your command handler code here
int i=0,j=0,Vs = m_graph.V_count*m_graph.V_count;
void CKursovikMinView::OnEditTestOnFull()
if(i != j && (!m_graph.E[i*Vs+j].state || !m_graph.E[j*Vs+i].state)) {IsFull = TRUE; break;}
if(!IsFull) MessageBox("Äàííûé ãðàô - ïîëíûé","Test results",MB_OK);
str.Format("Äàííûé ãðàô - íå ÿâëÿåòñÿ ïîëíûì\nÍåò ñîåäèíåíèÿ âåðøèí (%i,%i)",i,j);
MessageBox(str,"Test results",MB_OK);
// TODO: Add your command handler code here
void CKursovikMinView::OnShowGraph()
// TODO: Add your command handler code here
void CKursovikMinView::OnShowGraphs()
// TODO: Add your command handler code here
void CKursovikMinView::OnShowNgraph()
// TODO: Add your command handler code here
Название: Программа решения задачи о графах
Раздел: Рефераты по информатике
Тип: курсовая работа
Добавлен 02:05:31 05 декабря 2010 Похожие работы
Просмотров: 14
Комментариев: 15
Оценило: 3 человек
Средний балл: 5
Оценка: неизвестно Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Курсовая работа: Программа решения задачи о графах
Реферат: Сероквель – атипичный нейролептик. Скачать бесплатно и без регистрации
Дипломная работа: Анализ качества работы эндоскопического кабинета
Сочинение Про Выбор Профессии
Реферат: Налоги в США 2
Осень Лучшее Время Года Сочинение
Реферат: Анализ бюджета Кинель-Черкасского района
Реферат: World War Ii 3 Essay Research Paper
Контрольная работа по теме Здоровый образ жизни, учет индивидуальных и возрастных факторов в его реализации
Дипломная работа по теме Электроснабжение деревообрабатывающего предприятия
Сочинение На Тему Изменчивость Современного Мира
Курсовая работа по теме Вплив середньовічних університетів на формування середньовічної науки
Чему Учат Главные Герои Сказки Мини Сочинение
Реферат по теме Исполнительные департаменты в США
Контрольная Работа 10 Класс Биболетова
Сочинение Про Осень По Русскому
Реферат по теме Технология создания дизайна
Мини Сочинение Былинные Богатыри
Мәдениет Морфологиясы Эссе
Реферат по теме Жизнь и творчество Николая Константиновича Рериха
Чацкий И Молчание Сочинение
Дипломная работа: Управление оборотными средствами предприятия на примере ООО Радуга-Сервис
Реферат: Sweden
Реферат: Проектирование информационных систем на базе MySQL и Internet