Системы, графы взаимодействия.

⇐ ПредыдущаяСтр 3 из 3

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

Система - совокупность взаимосвязанных между собой объектов. Составные части системы называются элементами или компонентами.

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

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

В рамках современного понимания информационной системы компьютер является основным инструментом обработки информации.

В работе информационной системы можно выделить следующие этапы:

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

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

3. Обработка данных - процессы, вследствие которых на основании прежде накопленных данных формируются новые виды данных: обобщающие, аналитические, рекомендательные, прогнозные. Производные данные тоже можно обрабатывать, получая более обобщенные сведения.

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

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

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

Графы — это специальная математическая абстракция, которая позволяет обсуждать и анализировать широкий круг вещей в реальном мире. Это такая же абстракция, как, например, числа. Числа естественно возникают при подсчёте яблок у Пети, массы сахара в чайной ложке и температуре воздуха за окном. Изучая числа, вы сталкиваетесь с новыми определениями: вам объясняют, что называется квадратным корнем числа, что такое делители числа. Далее, про числа вам рассказывают в школе разные теоремы: например, формулу квадрата суммы двух чисел, теорему о единственности разложения числа на простые множители. Наконец, на программировании вы изучаете алгоритмы, связанные с числами: алгоритм Евклида нахождения НОД, алгоритм проверки числа на простоту. Всё это ждёт нас и при изучении графов.

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

Рис.3 – Схема метрополитена города Киева

Основное, что мы видим на ней — это станции и перегоны между ними.

Теперь взглянем на участок Москвы с автомобильными дорогами (скриншот сделан с сайта Яндекс.Карты).

Рис. 4 – Фрагмент карты Москвы

Можно описывать сеть дорог как набор перекрёстков, некоторые из которых соединены участками дорог.

Наконец, посмотрим на пример цепи питания в биологии.

Рис. 5 – Цепь питания

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

Итак, графом называется набор вершин и набор рёбер. Каждое ребро соединяет две вершины.

Степенью вершины называется количество рёбер, концом которых она является. Например, в графе метрополитенов большинство станций имеют степень 2, а конечные станции имеют степень 1. В графе славянской языковой группы вершина «западнославянский язык» имеет степень 4.

Рис. 6 – Пример графа путь

На рисунке выше вершина A имеет степень 3, вершина B имеет степень 4. Вершина H имеет степень 0 и называется изолированной вершиной.

Виды графов и пути в графах

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

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

Путём в графе называется любая последовательность вершин, в которой каждые две соседние вершины соединены ребром. На рисунке выше A → C → B → G — это путь из вершины A в вершину G. Есть и более короткий путь из A в G: путь A → B → G. Длиной пути называется количество рёбер в нём. Таким образом, кратчайший путь из A в G имеет длину 2.

Циклом в графе называют путь, у которого начальная и конечная вершина совпадают. На рисунке выше путь A → C → B → D → A является циклом.

Если вы внимательно посмотрите на определение пути и цикла, то увидите, что путём так же можно считать последовательность A → D → B → D → B, а последовательность F → E → F удовлетворяет определению цикла. Чтобы исключить такие патологические ситуации из рассмотрения, обычно вводят понятия простого пути и простого цикла. Простой путь — это путь, в котором нет повторяющихся рёбер. Простой цикл это цикл, который является простым путём.

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

1. между любыми двумя вершинами набора существует путь;

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

Всякий неориентированный граф разбивается на свои компоненты связности. На рисунке выше имеются три компоненты связности: {A, B, C, D, G}, {E, F} и {H}. Граф, у которого только одна компонента связности, называется связным. Граф, у которого более одной компоненты связности, называется несвязным. На рисунке выше изображён несвязный граф.

В ориентированном графе путём называется любая последовательность вершин, в которой соседние вершины соединены ребром, и это ребро идёт «слева направо» (в нужную сторону). Например, на рисунке ниже A → B → C → D является путём, а A → D → C → B — не является (потому что в графе нет рёбер A → D и C → B).

Рис. 7 – Пример графа цикл

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

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

Рис. 8 – Пример графа

