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

Автор работы: Пользователь скрыл имя, 24 Марта 2011 в 16:58, курсовая работа

Описание работы

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

Содержание работы

Введение 3
1. Теоретическая часть 4
1.1 История возникновения теории графов 4
1.2 Основные понятия теории графов 6
1.3 Основные теоремы теории графов 9
1.4 Способы представления графов в компьютере 14
1.4.1 Требования к представлению графов 14
1.4.2 Матрица смежности 14
1.4.3 Матрица инциденций 15
1.4.4 Списки смежности 15
1.4.5 Массив дуг 15
1.5 Обзор задач теории графов 16
Заключение 17
2. Практическая часть 18
2.1. Общая характеристика задачи 18
2.2. Описание алгоритма решения задачи 19
Список использованной литературы 24

Скачать архив (77.38 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

теория графов.doc

— 309.50 Кб (Скачать файл)

    Таблица 2 Доходы Чижова А. С. за квартал

Расходы семьи Чижовых за 1 квартал 2006 г., руб.
Наименование  расходов Сентябрь Октябрь Ноябрь Декабрь
Коммунальные  платежи 630 670 700 800
Оплата  электроэнергии 100 100 120 120
Оплата  телефонных счетов 195 195 195 195
Расходы на питание 2500 2500 2600 3000
Прочие  расходы 1000 1000 1500 2000
Погашение кредита 4000 4000 4000 4000
Суммарный расход в месяц        

    Таблица 3 Расходы семьи Чижовых за квартал

    1. Заполнить таблицу 4 числовыми данными о доходах семьи за квартал, выполнив консалидацию по расположению данных.
Доходы  семьи Чижовых за 1 квартал 2006 г., руб.
Наименование  доходов Сентябрь Октябрь Ноябрь Декабрь
Зарплата        
Прочие  поступления        
Сумма дохода в месяц        

    Таблица 4 Доходы семьи Чижовых за квартал

    1. Составить таблицу планирования бюджета семьи на квартал (табл. 5).
Бюджет  семьи Чижовых за 1 квартал 2006 г., руб.
Наименование Сентябрь Октябрь Ноябрь Декабрь
Суммарный доход в месяц        
Суммарный расход в месяц        
Остаток        

    Таблица 5 Бюджет семьи Чижовых за квартал

    1. По данным о бюджете семьи на квартал (табл. 5) построить гистограмму.

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

    1. Запустить табличный процессор MS Excel.
    2. Создать книгу с именем «Бюджет».
    3. Лист 1 переименовать в лист с названием Доходы.
    4. На рабочем листе Доходы MS Excel создать таблицы «Доходы Чижовой М. А. за квартал» и «Доходы Чижова А. С. за квартал».
    5. Заполнить таблицы доходов исходными данными (рис. 2.1).

    Рисунок 2. 1 Расположение таблиц доходов на рабочем листе Доходы MS Excel

    1. Лист 2 переименовать в лист с названием Расходы.
    2. На рабочем листе Расходы MS Excel создать таблицу расходов семьи Чижовых за квартал.
    3. Заполнить таблицу расходов исходными данными (рис. 2.2)

    Рисунок 2. 2 Расположение таблиц расходов на рабочем листе Расходы MS Excel

    1. Заполнить строку Сумма дохода в месяц таблиц «Доходы Чижовой М. А. за 1 квартал 2006 г., руб.» и «Доходы Чижова А. С. за 1 квартал 2006 г., руб.», находящихся на листе Доходы следующим образом:

    Занести в ячейку С6 формулу:

    =С4+С5

    Размножить  введенную в ячейку С6 формулу  для остальных ячеек (с С4 по F4 и с С12 по F12) данных строк.

    Таким образом будет автоматически подсчитаны суммы дохода в месяц (рис. 2.3).

    Рисунок 2. 3 Автоматический подсчет суммы доходов в месяц

    1. Заполнить строку Суммарный расход в месяц таблицы «Расходы семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Расходы следующим образом:

    Занести в ячейку С10 формулу:

    =СУММ(C4:C9)

    Размножить  введенную в ячейку С10 формулу для остальных ячеек (с С10 по F10) данной строки.

    Таким образом будет автоматически подсчитана сумма расхода в месяц (рис. 2.4).

    Рисунок 2. 4 Автоматический подсчет суммы расходов в месяц

    1. Лист 3 переименовать в лист с названием Итоги.
    2. На рабочем листе Итоги MS Excel создать таблицу «Доходы семьи Чижовых за 1 квартал 2006 г., руб.»
    3. Заполнить строки Зарплата, Прочие поступления, Сумма дохода в месяц таблицы «Доходы семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги следующим образом:

    Занести в ячейку С4 формулу:

    =Доходы!C4+Доходы!C10

    Размножить  введенную в ячейку С4 формулу для остальных ячеек (с С4 по F6) данной таблицы.

    Таким образом будут автоматически подсчитана сумма дохода в месяц (рис. 2.5).

    Рисунок 2. 5 Автоматический подсчет суммы доходов в месяц

    1. На рабочем листе Итоги MS Excel создать таблицу «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.»
    2. Заполнить строку Суммарный доход в месяц таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги следующим образом:

    Занести в ячейку С11 формулу:

    =C6

    Размножить введенную в ячейку С11 формулу для остальных ячеек (с С11 по F11) данной таблицы.

    1. Заполнить строку Суммарный расход в месяц таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги следующим образом:

    Занести в ячейку С12 формулу:

    =Расходы!C10

    Размножить  введенную в ячейку С12 формулу для остальных ячеек (с С12 по F12) данной таблицы.

    1. Заполнить строку Остаток таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги следующим образом:

    Занести в ячейку С13 формулу:

    =C11-C12

    Размножить  введенную в ячейку С13 формулу для остальных ячеек (с С13 по F13) данной таблицы.

    Таким образом будет заполнена таблица  «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.» (рис. 2.6)

    Рисунок 2. 6 Автоматическое заполнение таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.»

    1. Лист 4 переименовать в лист с названием Гистограмма.
    2. По данным таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.» на листе Гистограмма построим гистограмму (рис. 2.7).

        

    

    Рисунок 2. 7 Гистограмма

 

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

  1. Болтянский  В.Г., Наглядная топология, М., Просвещение, 1982.
  2. Кордемский Б.А., Математическая смекалка, М., Физматгиз, 1954.
  3. Кук Д., Бейз Г., Компьютерная математика, М., Наука, 1990.
  4. Оре О., Графы и их применение, Новокузнецкий Физико-математический институт, 2000.
  5. Информатика. Лабораторный практикум для студентов 2 курса всех специальностей. – М.: ВЗФЭИ, 2006.

Информация о работе Применение теории графов в информатике