02. Графические модели. Графы, деревья

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

Графические модели

Посмотрите на представленные ниже описания Мирового океана.

Общепризнанными океанами считаются Атлантический, Индийский, Тихий, Северный Ледовитый и Южный. Площадь Тихого океана составляет 168,7 млн км². Атлантический океан имеет площадь 85 млн км². Северный Ледовитый океан самый небольшой, он занимает около 15 млн км². Площадь Индийского океана составляет 70,6 млн км². Южный океан омывает Антарктиду, он занимает 20,3 млн км².

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

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

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

Взглянув на рисунок, диаграмму или схему, можно сразу увидеть основные связи и зависимости и быстро принять решение.

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

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

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

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

Карта — это графическая информационная модель. Кроме карт, к графическим информационным моделям относятся рисунки, фотографии, чертежи, схемы, графики, диаграммы, графы.

Любой рисунок — это модель. Неважно, сделан он профессиональным художником или совсем маленьким ребёнком, который пытается изобразить увиденное, например радугу или маму. Рисунок отражает наиболее важные моменты того, что хочет изобразить автор, либо то, как автор это видит.

Например, человечек на знаке пешеходного перехода не похож на реального человека, но это не имеет значения.

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

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

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

То есть картина (схема, графическая модель) всегда подчиняется тем целям, ради которых она создана.

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

Сделанный вами набросок на полях тетради или лента с фото в социальной сети — это графические информационные модели.

Рассмотрим термины «чертёж» и «схема». На первый взгляд может показаться, что это синонимы.

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

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

Главная цель схемы — показать самое существенное и принципиальное в изучаемом объекте.

Примером схемы является разметка футбольного поля с указанием ворот, положения игроков на поле, направлением удара.

Чертёж — выполненное с помощью инструментов графическое изображение, которое максимально отражает конструкцию объекта и его размеры.

Чертёж должен быть выполнен в точном соответствии с правилами черчения.

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

Точный чертёж нужен будет и мастеру, который делает ремонт, чтобы рассчитать необходимое количество стройматериалов. И уж тем более строителю, который создаёт новый строительный объект.

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

На рисунке 11 вы видите схему метро. Если мы внимательно посмотрим на карту города, то увидим, что реальное расположение станций метро отличается от тех, что указаны на схеме. Схема создаётся для того, чтобы пассажир мог легко ориентироваться в ветках и направлениях. Конечно же, схема не отражает реальное расположение станций и расстояние между ними.

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

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

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

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

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

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

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

В химии по графику можно проследить изменение скорости химической реакции в зависимости от времени.

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

В курсе истории и обществознания по графикам можно увидеть и проанализировать изменение численности населения Земли либо отдельно взятого государства.

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

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

Диаграммы бывают разные. Первая диаграмма (рис. 21) называется столбчатой диаграммой, или гистограммой. Такие диаграммы, как правило, используют для сравнения величин.

Круговые диаграммы (рис. 22) полезны для иллюстрации соотношения величин, которые вместе образуют 1 или 100 %. Например, по круговой диаграмме мы можем проанализировать, какую часть занимают разные страны в мировом рынке добычи нефти.

Графы

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

В переводе с греческого граф — «пишу», «описываю». Родственные слова — «график», «графика», «графоман» (тот, кто любит много писать), «графология» (наука, изучающая связь личности и почерка). Описывая какие-либо объекты, мы часто используем слова с корнем «граф»: биография, география, фотография и т. п.

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

Граф — схема, отображающая объекты и связи между ними.

Граф состоит из вершин, соединённых линиями — рёбрами. Вершины обозначают объекты, а рёбра — связи между объектами.

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

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

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

Важно, что размеры и форма вершин или рёбер графа не имеют значения. Это именно схема, а не чертёж. Гениальность Эйлера в решении задачи о мостах заключается как раз в том, что он догадался, что ни размеры островов, ни длины мостов, ни их форма не важны. Поэтому указанные объекты можно изобразить в виде точек и отрезков.

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

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

