Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа



Скачать 75.57 Kb.
Дата11.10.2012
Размер75.57 Kb.
ТипКурсовая


Министерство образования и науки Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра прикладной математики

Курсовая работа по практикуму на ЭВМ:

структуры данных и алгоритмы

Факультет: прикладной математики и информатики

Группа:

Студент:

Преподаватель:

Новосибирск 2009
1. Условие

В заданном графе указать его четырёхвершинные полные подграфы.
2. Анализ задачи

2.1. Исходные данные задачи:

n – количество вершин в графе,

m – количество рёбер в графе,

E – множество рёбер графа,

2.2. Результат:

R – множество вершин четырёхвершинных полных подграфов данного графа,

2.3. Решение:

Неориентированный граф называется подграфом графа , если , . Неориентированный граф является полным, если две его вершины смежны, т.е. соединены между собой ребром. Количество рёбер n-вершинного неориентированного графа вычисляется по формуле , в частности для четырёхвершинного полного графа оно равно 6. Таким образом, для нахождения всех полных четырёхвершинных подграфов заданного неориентированного графа, необходимо убедиться, что заданный граф имеет, по крайней мере, 6 рёбер (в противном случае внутри него не может существовать ни один четырёхвершинный полный подграф), и, перебирая неупорядоченные четырёхвершинные подмножества множества его вершин, добавлять их в список полных подграфов в случае, если между каждой парой вершин подмножества в исходном графе существует ребро.
Формальная постановка задачи

Добавить каждое неупорядоченное четырёхэлементное подмножество множества V исходного графа в список полных четырёхэлементных подграфов в случае, если .
3. Структуры данных, используемые для представления исходных данных и результатов задачи

3.1.
Входные данные

Внешнее представление неориентированного графа:

<ребро-графа> ::= <вершина-графа> пробел <вершина-графа>

<вершина-графа> ::= число

Внутреннее представление неориентированного графа: матрица смежности (такое представление позволяет быстро определить наличие/отсутствие ребра в графе)

int G[n][n];

3.2. Выходные данные

Внешнее представление: список четвёрок вершин исходного графа, составляющих его четырёхвершинные полные подграфы:

<список-вершин> ::= <список-вершин> | <список-вершин> <четвёрка-вершин>

<четвёрка-вершин> ::= <номер-вершины>,<номер-вершины>,<номер-вершины>,<номер-вершины>

<номер-вершины> ::= <число>

Внутреннее представление:

struct list

{

int a, b, c, d;

list *next;

list *prev;

};

list *complete;
4. Укрупнённый алгоритм решения задачи

4.1.

{

Граф = ВводГрафа

СписокЧетырёхВершинныхПодграфов = Пустой

Если (Граф->КоличествоРёбер >= 6)

{

for (i = 0..Граф->КоличествоВершин – 1)

for (j = i + 1..Граф->КоличествоВершин – 1)

for (k = j + 1..Граф->КоличествоВершин – 1)

for (l = k + 1..Граф->КоличествоВершин – 1)

{

СписокЧетырёхВершинныхПодграфов->Добавить({i, j, k, l})

}

}

Если (СписокЧетырёхВершинныхПодграфов->Пуст)

{

Ответ: Граф не содержит четырёхвершинных подграфов

} иначе {

Ответ: Граф содержит четырёхвершинные подграфы:

Вывести СписокЧетырёхВершинныхПодграфов

}

}

5. Структура программы

Текст программы разбит на два модуля.

Модуль 1 содержит основную подпрограмму, осуществляющую ввод графа, перебор подграфов, проверку их на полноту и вывод результата.

Модуль 2 содержит операции для работы со списком (двусвязный циклический список).

5.1. Состав модуля 1:

Главная функция main:

Назначение: ввод графа, перебор подграфов, проверка подграфов на полноту, вывод результата

Прототип: int main()

5.2. Состав модуля 2:

Функция createList:

Назначение: создание пустого двусвязного циклического списка.

Прототип: list *createList()

Функция: addToList:

Назначение: Добавление элемента в двусвязный циклический список

Прототип: void addToList(list *to, int a,int b,int c,int d)

5.3. Структура программы по управлению:



6. Текст программы на языке C++

main.cpp

#include

#include "list.h"
int main()

