2.1. Применение графов в различных областях жизни людей

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

1. Можно составить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов».

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


2. Лабиринт.

Исследовать лабиринт - это найти путь в этом графе.

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


3. Генеалогическое древо.

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

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

Любая вершина дерева может порождать несколько потомков – вершин, соответствующих классам нижнего уровня.

Для каждой пары вершин дерева существует единственный путь, их соединяющий. Этим свойством пользуются при нахождении всех предков, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов. (приложение 1 рис.3).

4. Блок-схема программы

Графами являются блок – схемы программ для ЭВМ, а так же любые электрические цепи или электрическая сеть.

(приложение 1 рис.4).


5. Схема цепей дежурного освещения

Схема цепей дежурного освещения тепловоза ТЭМ2 тоже представлена в виде графа.

(приложение 1 рис.5).


6. Схемы авиалиний

Схемы авиалиний представлены в виде графов.

(приложение 1 рис.6).

7. Участок московского Метрополитена.

Один из участков московского Метрополитена.

Он нарисован тоже в виде графа.

(приложение 1 рис.7).


8. Социограммы

Социограммы (в психологии при исследовании межличностных отношений в группах).

Она тоже представлена с помощью графа.

(приложение 1 рис.8).


9. Схема железных дорог

Схема железных дорог.

Вершины – железнодорожные станции, а рёбра – железнодорожные пути.

(приложение 1 рис.9).

10. Созвездия

Графы есть и на картах звездного неба.

Это созвездия.

(приложение 1 рис.10).


11. Химия. Теория графов позволяет точно определить и пояснить некоторые основные понятия химии: структуру, конфигурацию, конформацию, квантовомеханическое и статистико-механическое взаимодействия молекул, определять число теоретически возможных изомеров органических соединений, позволяет анализировать некоторые химические превращения, описывать химические реакции, определять некоторые свойства молекул.

Молекулярный граф — связный неориентированный граф, находящийся во взаимно-однозначном соответствии со структурной формулой химического соединения таким образом, что вершинам графа соответствуют атомы молекулы, а рёбрам графа — химические связи между этими атомам. (приложение 1 рис.11).

12. Математика. Немало поводов для появления графов и в математике. Наиболее очевидный пример – любой многогранник в трёхмерном пространстве.

Например, вершины и рёбра куба можно рассматривать как вершины и рёбра графа. При этом мы отвлекаемся от того, как расположены элементы куба в пространстве, оставляя лишь информацию о том, какие вершины соединены рёбрами. На рисунке 12 показаны три способа изобразить один и тот же граф - трёхмерного куба.

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

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

13. Физика. Одной из наиболее сложных и утомительных задач для радиолюбителей считается конструирование печатных схем.

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

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