Между вершинами A и B, а также между вершинами C и D проведены кратные рёбра. Заметим, что между вершинами E и F кратных рёбер нет, поскольку ориентированные рёбра считаются кратными, только если у них совпадают начала и концы с учётом ориентации. Рёбра, исходящие из вершин G и H, называются петлями. Про некоторые графы специально говорят «графы без петель и кратных рёбер», чтобы подчеркнуть, что в них не встречаются ситуации, аналогичные изображённым выше.

Деревья

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

Рис. 9 – Пример графа дерево

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

Ещё одно удивительное свойство деревьев — это связь между количеством вершин и количеством рёбер. Договоримся обозначать буквой V количество вершин (от англ. vertex «вершина»), а буквой E — количество рёбер (от англ. edge «ребро»). Например, у дерева на рисунке выше V = 11, E = 10. Мы видим, что для графа на рисунке E = V − 1.

Чтобы понять, всегда ли это будет верно, рассмотрим висячие вершины. Висячей вершиной называется вершина степени 1. На рисунке выше висячими являются вершины A, C, F, G, H, J и K. Заметим, что в дереве, в котором есть хотя бы две вершины, всегда есть хотя бы одна висячая вершина. Действительно, выберем произвольную вершину дерева и пойдём из неё гулять по рёбрам дерева в произвольном направлении, не возвращаясь назад. Поскольку циклов в дереве нет, то с каждым шагом мы будем посещать всё новые и новые вершины и в какой-то момент придём в вершину, из которой никуда пойти нельзя. Эта вершина и будет висячей.

Правда ли, что если в дереве есть хотя бы две вершины, то в нём есть хотя бы две висячие вершины? А правда ли, что если в дереве есть хотя бы три вершины, то в нём есть хотя бы три висячие вершины?

Теорема. В любом дереве E = V − 1.

Доказательство. Как мы выяснили, если в дереве хотя бы две вершины, то в нём есть хотя бы одна висячая вершина. Выберем её и удалим из графа её и ребро, за которое она присоединена к графу. При этом количество вершин и рёбер уменьшится на единицу. С новым графом проделаем ту же операцию. В конце концов, когда мы удалим всё, что можно, мы получим граф из одной вершины. Для него V = 1, E = 0, т.е. E = V − 1. Значит, и в исходном дереве выполнялось E = V − 1.

Контрольные вопросы

Что представляет собой модель?
Перечислите этапы компьютерного математического моделирования.
Как классифицируются математические модели?
Что представляет собой имитационное моделирование?
Назовите виды имитационного моделирования?
Что такое «САПР»?
Как классифицируется САПР?
Дайте определение понятию система.
Что представляет собой граф?
Какие бывают виды графов?

Список использованной литературы

1. Цветкова М.С., Великович Л.С. Информатика и ИКТ: учебник. – М.: Издательский центр «Академия», 2012, 1.1, 1.3.

2. Бондаренко Е. А., Журин А. А., Милютина И. А. Технические средства обучения в современной школе: Пособие для учителя и директора школы. / Под ред. А. А. Журина. – М.: «ЮНВЕС», 2004. – 416 с.

3. Захарова И. Г. Информационные технологии в образовании: Учебн. пособие для высш. учебн. заведений. – М.: Издательский центр «Академия», 2005. – 192 с.

4. Информатика. 10-11 класс / Под ред. Н. В. Макаровой. – СПб.: Питер, 2004. – 300 с.: ил.

5. Информатика: Учеб. пособие для студ. сред. проф. образования / Е. А. Колмыкова, И. А. Кумскова. – М.: Издательский центр «Академия», 2005. – 416 с.

6. Угринович Н. Д. Информатика и информационные технологии. Учебник для 10 – 11 классов. / Н. Д. Угринович. – 4-е изд. – М.: БИНОМ. Лаборатория знаний, 2007. – 511 с.: ил.

7. Оре О. Теория графов. — М.: Наука, 1968. — 336 с.

8. Уилсон Р. Введение в теорию графов. — М.: Мир, 1977. — 208 с.

9. Харари Ф. Теория графов. — М.: Мир, 1973.

10. Кормен Т. М. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 1296.

11. Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997.

12. Касьянов В. Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. — С. 1104.

Дата добавления: 2020-11-15; просмотров: 134; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 23

Мы поможем в написании ваших работ!