Решение математических задач с помощью графов

 

Решение математических задач с помощью графов.

Введение

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

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

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

Рисунок 1

 

 

 

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

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

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

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

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

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

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

Замечание

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

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

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

а для орграфа

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

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

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

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

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

Массив  дуг

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

производных органических соединений

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

Заключение

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Практическое  задание

1. На листе 1 создадим таблицу для учета товаров, цены и товарных остатков для группы товаров«Лист»:

Рисунок 1 -  Таблица Лист. Формулы

В результате получим  таблицу со значениями:

 

 

 

Рис.4.2 Таблица  Лист

На этом же листе  создаем 3 таблицы учета товарных запасов для каждой группы товаров:

 

 

 

 

 

Рис. 4.3 Таблица Товарные запасы. Формулы

 

 

 

 

Рис.4.4. Таблица Товарные запасы. Результаты вычислений.

 

Аналогично  заполним таблицы еще на две группы товаров: стиральные порошки и наборы шоколадных конфет.

 

2. На 2 листе создать таблицу Журнал продаж.В ней отражается количество проданного товара на каждый день и суммарное за неделю.

Рис.4.5 Таблица  Журнал продаж. Формулы

Рис.4.6 Таблица  Журнал продаж. Значения

Аналогичные таблицы  создаем для всех трех групп товаров.

3. На 3 листе создать таблицу для определения рентабельности:

 

Рис.4.10 Таблица Учет затрат. Формулы

4. На 4 листе создать таблицу для определения затрат:

 

 

 

 

 

 

Рис.4.9 Таблица Учет затрат. Формулы

 

 

Рис.4.10 Таблица Учет затрат. Значения