Обычно граф обозначают G (V, E), где V — множество вершин, E — множество рёбер (дуг).

Неориентированный граф — граф, в котором вершины соединяются рёбрами.

Ориентированный граф (орграф) — граф, в котором вершины соединены дугами.

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

Число рёбер, соединяющих две фиксированные вершины, может быть произвольным: оно определяется характером связей между объектами, соответствующими этим вершинам. Однако каждое ребро связывает не более двух вершин.

Вершины, которым не соответствует ни одно ребро, называются изолированными.

Взвешенный граф — граф, вершины и/или рёбра (дуги) которого имеют вес.

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

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

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

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

Такие графы нередко составляются для решения транспортной задачи — задачи об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления. Фактически под названием «транспортная задача» понимается достаточно широкий круг задач, которые сводятся к поиску оптимального пути передвижения, при котором обеспечиваются минимальная стоимость либо минимальные затраты времени, либо минимальное расстояние.

Решением проблемы решения транспортной задачи впервые заинтересовался французский математик Гаспар Монж в 1781 году. Многие учёные предлагали различные методы решения задачи. Однако точный законченный метод решения был разработан во время Великой Отечественной войны советскими математиками Канторовичем и Гавуриным. Поэтому нередко транспортную задачу называют задачей Монжа — Канторовича.

Ещё одной интересной и популярной задачей является задача коммивояжёра. В XIX и XX веке по городам ездили коммивояжёры, сейчас их называют торговыми агентами. Приезжая в очередной город, коммивояжёр ходил по домам и предлагал людям купить разные товары. После этого он отправлялся в следующий город. Чем больше городов посетит коммивояжёр, тем больше он сможет заработать, но при этом ему необходимо вернуться домой. Поиск оптимального пути и называется задачей коммивояжёра. Если представить сеть городов в виде графа, то задачу коммивояжёра можно сформулировать так: найти самый короткий путь между вершинами, чтобы посетить каждую вершину хотя бы по одному разу и вернуться в начальную вершину.

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

Количество рёбер полного графа, у которого вершин, можно определить по формуле:

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

Путь — это последовательность рёбер (дуг), по которым можно перейти из одной вершины в другую.

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

Связный граф — граф, в котором от любой его вершины можно по рёбрам перейти к любой другой вершине.

Петлёй называется линия (ребро или дуга), выходящая из некоторой вершины и входящая в неё же. На рисунке 35 петля есть у вершины .

Цикл — цепь, начальная и конечная вершины которой совпадают. В приведённых графах (рис. 35) цикл объединяет вершины .

Сеть — граф с циклом.

В настоящей рыболовной сети волокна или леска образуют замкнутые ячейки, с которыми можно ассоциировать циклы.

Схема взаимодействия компонентов компьютера, с которой вы знакомились в 7-м классе, представляет собой сетевой граф (рис. 36).

Компьютерную сеть также можно представить в виде графа, вершины которого — узловые компьютеры, рёбра — каналы связи (рис. 37). В графе, иллюстрирующем Всемирную паутину, можно в качестве вершин использовать адреса веб-страниц, находящихся в сети, а в качестве рёбер — гиперссылки, связывающие веб-страницы (рис. 38).

Направленный ациклический граф — ориентированный граф, не имеющий циклов (рис. 39).

В этом графе вершина является начальной вершиной, это источник графа (единственная вершина графа, в которую не входит ни одна дуга, есть только выходящие из неё дуги).

Вершина — конечная вершина (сток) графа, дуги в эту вершину входят, но нет ни одной дуги, выходящей из вершины .

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

Название выбрано неслучайно: в каждую вершину от главной вершины, называемой корнем, ведёт только один путь. Так же вода от корня настоящего дерева только единственным образом достигает каждого листочка. Между любыми двумя вершинами дерева существует единственный путь.

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

Рассмотрим элементы древовидного графа на примере схемы управления учебным заведением (рис. 42).

Корень дерева — главная вершина дерева, расположенная на самом верхнем уровне. Корнем дерева на рисунке 42 является вершина Директор.

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

