Информационные модели на графах

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

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

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

Например, граф, отражающий отношение «переписываются» между объектами класса «дети», может выглядеть, как показано на рис. 44.

Отношение «переписываются» («пишут письма друг другу») является двухсторонним (симметричным). Поэтому соответствующие вершины соединены линиями без стрелок (рёбрами).

Граф называется неориентированным, если его вершины соединены ребрами.

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

Пример цепи: Юра — Аня — Витя — Коля (см. рис. 44).

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

Пример цикла: Аня — Коля — Витя — Аня.

Иначе выглядит граф, отражающий отношение «пишет письма» между теми же объектами класса «дети». Линии со стрелками (дуги) придают ему совершенно иной смысл (рис. 45).

Граф называется ориентированным, если его вершины соединены дугами.

Приведите примеры цепи и цикла в графе на рис. 45.

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

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

Назовите пути и циклы в графе на рис. 46.

Граф с циклами называется сетью.

На рисунке 47 в виде графа представлена информационная модель сказки про Царевну-лягушку.

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

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

Источник

Что такое взвешенный граф в информатике

Вы будете перенаправлены на Автор24

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

Взвешенный граф

Под взвешенным графом понимается граф, у которого рёбрам соответствуют некоторые весовые параметры. То есть каждому ребру (дуге) поставлено в соответствие некое числовое значение, которое называется длина дуги (или вес, стоимость). Обычные графы (не взвешенные) тоже возможно представить в виде взвешенных, если считать, что все их рёбра обладают весом равным единице. Под длиной пути во взвешенном графе понимается суммарная длина (вес) рёбер, составляющих данный путь. Расстоянием между вершинами считается дистанция самого короткого по весу пути. На рисунке один приведён пример взвешенного графа и там можно видеть, что расстояние между вершинами a и d равняется шести. То есть это путь с наименьшим суммарным весом (от вершины a и далее b, c, d).

Рисунок 1. Образец взвешенного графа. Автор24 — интернет-биржа студенческих работ

Эйлеровы и гамильтоновы графы

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

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

Эти формулировки появились в 1735-ом году в работе Эйлера, где он искал решение задачи о Кёнигсбергских мостах и там первым привёл термин граф. На рисунке два изображена схема, где представлены семь мостов в городе Кёнигсберг (сегодня это Калининград). По условиям задачи требуется пересечь каждый из мостов только один раз и выполнить возврат в начальную точку С. Так как обход мостов завешается в начальной точке маршрута и есть условие однократного пересечения каждого моста, то такой маршрут можно считать простым циклом, который содержит все рёбра графа. Позже подобные циклы получили название эйлеровых, а графы, в составе которых есть такие циклы, назвали эйлеровыми графами.

Готовые работы на аналогичную тему

Рисунок 2. Задача Эйлера о Кёнигсбергских мостах. Автор24 — интернет-биржа студенческих работ

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

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

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

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

Источник

Информационные модели на графах. Использование графов при решении задач

Урок 22. Информатика 6 класс ФГОС

В данный момент вы не можете посмотреть или раздать видеоурок ученикам

Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.

Получите невероятные возможности

Конспект урока «Информационные модели на графах. Использование графов при решении задач»

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

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

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

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

Следующий вид графических средств представления информации – схемы.

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

Есть ещё один вид графических средств – это графы.

Сегодня на уроке мы узнаем:

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

Граф — это группа объектов со связями между ними.

Объекты представляются как вершины графа, а связи — это линии соединяющие вершины.

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

В данном примере вершины графа – это отдельные ребята, а связи – это процесс «пишут друг другу SMS».

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

Разберёмся более подробно со связями, то есть с линиями, соединяющими вершины графа.

Если линия, соединяющая вершины графа направленная, то есть со стрелкой, то она называется дугой.

То есть дугой называется направленная линия, соединяющая вершины графа.

Если линия ненаправленная, то есть, нет стрелки, то эта линия называется ребром.

