Інформаційні моделі на графах
Головна | Інформатика та інформаційно-комунікаційні технології | Планування уроків і матеріали до уроків | 6 класи | Планування уроків на навчальний рік (ФГОС) | Інформаційні моделі на графах
Презентація «Схеми»
Інформаційні моделі на графах
Наочним засобом представлення складу та структури системи є граф. Граф складається з вершин. пов'язаних лініями. Якщо лінія спрямована (зі стрілкою), то вона називається дугою; лінія ненаправленная (без стрілки) називається ребром. Лінія, що виходить з деякої вершини і входить в неї ж, називається петлею. Вершини можуть зображуватися колами, овалами, точками, прямокутниками і т. Д.
Якщо об'єкти деякої системи зобразити вершинами, а зв'язки між ними - лініями, то ми отримаємо інформаційну модель даної системи в формі графа.
Раніше ми розглядали графи - схеми відносин, що відображають наші зв'язки між об'єктами.
Наприклад, граф, що відображає ставлення «переписуються» між об'єктами класу «діти», може виглядати, як показано на рис. 44.
Ставлення «переписуються» ( «пишуть листи один одному») є двостороннім (симетричним). Тому відповідні вершини з'єднані лініями без стрілок (ребрами).
Граф називається неорієнтованим. якщо його вершини з'єднані ребрами.
Шлях по вершинах і ребрах графа, що включає будь-ребро графа не більше одного разу, називається ланцюгом.
Приклад ланцюга: Юра - Аня - Вітя - Коля (див. Рис. 44).
Ланцюг, початкова і кінцева вершини якої збігаються, називається циклом.
Приклад циклу: Аня - Коля - Вітя - Аня.
Інакше виглядає граф, що відображає ставлення «пише листи» між тими ж об'єктами класу «діти». Лінії зі стрілками (дуги) надають йому зовсім інший зміст (рис. 45).
Граф називається орієнтованим. якщо його вершини з'єднані дугами.
Наведіть приклади ланцюга і циклу в графі на рис. 45.
Граф називається зваженим, якщо його вершини або ребра (дуги) характеризуються деякою додатковою інформацією - вагою вершини або ребра (дуги).
На малюнку 46 інформація про міста Золотого кільця представлена зваженим графом: ваги його вершин - року заснування міст, ваги ребер - відстані в кілометрах між містами.
Назвіть шляхи і цикли в графі на рис. 46.
Граф з циклами називається мережею.
На малюнку 47 в вигляді графа представлена інформаційна модель казки про Царівну-жабу.
Вершини цього графа - персонажі і предмети з казки, дуги - зв'язки між ними. На відміну від попередніх прикладів,
тут всі зв'язки різні. Тому вони підписуються поруч з відповідними дугами.
Такий граф називається семантичної мережею. Вважається, що будь-яку інформацію можна представити у вигляді семантичної мережі, на якій будуть відображені об'єкти (поняття) і зв'язку (відносини) між ними.
Ієрархія - це розташування частин або елементів цілого в порядку від вищого до нижчого. Системи, елементи яких знаходяться в стосунках «є різновидом», «входить до складу» та інших відносинах підлеглості, називаються ієрархічними системами (системами з ієрархічною структурою).
Наприклад, ієрархічну структуру має школа, тому що в ній встановлені наступні відносини підпорядкованості: директор - заступники директора - вчителі - учні.
Ієрархічну структуру мають системи, елементи яких пов'язані відношенням «входить до складу».
На малюнку 48 зображено граф ієрархічної системи, що представляє склад прикладного програмного забезпечення (ПО) комп'ютера.
Граф ієрархічної системи називається деревом. Відмінною особливістю дерева є те, що між будь-якими двома його вершинами існує єдиний шлях. Дерево не містить циклів і петель.
Зазвичай у дерева, що представляє ієрархічну систему, виділяється одна головна вершина, яка називається коренем дерева. Кожна вершина дерева (крім кореня) має тільки одного предка - позначений нею об'єкт входить в один клас верхнього рівня. Будь-яка вершина дерева може породжувати кілька нащадків - вершин, відповідних класів нижнього рівня. Такий принцип зв'язку називається «один до багатьох». Вершини, які не мають породжених вершин, називаються листям.
Деревоподібними є схеми відносин «є різновидом», використовувані для наочного уявлення класифікації об'єктів (рис. 49).
Ієрархію легко зобразити «драбинкою» - у вигляді багаторівневого списку. Об'єкти одного рівня ієрархії розташовуються на одному рівні в списку. Чим нижче рівень ієрархії, тим правіше знаходиться відповідний рівень списку:
рептилії
черепахи
Крокодили
клювоголовие
лускаті
ящірки
змії
За ієрархічним принципом організована система зберігання файлів у зовнішній пам'яті комп'ютера. Операційна система дозволяє отримати на екрані комп'ютера зображення файлової системи у вигляді дерева (рис. 50).
Родинні зв'язки між членами сім'ї зручно зображувати за допомогою схеми, званої генеалогічним або дерево їхнього роду. Зображати генеалогічне дерево можна в будь-якому напрямку - це справа смаку розробника моделі.
Використання графів при вирішенні задач
Графи зручно використовувати при вирішенні деяких класів задач.
Скількома способами можна розсадити в ряд на три стільці трьох учнів? Виписати всі можливі випадки.
Вирішення цього завдання найзручніше представити у вигляді дерева. За його кореневу вершину візьмемо довільну точку площини О.
На перший стілець можна посадити будь-якого з трьох учнів - позначимо їх А, В л С. На схемі це відповідає трьом гілкам, що походить із точки О (рис. 51).
Посадивши на перший стілець учня А, на другий стілець можна посадити учня В або С. Якщо ж на перший стілець сяде учень В, то на другий можна посадити А чи С. Якщо на перший стілець сяде С, то на другий можна буде посадити А чи В. Це відповідає на схемі двом гілкам, що походить із кожної вершини першого рівня (рис. 52).
Очевидно, що третій стілець в кожному випадку займе залишився учень. Це відповідає одній гілці дерева, яка «виростає» на кожній з попередніх гілок (рис. 53).
Випишемо всі шляхи від вершин першого рівня до вершин третього рівня: А-В-Су А-С-В, В-А-С, В-С-А, С-А-Б, С-В-А. Кожен з виписаних шляхів визначає один з варіантів розсаджування учнів на стільці. Так як інших шляхів немає, то шукане число способів - 6.
Дерево можна не будувати, а то й потрібно виписувати всі можливі варіанти, а потрібно просто вказати їх число. В цьому випадку міркувати потрібно так: на перший стілець можна посадити одного з трьох чоловік, на другий - одного з двох, що залишилися, на третій - одного залишився: 3-2-1 = 6.
Щоб принести Царю-батюшці молодильні яблука, повинен Іван-царевич знайти єдиний вірний шлях до чарівного саду. Зустрів Іван-царевич на розвилці трьох доріг старого ворона і ось які поради від нього почув:
1) йди зараз по правій стежці;
2) на наступній розвилці не вибирають праву стежку;
3) на третьому розвилці не ходи по лівій стежині.
Пролітав повз голуб шепнув Івану-царевичу, що тільки одна порада ворона вірний і що обов'язково треба пройти стежками різних напрямків. Наш герой виконав завдання і потрапив в чарівний сад. Яким маршрутом він скористався?
Позначимо ліву, середню і праву стежки відповідно Л, С і П. Можливі маршрути представимо у вигляді графа. При цьому підказки ворона відзначимо більш «жирними» ребрами. Так як тільки одна порада ворона вірний, то на графі йому буде відповідати маршрут, який має одне «жирне» ребро. Цей маршрут позначений додаткової пунктирною лінією (рис. 54).
Запитання і завдання
1. Наведіть 2-3 приклади схем, з якими ви стикаєтеся в повсякденному житті. Інформаційними моделями яких об'єктів є ці схеми?
2. На кожному поверсі в вашій школі повинен бути план евакуації при пожежі. Знайдіть і вивчіть його. Які об'єкти представлені на цій схемі?
3. У яких сферах діяльності неможливо обійтися без карт - інформаційних моделей поверхні Землі?
4. Визначте казку, для якої наступний граф визначає відносини між персонажами.
5. З різних сторін на пагорб піднімаються три стежки і сходяться на вершині. Перерахуйте безліч маршрутів, за якими можна піднятися на пагорб і спуститися з нього. Вирішіть ту ж задачу, якщо вгору і вниз треба йти по різних стежках.
6. Скільки тризначних чисел можна записати за допомогою цифр 1, 3, 5 і 7 за умови, що в запису числа не повинно бути однакових цифр?