В графах древовидной структуры реализован принцип «один ко многим», согласно которому у каждого потомка есть только один предок. В показанном графе предки есть у всех вершин, кроме вершины Директор: предком вершин Главный бухгалтер и Заместитель директора является вершина Директор, предком вершины Бухгалтер является вершина Главный бухгалтер, предком вершин Методист и Организатор является вершина Заместитель директора.

Вершины, у которых нет потомков, называют листьями дерева. На рисунке 42 листьями являются вершины Бухгалтер, Методист и Организатор.

Любая вершина дерева вместе со всеми своими потомками называется поддеревом.

Уровень вершины дерева — длина пути от корня до вершины. В рассматриваемом примере вершина Директор (корень дерева) имеет нулевой уровень, вершины Главный бухгалтер и Заместитель расположены на первом уровне. Три вершины (Бухгалтер, Методист и Организатор) находятся на втором уровне.

Высота дерева — максимальный уровень вершин, образующих дерево. В нашем примере высота дерева равна двум.

Графы являются схемами, которые используются в различных сферах нашей жизни (рис. 43).

Любая транспортная сеть — не что иное, как граф, в котором транспортные узлы являются вершинами графа, а дороги (например, автомобильные или железнодорожные магистрали) — рёбрами графа.

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

В виде связного неориентированного графа изображается структура химического вещества: вершинам графа соответствуют атомы и молекулы, а рёбрам графа — химические связи между атомами.

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

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

Рассмотрим тип задач, встречающихся в экзаменационных материалах по информатике.

Задача 1

На рисунке 44 представлен ориентированный граф. Необходимо найти количество различных путей, ведущих из вершины в вершину .

Решение

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

Подсчитаем количество путей, ведущих из вершины в каждую из вершин (рис. 45):

• в вершину можно попасть только из , это один путь;

• в вершину ведут пути — из и из ;

• в ведут пути — из и из ;

• в таким образом получим путей: из вершины и из вершины .

Ответ: .

Немного изменим условие задачи.

Задача 2

Необходимо найти количество различных путей, ведущих из вершины в вершину и проходящих через .

В этом случае зачеркнём дуги, путь по которым не проходит через вершину : это дуга из в и дуга из в (рис. 46). В остальном ход решения такой же.

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

Ответ: .

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

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

Графы позволяют выбрать стратегически верное решение для достижения победы. В ответвлении вы можете познакомиться с графическим решением задачи на выбор стратегии игры.

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

Полезные ссылки

Список рекомендованных учебников

Проверь себя

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

2. В чём отличие схем и диаграмм?

3. Что такое граф?

4. Какой граф называется ориентированным?

5. Какой граф называется взвешенным?

6. При решении каких практических задач могут использоваться графы?

Список использованных источников:

Изображения используются согласно лицензии Shutterstock / FOTODOM

Иллюстратор Шакуртова Ю. А.

Моушн-дизайнер Лопатин М. С.

Источник: wikipedia.org / название: Иллюстрация к «Сказке о царе Салтане». Купцы / атрибуция: public domain, автор: Иван Яковлевич Билибин

Источник: wikipedia.org / название: Yellow-Red-Blue / атрибуция: public domain, автор: Wassily Kandinsky

Источник: wikipedia.org / название: Königsberg 1651 / атрибуция: public domain, автор: Merian-Erben

Источник: wikipedia.org / название: Figure 1 from Solutio problematis ad geometriam situs pertinentis by Leonhard Euler / атрибуция: public domain, автор: Leonhard Euler

Источник: wikipedia.org / название: Portrait of Gaspard Monge / атрибуция: public domain, автор: François-Seraphin Delpech

Источник: wikipedia.org / название: Nobel laureates Leonid Kantorovich / атрибуция: https://creativecommons.org/licenses/by/3.0/deed.ru, автор: Андрей Богданов

Источник: wikipedia.org / название: Portrait of Leonard Euler / атрибуция: public domain, автор: Jakob Emanuel Handmann