Ребро – это ненаправленная линия, которая соединяет вершины графа.

Если линия выходит из некоторой вершины и входит в неё же, то эта линия называется петлёй.

Петля – это линия, которая выходит из некоторой вершины и входит в нее же

Вернёмся к примеру, с шестиклассниками. Здесь система – это ученики шестого класса в какой-то школе. Мы, объекты этой системы (т.е. отдельных ребят) изобразили вершинами, и соединили вершины ненаправленными линиями (рёбрами). Ребра в данном случае являются двухсторонними отношениями, потому что ребята пишут SMS-ки друг другу.

Мы получили информационную модель рассматриваемой системы в форме графа.

Рассмотрим виды графов.

Если вершины графа соединены рёбрами, то такой граф называется неориентированным.

Рассмотрим пример: Таня написала SMS Никите, Никита ответил Тане, Таня написала Маше, Маша ответила Тане, Никита написал Маше. Здесь ребята отвечали друг другу на смски.

Данное отношение называется цепью графа.

Цепь графа – это путь по вершинам и рёбрам графа, который включает любое ребро не меньше одного раза.

Если в цепи начальная и конечная вершины совпадают, то такая цепь называется циклом.

Например, Таня написала SMS Никите, Никита – Маше, Маша – Платону, а Платон написал Тане.

Здесь цикл – это цепь Таня – Никита – Маша – Платон – Таня.

Далее, рассмотрим следующий вид графа.

Если вершины графа соединены дугами (стрелками), то такой граф называется ориентированным.

В нашем примере цепь будет выглядеть следующим образом: Таня написала SMS Никите, Никита – Маше, Маша – Платону. То есть СМС-ки были без ответа.

Рассмотрим следующий пример:

Город Москва основан в 1147 году, город Санкт-Петербург основан в1703 году. Расстояние от Москвы до Санкт-Петербурга 713 км. Год основания города Тверь 1135 год, расстояние от Москвы до Твери 175 км. Ярославль основан в 1010 год, расстояние от Москвы до Ярославля 272 км. Город Смоленск основан в 863 году, а расстояние от Москвы до Смоленска 400 км.

Мы получили взвешенный граф.

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

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

Помните сказку о царе Солтане? Давайте построим граф по отрывкам из сказки.

К морю лишь подходит он,

Вот и слышит будто стон.

Бьётся лебедь средь зыбей,

Коршун носится над ней;

Но как раз стрела запела,

В шею коршуна задела —

Коршун в море кровь пролил,

Лук царевич опустил;

Смотрит: коршун в море тонет

И не птичьим криком стонет,

Лебедь около плывёт,

Злого коршуна клюёт,

Молвит русским языком…

Вот открыл царевич очи;

Отрясая грёзы ночи

И дивясь, перед собой

Видит город он большой,

Мать и сын идут ко граду.

Лишь ступили за ограду,

Пышный двор встречает их;

Все их громко величают

И царевича венчают

Княжий шапкой, и главой

Возглашают над собой…

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

Следующий вид графа, называется дерево.

Дерево – это граф с иерархической системой, где Иерархия – это структура распределения частей целого от высшего к низшему. А Иерархическая система – это система, части которой находятся в определённых отношениях. К отношениям иерархической системы относятся «является разновидностью», «входит в состав» и другие «отношения подчинённости».

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

Периодическая система элементов в неё состав входят металлы и неметаллы. В свою очередь металлы делятся на 2 группы – группа 1 и группа 2, неметаллы делятся также на 2 группы – группа 5 и группа 6 и так далее. В отличие от остальных графов дерево не содержит циклов и петель, так как между любыми двумя его вершинами существует только один путь.

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

Следующий вид древовидного графа с отношением «является разновидностью» применяется для представления классификации объектов.

