Каталог Рефератов - Применение теории графов в информатике

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

Применение теории графов в информатике

нопка «Удалить» предназначена для удаления вершин графа.

Рис. 10. Кнопка «Удалить»

При нажатии на кнопку «Новый» рабочее поле программы будет очищено и появится возможность ввода нового графа.

Рис. 11. Кнопка «Новый»

Кнопка «Помощь» вызывает помощь программы.

Рис. 12. Кнопка «Помощь»

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

Рис. 13. Кнопка «Обновить»

При нажатии на кнопку «Настройки» на экране появится окно, в котором можно настроить параметры сетки рабочего поля программы и цвета вводимого графа.

Рис. 14. Кнопка «Настройка»

Окно настроек выглядит следующим образом:

Рис. 15. Окно настроек

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

При включенной кнопке «Показывать сетку» отображается сетка для удобства ввода вершин.

Рис. 16. Кнопка «Показывать сетку»

Для автоматического ввода длины ребра графа необходимо нажать кнопку.

Рис. 17. Кнопка «Автоматический ввод длинны ребра»

При включенной кнопке «Выравнивать по сетке» новые вершины будут автоматически выравниваться по координатной сетке.

Рис. 18. Кнопка «Выравнивать по сетке»

Если выбрать две различные вершины (щелчком левой кнопки мыши) нажать на кнопку, то программа найдет кратчайший путь между вершинами.

Рис. 19. Кнопка «Нахождение кратчайшего пути между вершинами»

2. Практическая часть

2.1 Общая характеристика задачи

Агентство по грузоперевозкам "Летучий голландец" предоставляет услуги по перевозке грузов по различным маршрутам. Данные о маршрутах, выполненных в течение недели, по каждому водителю приведены на рис. 1.

Сведения о выполненных маршрутах
№ п/п	ФИО водителя	Марка автомобиля	№ рейса	Выполнено рейсов, шт.	Протяженность рейса, км.	Расход топлива на 100 км, л	Израсходовано топлива, л	Грузоподъемность, т	Вес перевезенного груза, т
1	Соловьев В.В.	КАМАЗ	А112	4
2	Михайлов С.С.	ЗИЛ	С431	3
3	Кузнецов Я.Я.	МАЗ	А112	5
4	Иванов К.К.	МАЗ	М023	7
5	Сидоров А.А.	ЗИЛ	В447	2
6	Волков Д.Д.	КАМАЗ	С431	8
7	Быков Л.Л.	КАМАЗ	В447	4
	ИТОГО	Х	Х
	В СРЕДНЕМ	Х	Х

Рис. 1. Данные о маршрутах

Справочные данные о технических характеристиках автомобилей и протяженности маршрутов представлены на рис. 2.

Протяженность рейсов
№ п/п	№ рейса	Протяженность рейса, км
1	А112	420
2	В447	310
3	М023	225
4	С431	250
Технические характеристики автомобилей
№ п/п	Марка автомобиля	Расход топлива на 100 км, л	Грузоподъемность, т
1	ЗИЛ	42	7
2	КАМАЗ	45	16
3	МАЗ	53	12

Рис. 2 Данные о технических характеристиках автомобилей и протяженности маршрутов

1. Построить таблицы по приведенным ниже данным.

2.Выполнить расчет количества израсходованного топлива каждым водителем и веса перевезенного груза, данные расчета занести в таблицу.

3. Организовать межтабличные связи для автоматического формирования ведомости расхода топлива за неделю.

4. Сформировать и заполнить ведомость расхода топлива каждым водителем за неделю.

5. Результаты расчета количества израсходованного топлива за неделю представить в графическом виде.

2.2 Описание алгоритма решения задачи

1. Запустить табличный процессор МS Excel.

2. Создать книгу с именем “Летучий голландец”.

3. Лист 1 переименовать в лист с названием Сведения.

4. На рабочем листе Сведения создать таблицу Сведения о выполненных маршрутах (табл. №1).

5. Заполнить таблицу Сведения о выполненных маршрутах.

6. Лист 2 переименовать в лист Характеристики.

7. На рабочем листе Характеристики создать таблицу, в которой будут содержаться технические характеристики автомобилей (табл. №2).

8. Заполнить таблицу со списком Технических характеристик автомобилей.

9. Лист 3 переименовать в лист Протяженность.

10. На рабочем листе Протяженность, создать таблицу протяженности рейсов (табл. №3).

11. Заполнить таблицу Протяженность рейсов исходными данными.

12. Лист 4 переименовать в Ведомость (табл. №4).

