ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

КАФЕДРА АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ ЭКОНОМИЧЕСКОЙ ИНФОРМАЦИИ

КУРСОВАЯ РАБОТА

по дисциплине «Информатика»

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

Исполнитель:

специальность

группа

№ зачетной книжки

Руководитель:

Туймазы – 2007

Содержание

Введение. 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

Введение

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

1. Теоретическая часть

1.1 История возникновения теории графов

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783) [3, стр. 36]. Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

1. Задача о Кенигсбергских мостах.
На рис. 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует) Эйлером в 1736 году.

Рисунок 1

2. Задача о трех домах и трех колодцах.
Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году [2, стр. 51].

Рисунок 2

3. Задача о четырех красках.
Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

Рисунок 3

1.2 Основные понятия теории графов

1) Графом
G
(
V
,
E
)
называется совокупность двух множеств – непустого множества V(множества вершин) и множества E двухэлементных подмножеств множества V(E – множество ребер).

2) Ориентированным
называется граф, в котором - множество упорядоченных пар вершин вида (x,y), где x называется началом, а y – концом дуги. Дугу (x, y) часто записывают как . Говорят также, что дуга ведет от вершины x к вершине y, а вершина yсмежная
с вершиной x.

3) Если элементом множества E может быть пара одинаковых
(не различных) элементов V, то такой элемент множества E называется петлей
, а граф называется графом с петлями
(или псевдографом
).

4) Если E является не множеством, а набором
, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами
, а граф называется мультиграфом
.

5) Если элементами множества E являются не обязательно двухэлементные, алюбые подмножества множества V, то такие элементы множества E называются гипердугами
, а граф называется гиперграфом
.

6) Если задана функция F
:
V
→
M
и/или F
:
E
→
M
, то множество M
называется множеством пометок
, а граф называется помеченным
(или нагруженным
). В качестве множества пометок обычно используются буквы или целые числа. Если функция F
инъективна, то есть разные вершины (ребра)имеют разные пометки, то граф называют нумерованным
.

7) Подграфом
называется граф G′(V′,E′), где и/или .

a) Если V′ = V, то G′ называется остовным
подграфом G.

b) Если , то граф G′ называется собственным
подграфом графа G.

c) Подграф G′(V′,E′) называется правильным подграфом графа G(V,E), если G′ содержит все возможные рёбра G.

8) Степень (валентность)
вершины – это количество ребер, инцидентных этой вершине (количество смежных с ней вершин).

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

a) Если , то маршрут замкнут
, иначе открыт
.

b) Если все ребра различны, то маршрут называется цепью.

c) Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью
.

d) Замкнутая цепь называется циклом
.

e) Замкнутая простая цепь называется простым циклом
.

f) Граф без циклов называется ациклическим.

g) Для орграфов цепь называется путем
, а цикл – контуром
.

рис. 4. Маршруты, цепи, циклы

Пример

В графе, диаграмма которого приведена на рис.4:

1. v₁
, v₃
, v₁
, v₄
– маршрут, но не цепь;

2. v₁
, v₃
, v₅
, v₂
, v₃
, v₄
– цепь, но не простая цепь;

3. v₁
, v₄
, v₃
, v₂
, v₅
– простая цепь;

4. v₁
, v₃
, v₅
, v₂
, v₃
, v₄
, v₁
– цикл, но не простой цикл;

5. v₁
, v₃
, v₄
, v₁
– простой цикл.

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

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

12) Деревом
называется связный граф без циклов.

13) Остовом
называется дерево, содержащее все вершины графа.

14) Паросочетанием
называется множество ребер, в котором никакие два не смежны.

15) Паросочетание называется максимальным
, если никакое его надмножество не является независимым.

16) Две вершины в графе связаны
, если существует соединяющая их простая цепь.

17) Граф, в котором все вершины связаны, называется связным.

18) Граф, состоящий только из изолированных вершин, называется вполне несвязным.

19) Длиной маршрута
называется количество ребер в нем (с повторениями).

20) Расстоянием
между вершинами u и v называется длина кратчайшей цепи , а сама кратчайшая цепь называется геодезической
.

21) Диаметром
графа G называется длина длиннейшей геодезической.

22) Эксцентриситетом
вершины v в связном графе G(V,E) называется максимальное расстояние от вершины v до других вершин графа G.

23) Радиусом
графа G называется наименьший из эксцентриситетов вершин.

24) Вершина v называется центральной
, если ее эксцентриситет совпадает с радиусом графа.

25) Множество центральных вершин называется центром
графа.

рис. 5 Эксцентриситеты вершин и центры графов (выделены).

1.3 Основные теоремы теории графов

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

Теорема 1.
Удвоенная сумма степеней вершин любого графа равна числу его ребер. [
1, стр. 66]

Доказательство
. Пусть А₁

, А₂

, А₃

, ...,A_n

—
вер­шины данного графа, ap(A
₁

), p(А₂

), ..., p(A_n

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

Отсюда следует: p(A
₁

)+p(А₂

)+ ... +p(A_n

)=0,5N,
или 2(p(A₁

)+p(А
₂

)+ ... +p(A_n

))=N
, где N
—
число ребер.

Теорема 2.
Число нечетных вершин любого графа четно.

Доказательство
. Пусть a
₁

,
a
₂

,
a
₃

, …,
a_k

—
это сте­пени четных вершин графа, а b
₁

,
b
₂

,
b
₃

, …,
b_m

—
степени нечетных вершин графа. Сумма a
₁

+
a
₂

+
a
₃

+…+
a_k

+
b
₁

+
b
₂

+
b
₃

+…+
b_m

ровнов два раза превышает число ребер гра­фа. Сумма a
₁

+
a
₂

+
a
₃

+…+
a_k

четная (как сумма четных чисел), тогда сумма b
₁

+
b
₂

+
b
₃

+…+
b_m

должна быть четной. Это возможно лишь в том случае, если m
—
четное, то есть четным является и число нечетных вершин графа. Что и требовалось доказать.

Следствие 1.
Нечетное число знакомых в любой компании всег­да четно.

Следствие 2.
Число вершин многогранника, в которых сходится нечетное число ребер, четно.

Следствие
3. Число всех людей, когда-либо пожавших руку дру­гим людям, нечетное число раз, является четным.

Теорема 3.
Во всяком графе с n
вершинами, где n
больше или равно 2, всегда найдутся две или более вершины с оди­наковыми степенями.

Доказательство
. Если граф имеет n
вершин, то каждая из них может иметь степень 0, 1, 2, ..., (n
-
1). Предположим, что в некотором графе все его вершины имеют различную степень, то есть,
и покажем, что этого быть не может. Действительно, если р(А
)=0,
то это значит, что А —
изолированная вершина, и поэтому в графе не найдется вершины Х
со степенью р(Х
)=n
-1.
В са­мом деле, эта вершина должна быть соединена с (n
-
1) вершиной, в том числе и с А
, но ведь А
оказалась изолированной. Следовательно, в графе, имеющем n
вершин, не мо­гут быть одновременно вершины степени 0 и (n
-1). Это значит, что из n
вершин найдутся две, имеющие одинаковые степени.

Теорема 4.
Если в графе с n
вершинами (n
больше или равно 2) только одна пара имеет одинаковуюстепень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

Доказательство данной теоремы мы опускаем. Остановимся лишь на некотором ее пояснении. Содержание этой теоремы хорошо разъясняется задачей: группа, состоящая из n
школьников, обменивается фотографиями. В некоторый момент времени выяс­няется, что двое совершили одинаковое число обме­нов. Доказать, что среди школьников есть либо один еще не начинавший обмена, либо один уже завершив­ший его.

Теорема
5.
Если у графа все простые циклы четной длины, то он не содержит ни одного цикла четной длины.

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

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

Теорема 7.
Для того чтобы на связном графе можно было бы проложить цепь АВ,
содержащую все его ребра в точности по одному разу, необходимо и достаточно, чтобы А
и В
были единственными нечет­ными вершинами этого графа.

Доказательство этой теоремы очень интересно и ха­рактерно для теории графов. Его также следует счи­тать конструктивным (обратите внимание на то, как использована при этом теорема 3.6). Для доказательства к исходному графу присоеди­няем ребро (А
, В
); после этого все вершины графа станут четными. Этот новый граф удовлетворяет всем условиям теоремы 3.6, и поэтому в нем можно про­ложить эйлеров цикл Ψ.
И если теперь в этом цикле удалить ребро (А
, В
),
то останется искомая цепь АВ.

На этом любопытном приеме основано доказатель­ство следующей теоремы, которую следует считать обоб­щением теоремы 7.

Теорема 8.
Если данный граф является связ­ным и имеет 2k
вершин нечетной степени, то в нем можно провести k
различных цепей, содержащих все его ребра в совокупности ровно по одному разу.

Теорема 9.
Различных деревьев с n
перенумерованными вершинами можно построить n<sup>n

-2</sup>

.

По поводу доказательства этой теоремы сделаем одно замечание. Эта теорема известна, в основном, как вывод английского математика А. Кэли (1821—1895). Графы-деревья издавна привлекали внимание ученых. Се­годня двоичные деревья используются не только ма­тематиками, а и биологами, химиками, физиками и инженерами (подробнее об этом – в параграфе 6).

Теорема 10.
Полный граф с пятью верши­нами не является плоским.

Доказательство
. Воспользуемся формулой Эйлера: В-Р+Г
=2,
где В
— число вершин плоского графа, Р
— число его ре­бер, Г
— число граней. Формула Эйлера справедлива для плоских связных графов, в которых ни один из многоугольников не лежит внутри другого.

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

обозначить число таких граней, то φ₂

=0. Далее рассуждаем от противного, а именно: пред­положим, что исследуемый граф плоский. Это значит, что для него верна формула Эйлера. Число вершин в данном графе В
=5,
число ребер Р
=10, тогда число граней Г
=2-В
+Р
=2-5+10=7.

Это число можно представить в виде суммы: Г
=φ₁
+φ₂
+φ₃
+
…, где φ₃

– число граней, ограниченных тремя ребрами, φ₄

— число граней, ограниченных че­тырьмя ребрами и т. д.

С другой стороны, каждое ребро является границей двух граней, а поэтому число граней равно 2Р,
в то же время 2Р
=20=3φ₃
+
4φ₄

+...
. Умножив равенство Г
=7=φ₃
+ φ₄
+ φ₅
+
…
на три, получим ЗГ
=21=3( φ₃
+ φ₄
+ φ₅
+ …).

Ясно, что (3φ₃
+
3φ₄

+3φ₅

+…) < (3φ₃
+
4φ₄
+
5φ₅
+
…)

или 3Г
<2Р
, но по условию, 2Р
=20, а ЗГ
=21; поэтому вывод, полученный при введенном нами предположе­нии (граф плоский), противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами не является плоским.

Теорема 11. (Теорема Понтрягина-Куратовского)
Граф является плоским тогда и только тогда, когда он не имеет в качестве подграфа полного графа с пятью вершинами.

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

1.4 Способы представления графов в компьютере

Конструирование структур данных для представления в программе объектов математической модели – это основа искусства практического программирования. Далее приводится четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовых идеях, которые описаны в этом разделе.

1.4.1 Требования к представлению графов

Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) – объема памяти для каждого представления. Здесь p – число вершин, а q – число ребер.

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

Представление графа с помощью квадратной булевой матрицы M, отражающей смежность вершин, называется матрицей смежности,
где

Для матрицы смежности n(p,q) = O(p²
).

Замечание

Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.

1.4.3 Матрица инциденций

Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций
, где для неориентированного графа

а для орграфа

Для матрицы инциденций n(p,q) = O(pq).

1.4.4 Списки смежности

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

N : record
v : 1..p; n :↑ N end record
,

называется списком смежности
. В случае представления неориентированных графов списками смежности n(p,q) = O(p+2q), а в случае ориентированных графов n(p,q) = O(p+q).

1.4.5 Массив дуг

Представление графа с помощью массива структур

E : array
[1..q] of record
b,e : 1..p end record
,

отражающего список пар смежных вершин, называется массивом ребер
(или, для орграфов, массивом дуг
). Для массива ребер (или дуг) n(p,q) = O(2q).

1.5 Обзор задач теории графов

Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.[4, стр. 12-15]

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

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

- Задача о кратчайшей цепи

замена оборудования

составление расписания движения транспортных средств

размещение пунктов скорой помощи

размещение телефонных станций

- Задача о максимальном потоке

анализ пропускной способности коммуникационной сети

организация движения в динамической сети

оптимальный подбор интенсивностей выполнения работ

синтез двухполюсной сети с заданной структурной надежностью

задача о распределении работ

- Задача об упаковках и покрытиях

оптимизация структуры ПЗУ

размещение диспетчерских пунктов городской транспортной сети

- Раскраска в графах

распределение памяти в ЭВМ

проектирование сетей телевизионного вещания

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

проектирование кратчайшей коммуникационной сети

синтез структурно-надежной сети циркуляционной связи

анализ надежности стохастических сетей связи

- Изоморфизм графов и сетей

структурный синтез линейных избирательных цепей

автоматизация контроля при проектировании БИС

- Изоморфное вхождение и пересечение графов

локализация неисправности с помощью алгоритмов поиска МИПГ

покрытие схемы заданным набором типовых подсхем

- Автоморфизм графов

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

синтез тестов цифровых устройств

Заключение

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

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

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

Расмотрим следующую задачу:

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

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

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

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

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

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

3. Составить таблицу планирования бюджета семьи на квартал (табл. 5).

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

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

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

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

2. Создать книгу с именем «Бюджет».

3. Лист 1 переименовать в лист с названием Доходы.

4. На рабочем листе Доходы
MSExcel создать таблицы «Доходы Чижовой М. А. за квартал» и «Доходы Чижова А. С. за квартал».

5. Заполнить таблицы доходов исходными данными (рис. 2.1).

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

6. Лист 2 переименовать в лист с названием Расходы.

7. На рабочем листе Расходы
MS Excel создать таблицу расходов семьи Чижовых за квартал.

8. Заполнить таблицу расходов исходными данными (рис. 2.2)

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

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

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

=С4+С5

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

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

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

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

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

=СУММ(C4:C9)

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

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

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

11. Лист 3 переименовать в лист с названием Итоги.

12. На рабочем листе Итоги
MS Excel создать таблицу «Доходы семьи Чижовых за 1 квартал 2006 г., руб.»

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

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

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

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

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

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

14. На рабочем листе Итоги
MS Excel создать таблицу «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.»

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

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

=C6

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

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

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

=Расходы!C10

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

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

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

=C11-C12

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

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

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

18. Лист 4 переименовать в лист с названием Гистограмма.

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

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

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

1. Болтянский В.Г., Наглядная топология, М., Просвещение, 1982.

2. Кордемский Б.А., Математическая смекалка, М., Физматгиз, 1954.

3. Кук Д., Бейз Г., Компьютерная математика, М., Наука, 1990.

4. Оре О., Графы и их применение, Новокузнецкий Физико-математический институт, 2000.

5. Информатика. Лабораторный практикум для студентов 2 курса всех специальностей. – М.: ВЗФЭИ, 2006.