{

// Открытие файла теста

char filename[16];

printf("Filename: "); gets(filename);

FILE *fh = fopen(filename, "r");

if (!fh)

{

perror("Error opening file");

return 1;

}
int N, M;

fscanf(fh, "%d", &N); // Число вершин

fscanf(fh, "%d", &M); // Число рёбер

list *complete = createList(); // Список искомых подграфов

if (M >= 6)

{

// Четырёхвершинный полный подграф содержит не менее 6 вершин
// Построение графа

int **G = new int *[N];

for (int i = 0; i < N; i++)

{

G[i] = new int[N];

for (int j = 0; j < N; j++)

{

G[i][j] = 0;

}

}

// Ввод рёбер

for (int i = 0; i < M; i++)

{

int a, b;

fscanf(fh, "%d", &a); a--;

fscanf(fh, "%d", &b); b--;

G[a][b] = G[b][a] = 1;

}
// Перебор четырёхвершинных подграфов

for (int i = 0; i < N; i++)

for (int j = i + 1; j < N; j++)

for (int k = j + 1; k < N; k++)

for (int l = k + 1; l < N; l++)

{

if (G[i][j] && G[i][k] && G[i][l] && G[j][k] && G[j][l] && G[k][l])

{

// Нашли полный четырёхвершинный подграф

addToList(complete, i, j, k, l);

}

}

}
// Вывод результата

if (complete->next == complete)

{

// Ничего не найдено

printf("This graph does not contain four-vertices complete subgraphs\n");

} else {

list *p = complete;

printf("Found four-vertices complete subgraphs:\n");

while (complete != (p = p->next))

{

printf("%d %d %d %d\n", p->a + 1, p->b + 1, p->c + 1, p->d + 1);

}

}

return 0;

}
list.h

struct list

{

int a, b, c, d;

list *next;

list *prev;

};
list *createList();

void addToList(list *to, int a, int b, int c, int d);

list.cpp

#include "list.h"
list *createList()

{

list *result = new list;

result->next = result;

result->prev = result;

return result;

}
void addToList(list *to, int a, int b, int c, int d)

{

list *newItem = new list;

newItem->a = a;

newItem->b = b;

newItem->c = c;

newItem->d = d;

newItem->next = to;

newItem->prev = to->prev;

to->prev->next = newItem;

to->prev = newItem;

}




7. Набор тестов

Тест 1: Пустой граф

Входные данные: 7

0

Выходные данные: This graph does not contain four-vertices complete subgraphs




Тест 2: Непустой граф

Входные данные: 7

10

1 4

1 2

4 2

1 6

2 6

2 5

5 6

2 3

2 7

7 6

Выходные данные: This graph does not contain four-vertices complete subgraphs
Тест 3: Изолированные подграфы

Входные данные: 11

16

1 6

6 7

7 8

1 8

6 8

1 7

2 3

3 4

2 4

3 10

10 9

5 9

5 10

5 11

11 9

10 11

Выходные данные: Found four-vertices complete subgraphs:

1 6 7 8

5 9 10 11

Тест 4: Полный граф

Входные данные: 7

21

1 2

1 3

1 4

1 5

1 6

1 7

2 3

2 4

2 5

2 6

2 7

3 4

3 5

3 6

3 7

4 5

4 6

4 7

5 6

5 7

6 7

Выходные данные: Found four-vertices complete subgraphs:

1 2 3 4

1 2 3 5

1 2 3 6

1 2 3 7

1 2 4 5

1 2 4 6

1 2 4 7

1 2 5 6

1 2 5 7

1 2 6 7

1 3 4 5

1 3 4 6

1 3 4 7

1 3 5 6

1 3 5 7

1 3 6 7

1 4 5 6

1 4 5 7

1 4 6 7

1 5 6 7

2 3 4 5

2 3 4 6

2 3 4 7

2 3 5 6

2 3 5 7

2 3 6 7

2 4 5 6

2 4 5 7

2 4 6 7

2 5 6 7

3 4 5 6

3 4 5 7

3 4 6 7

3 5 6 7

4 5 6 7

Тест 5: Триангуляция

Входные данные: 7

12

1 2

2 3

3 7

7 6

6 5

5 1

1 4

5 4

6 4

7 4

3 4

2 4

Выходные данные: This graph does not contain four-vertices complete subgraphs


Похожие:

Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа
По системе двусторонних дорог определить, можно ли, построив какие-нибудь новые три дороги, из заданного города добраться до каждого...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа
Проверить, является ли заданный граф транзитивным, т е для любых трёх вершин u, v и w выполняется условие: если u и w, а также v...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа
В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города a в город b с минимальной...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКурсовая работа "Структуры и алгоритмы обработки данных" вариант 11 студент группы п 64 Ивантеева А. В
Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные по...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconРабочая программа «техно kids2 (Развивающая информатика, логика и математика)»
Автор: Ибрагимова А. С., к ф м н., доцент кафедры математики и прикладной информатики, Шмидт Н. М, к п н., доцент кафедры математики...
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconИстория и методология прикладной математики и информатики
Изучение истории развития прикладной математики, электронно-вычислительной техники и программирования
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconУчебное пособие по дисциплине «Структуры и алгоритмы обработки данных» для специальностей «Программное обеспечение информационных технологий»
Структуры и алгоритмы обработки данных: Учеб пособие. – Мн: бнту, 2010. – 151 с.: ил
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconКраткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия
Цели и задачи курса: структуры данных, алгоритмы обработки данных, работа с динамическими структурами, графами
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconСтруктуры и алгоритмы обработки данных
Структура данных работа с элементами которой организована по принципу fifo (первый пришел первый ушел) это
Курсовая работа по практикуму на эвм: структуры данных и алгоритмы Факультет: прикладной математики и информатики Группа iconУчебно-методический комплекс «Высокоуровневые методы информатики и программирования»
Автор: Рязанова О. В., ст преподаватель кафедры математики и прикладной информатики
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org