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

2. Раскраска в графах:

• распределение памяти в ЭВМ;
• проектирование сетей телевизионного вещания.

3. Связность графов и сетей:

• проектирование кратчайшей коммуникационной сети;
• синтез структурно-надежной сети циркуляционной связи;
• анализ надежности стохастических сетей связи.

4. Изоморфизм графов и сетей:

• структурный синтез линейных избирательных цепей;
• автоматизация контроля при проектировании БИС.

5. Автоморфизм графов:

• конструктивное перечисление структурных изомеров для производных органических соединений;
• синтез тестов цифровых устройств.

 

 

Заключение

 

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

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

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

 

 

2. Практическая часть
1. Общая характеристика задачи

 

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

Технические характеристики автомобилей

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

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

 

 

 

 

 

 

 

 

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

 

ФИО водителя № рейса Выполнено рейсов, шт Израсходовано топлива, л Соловьев В.В. А112     Михайлов С.С. С431     Кузнецов Я.Я. А112     Иванов К.К. М023     Сидоров А.А. В447     Волков Д.Д. С431     Быков Л.Л. В447     ИТОГО       Бухгалтер _________________________

 

Рис.3 ведомость расхода  горючего

 

 

2. Описание алгоритма решения  задачи
1. Заходим в МS Excel.
2. Создаем книгу с именем  «Летучий голландец».
3. Переименовываем Лист 1 в «Сведения О Выполненных Маршрутах»
4. На этом листе создадим таблицу «Сведения о выполненных маршрутах»
5. Заполняем графу Израсходовано топливо в таблице «Сведения о выполненных маршрутах» (рис.2):

• Заносим в ячейку H2 формулу: =СУММ(F2*G2/100)

• Заполняем ячейки с Н3 по Н8 данной графы, меняя строки F2 и G2 на соответствующие строкам в столбце Н. Таким образом, мы выполним автоматический подсчет расхода топлива.
• Заполняем графу Вес перевезенного груза таблицы “Сведения о выполненных маршрутах”:
• Заносим в ячейку J2 формулу: =СУММ(I2*E2).
• Заполняем ячейки с J3 по J8 данной графы, меняя строки I3, E3 на соответствующие строкам в столбце J.

6. Создаем Лист 2 и переименовываем его в «Тех.Характеристики Автомобилей».

7. На этом листе создадим таблицу «Тех.Характеристики Автомобилей» (Рис.2).
8. Создаем Лист 3 и переименовываем его в «Протяженность Рейсов».
9. На этом листе создадим таблицу Протяженности рейсов (Рис. 3).
10. Создаем Лист 4 и переименовываем его в «Ведомость».
11. На рабочем листе Ведомость создадим таблицу Ведомость расхода топлива. 
12. На листе «Ведомость» заполним графу «Израсходовано топлива» следующим образом (рис.4):

• Заносим в ячейку D8 формулу:

=СУММ(СведенияОВыполненныхМаршрутах!H2).

 

• Заполняем ячейки с D9 по D14 данной графы, соответственно меняя строки формулы с Н3 по Н7.    

13. На листе «Ведомость» заполним графу «Выполнено рейсов» следующим образом (рис.4):

• Заносим в ячейку C8 формулу

=СУММ(Сведения!E2).

• Заполняем ячейки с C9 по C14 данной графы, соответственно меняя строки формулы с Е3 по Е8.

 

Рис.1 Сведения О Выполненных Маршрутах

 

Рис.2  Тех.Характеристики Автомобилей

 

Рис.3 Протяженность рейсов

 

        Рис.4 ведомость

14. Создаем Лист 5 и переименовываем его в «Диаграмма » (рис.5)
15.    На панели меню нажимаем Вставка-Диаграмма. В появившемся окне Тип диаграммы открываем вкладку Стандартные и выбираем Гистограмма и нажимаем кнопку Далее.
16. В окне Источник данных диаграммы в вкладке Диапазон данных нажимаем на кнопку Исходные данные – Диапазон. Выделяем на листе Сведения столбцы от B3 до D9 и от G3 до H9. Нажимаем кнопку Далее.

 

Рис.5

 

 

Список используемой литературы

 

1. Бурков  В.Н.,  Заложнев  А.Ю.,  Новиков Д.А.  Теория  графов  в управлении организационными системами. М.: Синтег, 2001. – 124 с
2. Ивушкин Г.В., Способы представления графов в компьютере. -  http://www.cross-kpk.ru/ims/00408/page20.html
3. Кордемский Б.А., Математическая смекалка – М.: Физматгиз, 1954 – 326 с.
4. Кук Д., Бейз Г., Компьютерная математика. – М.: Наука, 1990 – 315с.
5. Самохин А. В. Проблема четырех красок: неоконченная история доказательства – СОЖ:  2000. - № 7. – 253с
6. Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980 — С. 336.
7. Рабкин Е.Л., Фарфоровская Ю.Б. Дискретная математика – М.: Просвещение, 2005 – 465с
8. http://ru.wikipedia.org/wiki/%D2%E5%EE%F0%E8%FF_%E3%F0%E0%F4%EE%E2