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

Храни порядок, и порядок сохранит тебя.

Латинская формула

Сети получили широкое практическое применение потому, что они являются естественным и удобным способом изображения и дальнейшего анализа различных сложных систем. Одним из первых применений сетевого изображения было создание американскими учеными баллистических ракет «Поларис» для оснащения атомных подводных лодок военно-морского флота США. В реализации этого грандиозного проекта участвовали 600 фирм из 48 штатов. Сам сетевой граф содержал 10 000 событий. В основе системы планирования и управления лежат в США система «Перт»,

Рис. 2.21. Взвешенный сетевой граф проведения комплекса работ	Рис. 2.22. Сеть Петри

 

а в нашей стране — «СПУ», широко и успешно применяют графы, так как они позволяют обрабатывать на ЭВМ проект большим количеством событий.

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

Структуру такого типа имеют, например, предприятия (его составные части: цехи, бригады, участки и т.д.), учебные заведения (колледж состоит из факультетов, которые, в свою очередь, состоят из курсов, курсы — из групп). Такой же зависимости подчинены армейские соединения (дивизия, полк, батальон, рота, взвод, отделение, отдельные солдаты). Аналогично устроена любая административно-территориальная структура: республика, области, районы, населенные пункты. По путям этих деревьев дви­жутся информационные потоки: сверху вниз — распоряжения, руководящие указания, снизу вверх — отчеты о работе, оператив­ная информация. Так как путь от листа к корню единственный, то его можно использовать для опознания компонентов системы. Например, почтовый адрес представляет собой «путь в дереве», аналогичный административно-территориальному. В разделе «Кому» указывается страна, республика, область, район, населенный пункт, улица, дом, квартира. Аналогично классифицируют объекты в любой науке. Получаемая классификация служит примером иерархической структуры.Например, в биологии: класс, отряд, семей­ство, род, вид. Соответствующий граф содержит элементы разных Уровней, корень — класс, а листья — отдельные виды животных.

Иногда связи между объектами образуют не дерево, но все же их можно представить в виде графа. Это бывает в тех случаях, когда, например, происходит подчинение не одному, а нескольким независимым службам (соподчинение между собой).

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

Рис. 2.23. Блок-схема иерархической структуры: учебник

Генеалогическое древо графа Льва Николаевича Толстого имеет вид, изображенный на рис. 2.25.

Бинарный поиск.Бинарные деревья применяются в информатике для одной из самых распространенных в прикладных науках операций — поиску. К нему прибегают, когда необходимо найти в некотором упорядоченном массиве (множестве) определенную информацию. Например, в телефонном справочнике — номер какого-нибудь абонента, в словаре — определенное слово, в файле — сведения о зарплате сотрудников некоторого предприятия, сведе­ния о зарплате отдельного работника и т.д.

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

 

Рис. 2.25. Генеалогическое древо Л. Н.Толстого

 

 

Рис. 2.26. Блок-схема иерархического представления видов вычислительных машин

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

Пусть надо найти дубликаты всех чисел в некотором списке. Можно применить сравнение каждого числа с предшествующим на предмет «был — не был». Но тогда необходимо большое число сравнений. Использование бинарных деревьев (БД) укорачивает процедуру сравнения. Считывается новое число и помещается в узел — будущий корень нового БД. Каждое последующее число из списка сравнивается с числом в корне БД. Если эти значения совпадают, то дубликат найден, если число меньше корня, то процесс продолжается в правом поддереве, если больше — в левом поддереве.

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

На процедуре бинарного поиска с использованием графа-дерева основана работа ЭВМ с базой данных. Информация о базе может быть представлена несколькими способами, в том числе матричным. Так называемые реляционные базы хранят различную информацию в форме таблиц, причем порядок строк и столбцов задается при вводе данных. В базах возможна дли­тельная работа с информацией, ее реорганизация и обновление. С помощью автоматического поиска данных происходит их отбор на основании запроса по определенным характерным признакам.

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