13. На рабочем листе Ведомость создать таблицу Ведомость расхода топлива.

14. Лист 5 переименовать в лист График (табл. №5).

15. На рабочем листе График создать график учета расхода топлива на каждого водителя.

16. Заполнить графу Израсходовано топливо таблицы “Сведения о выполненных маршрутах” находящейся на листе Сведения следующим образом:

Занести в ячейку H3 формулу: =СУММ(F3*G3/100).

Размножить введенную в ячейку Н3 формулу для остальных ячеек (с Н4 по Н7) данной графы, соответственно меняя строки F3, G3 на соответствующие строкам в столбце Н.

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

17. Заполнить графу Вес перевезенного груза таблицы “Сведения о выполненных маршрутах” находящейся на листе Сведения следующим образом:

Занести в ячейку J3 формулу: =СУММ(I3*E3).

Размножить введенную в ячейку J3 формулу для остальных ячеек (с J4 по J7) данной графы, соответственно меняя строки I3, E3 на соответствующие строкам в столбце J.

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

18. На листе Ведомость заполнить графу Израсходовано топлива следующим образом:

Занести в ячейку Е12 формулу: =СУММ(Сведения!H3).

Размножить введенную в ячейку Е12 формулу для остальных ячеек (с Е12 по Е18) данной графы, соответственно меняя строки формулы с Н3 по Н9.

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

19. На листе Ведомость заполнить графу Выполнено рейсов следующим образом:

Занести в ячейку D12 формулу =СУММ(Сведения!E3).

Размножить введенную в ячейку D12 формулу для остальных ячеек (с D13 по D18) данной графы, соответственно меняя строки формулы с Е3 по Е9.

Таким образом, будет выполнен автоматический подсчет количества выполненных рейсов.

20.По результатам заполненных параметров в таблице «Ведомость расхода топлива» создать график расхода топлива на листе «график».

Таблица №1

Сведения о выполненных маршрутах
№ п/п	ФИО водителя	Марка автомобиля	№ рейса	Выполнено рейсов,шт.	Протяженность рейсов,км	Расход топлива на 100км,л	Израсходовано топлива,л	Грузоподъемность,т	Вес перевезенного груза,т
1	Соловьев В.В.	КАМАЗ	А112	4	420	45	189	16	64
2	Михайлов С.С.	ЗИЛ	С431	3	250	42	105	7	21
3	Кузнецов Я.Я.	МАЗ	А112	5	42	53	222,6	12	60
4	Иванов К.К.	МАЗ	М023	7	225	53	119,25	12	84
5	Сидоров А.А.	ЗИЛ	В447	2	310	42	130,2	7	14
6	Волков Д.Д.	КАМАЗ	С431	8	250	45	112,5	16	128
7	Быков Л.Л.	КАМАЗ	В447	4	310	45	139,5	16	64
	ИТОГО			33	2185	325	1018,05	86	435
	В СРЕДНЕМ			4,71	312,14	46,43	145,44	12,29	62,14

Таблица №2

Технические характеристики автомобилей
№ п/п	Марка автомобиля	Расход топлива на 100 км, л	Грузоподъемность, т
1	ЗИЛ	42	7
2	КАМАЗ	45	16
3	МАЗ	53	12

Таблица№3

Протяженность рейсов
№ п/п	№ рейса	Протяженность рейса, км
1	А112	420
2	В447	310
3	М023	225
4	С431	250

Таблица №4

ФИО водителя

№ рейса

Выполнено рейсов, шт

Израсходовано топлива, л

Соловьев В.В.

А112

189

Михайлов С.С.

С431

105

Кузнецов Я.Я.

А112

222,6

Иванов К.К.

М023

119,25

Сидоров А.А.

В447

130,2

Волков Д.Д.

С431

112,5

Быков Л.Л.

В447

139,5

ИТОГО

1018,05

Бухгалтер _________________________

Таблица №5

Заключение

В работе были рассмотрены задачи из теории графов, которые уже стали классическими. Особенно часто в практическом программировании возникают вопросы о построении кратчайшего остова графа и нахождении максимального паросочетания. Известно также, что задача о нахождении гамильтонова цикла принадлежит к числу NP-полных, т.е. эффективный алгоритм для ее решения не найден. Таким образом, задачи теории графов актуальны, так как могут принести экономию времени и средств на производстве и в быту. Теория графов находит широкое применение в различных областях науки и техники:

Графы и информация

Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.

Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

CnH2n+2

Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.

Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.

Графы и биология

Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов - размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.

Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

Графы и физика

Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.

Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.

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

Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов.

Страницы: 1, 2, 3

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.