Программа решения задачи о графах

Федеральное государственное образовательное учреждение

высшего профессионального образования

"Саровский государственный физико-технический институт"

Экономико-математический факультет

пояснительная записка

к курсовой работе

На тему:

Программа решения задачи о графах

СТУДЕНТ (группа ИС-45Д)

РУКОВОДИТЕЛЬ Беляев С.П.

г. Саров2008 г

Оглавление

ВВЕДЕНИЕ

ПОЛНЫЙ ГРАФ. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Исходные параметры

Матрица смежностей

Исходные параметры

Этапы построения модели

РЕШЕНИЕ ЗАДАЧИ О ГРАФАХ

ОБОСНОВАНИЕ ВЫБОРА ПРОГРАММНЫХ СРЕДСТВ

ОПИСАНИЕ ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯ

КОНТРОЛЬНЫЙ ПРИМЕР

СПИСОК ЛИТЕРАТУРЫ

ТЕКСТ ПРОГРАММЫ

ВВЕДЕНИЕ

Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. Эта теория тесно связана также со многими разделами математики, среди которых — теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Достоверно и то, что теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем, достойных внимания самых искушенных математиков.

ЗАКЛЮЧЕНИЕ

В результате выполнения работы был изучен алгоритм решения задачи поиска инвариантного и полного графа. На основе алгоритма реализована программа с графическим интерфейсом пользователя. Также реализован удобный редактор графа и вывод полученных результатов в простой и понятной форме.

СПИСОК ЛИТЕРАТУРЫ

- Холзенер С. X71 VisualC++ 6: Учебный курс – СПб: Питер, 2001 – 576 с: ил.

- Дж. Макконнел. Анализ алгоритмов. Вводный курс – Москва: Техносфера, 2002 – 304 с.

- Тимофеев В. В.С++ как он есть. Самоучитель. – М.: ООО ≪Бином-Пресс≫,2004 г. – 366с.:ил.

ТЕКСТ ПРОГРАММЫ

Файл Graph.h

// 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_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

class CGraphV{

public:

CPoint pt;

CString Title;

public:

CGraphV() : pt(CPoint(0,0)), Title(_T("")){};

virtual ~CGraphV() {};

public:

CGraphV& operator = (const CGraphV& gV){

pt = gV.pt; Title = gV.Title;

return *this;

}

};

class CGraphE{

public:

BOOL state;

double len;

public:

CGraphE() : state(FALSE),len(0.0){};

virtual ~CGraphE() {};

public:

CGraphE& operator = (const CGraphE& gE){

state = gE.state; len = gE.len;

return *this;

}

};

class CGraph

{

public:

CGraphV *V;

CGraphE *E;

int V_count;

int curV;

public:

void Create(int mV_count);

BOOL IsExist();

void Destroy();

void Null(int m_V,double len);

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 Save(CString fname);

void Load(CString fname);

void MoveV(int m_x, int m_y);

void SetCurV(int m_cur) { curV = m_cur;};

void DeleteV(int indexV);

void AddV(CPoint pt, CString m_Title);

void MakeFull();

public:

CGraph();

virtual ~CGraph();

public:

CGraph& operator = (const CGraph& g){

int i=0;

Destroy();

Create(g.V_count);

for(i=0;i<V_count;i++) V[i]=g.V[i];

for(i=0;i<V_count*V_count;i++) E[i]=g.E[i];

curV = g.curV;

return *this;

}

CGraph& operator ! (){

int i=0,j=0;

BOOL fl = FALSE;

for(i=0;i<V_count;i++)

for(j=0;j<V_count;j++)

if(i!=j) {

fl = !(E[i*V_count+j].state);

E[i*V_count+j].state=fl;

}

return *this;

}

};

#endif // !defined(AFX_GRAPH_H__8C8860CB_4D3F_4F0B_9B81_66289DCC2354__INCLUDED_)

Файл Graph.cpp

// Graph.cpp: implementation of the CGraph class.

//

//////////////////////////////////////////////////////////////////////

#include "stdafx.h"

#include "KursovikMin.h"

#include "Graph.h"

#ifdef _DEBUG

#undef THIS_FILE

static char THIS_FILE[]=__FILE__;

#define new DEBUG

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать