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

Это число можно представить  в виде суммы: Г=φ₁+φ₂+φ₃+…,  где φ₃ –  число граней, ограниченных тремя ребрами, φ₄ — число граней, ограниченных четырьмя ребрами и т. д.

С другой стороны, каждое ребро является границей двух граней, а поэтому  число граней равно 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 квартал 2006 г., руб.
Наименование доходов	Сентябрь	Октябрь	Ноябрь	Декабрь
Зарплата	4000	3000	2200	3200
Прочие поступления	-	500	-	1000
Сумма дохода в месяц

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

Доходы Чижова А. С. за 1 квартал 2006 г., руб.
Наименование доходов	Сентябрь	Октябрь	Ноябрь	Декабрь
Зарплата	7200	7000	7500	7400
Прочие поступления	1200	500	500	1000
Сумма дохода в месяц

Таблица 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 Расходы семьи Чижовых за квартал

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

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

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

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

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

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

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

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

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