Например, разновидностями отряда «Насекомые» являются: Прямокрылые к ним относятся кузнечики, сверчки. Полужёсткокрылые – к ним относятся клопы, Чешуекрылые к ним относятся бабочки и Стрекозы.

Некоторые виды задач удобно решать с помощью графов.

Давайте решим одну из задач.

В коробке три шарика: жёлтый, зелёный и красный. Шестиклассница Таня со своими двумя друзьями Машей и Никитой вынимают их из коробки по одному. Сколько комбинаций выбора при этом возможно? Нужно выписать все варианты выбора.

Решение данной задачи удобно представить в виде дерева. Возьмём за корневую вершину произвольную току О., Таня может взять из коробки один из трёх шариков. Обозначим их буквами Ж, З и К. На схеме это соответствует трём ветвям, исходящим из точки О. Первый уровень в нашей задаче – это выбор Тани.

Теперь мы будем строить второй уровень графа. Второй уровень – это выбор Никиты.

Если Таня взяла жёлтый шарик, то Никита может взять зелёный или красный. Если же Таня взяла зелёный шарик, то Никита может взять жёлтый или красный. Аналогично, если Таня взяла красный шарик, то Никита может взять жёлтый или зелёный.

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

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

Если при решении задачи не нужно указывать все возможные варианты, а нужно просто указать их число, то дерево можно и не строить. Тогда рассуждаем так: Таня может взять один из трёх шариков, Никита может взять один из двух оставшихся шариков, а Маша – один оставшийся. Получаем: 3, умножить на 2, умножить на 1 получаем ответ – 6 вариантов.

Итак, сегодня на уроке мы узнали:

Граф является наглядным средством представления информации состава и структуры системы.

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

Иерархия – это структура распределения частей целого от высшего к низшему.

Иерархическая система – это система, части которой находятся в отношениях подчинённости «является разновидностью», «входит в состав» и других.

Перейдём к практической части урока.

Сегодня на уроке мы научимся:

пользоваться инструментом Надпись

добавлять (вписывать) текст в автофигуру

1-e задание. Солнечная система.

1. Открыть текстовый документ «Солнечная система.docx».

2. На картинке по информации из таблицы указать положение планет.

3. Сохранить документ под именем «Солнечная система надписи».

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

Смотрим внимательно на схему и таблицу.

Ближе всего к солнцу находится Меркурий. Обозначим на схеме Меркурий.

Выбираем вкладку Вставка, затем в группе Текст выберем инструмент Надпись, и нажимаем Нарисовать надпись, при этом указатель мыши примет форму «плюса».

Чтобы вставить надпись стандартного размера просто щёлкните в документе.

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

Перетащим надпись на нужное место.

Если надпись окружена рамкой, уберём рамку. Нажимаем Формат – Контуры фигуры – Нет контура.

Аналогично подпишем остальные планеты солнечной системы.

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

2-e задание. Поездка в автобусе.

1. Открыть текстовый документ «Поездка в автобусе.docx».

2. Дорисовать схему отношений при поездке в автобусе и подписать их названия с помощью глаголов.

3. Сохранить документ под именем «Поездка в автобусе граф».

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

Смотрим на схему. Водитель ведёт автобус.

Выбираем вкладку Вставка, в группе Иллюстрации нажимает на Фигуры. Здесь нам нужна стрелка. Соединяем вершины графа Водитель – Автобус стрелкой и, также как в первом задании, добавляем надпись.

Аналогично достраиваем всю схему.

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

Третье задание называется Арифметические выражения.

1. Открыть текстовый документ «Арифметические выражения.docx».

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

3. Сохранить документ под именем «Выражение дерево».

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

Листьями данного дерева являются числа, а остальные вершины – это арифметические операции. Листья связаны с вершинами рёбрами.

Сохраним свою работу в своей рабочей папке под именем Выражение дерево.

Таким образом, сегодня на уроке мы научились:

• пользоваться инструментом Надпись;

• добавлять (вписывать) текст в автофигуру;

Источник