Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
снови інформатики: лабораторні роботи
Лабораторна робота №8
Інформаційні моделі на графах
Мета: Ознайомитись з інформаційними моделями на графах.
Вимоги до захисту роботи: Виконати завдання лабораторної роботи. Подати звіт у електронному вигляді (формат Word) з протоколом виконання роботи. Знати відповіді на контрольні питання.
Програмне забезпечення: текстовий процесор, Калькулятор.
Теоретичні відомості:
Основні поняття
Граф – це засіб для наочного представлення складу та структури системи.
Граф складається з вершин, пов'язаних дугами або ребрами. Вершини можуть бути зображені колами, овалами, точками, прямокутниками тощо. Зв’язки між вершинами зображуються лініями. Якщо лінія направлена (тобто зі стрілкою), то вона називається дугою, якщо не направлена (без стрілки), то ребром. Прийнято вважати, що одне ребро замінює дві дуги, які направлені в протилежні сторони. Граф, в якому всі лінії направлені, називається орієнтованим графом. Дві вершини, які з’єднані дугою або ребром, називаються суміжними.
У випадку представлення інформації про склад і структуру системи у вигляді графа компоненти системи зображуються вершинами, а зв’язки між ними – лініями (дугами або ребрами).
Графи використовуються в багатьох областях практичної і наукової діяльності людей.
Приклад 1. Знайому багатьом схему ліній метрополітену можна розглядати як граф (див. рис.). Вершинами є станції метро, лінії відображають рельсовий зв’язок між станціями. Ніякої іншої інформації, крім структури метрополітену, схема-граф не містить.
Приклад 2. Граф на наступному малюнку відображає будову кулькової ручки.
Розмічений граф – це граф, в якому з вершинами або лініями пов’язана деяка додаткова інформація. Ця інформація називається вагою вершини або лінії. Найчастіше вага задається у вигляді надпису на вершині або лінії, але можливі і інші способи: форма або колір вершини, товщина, колір і тип лінії (наприклад, суцільна або пунктирна).
Вага дозволяє відобразити на графі не тільки структуру системи, але й різні властивості компонентів і зв’язків, кількісні характеристики тощо.
Приклад 3. На рисунку зображено розмічений граф, який представляє інформацію про дороги між чотирма селами. Вага вершин – назва сіл, вага ліній – довжина доріг в кілометрах. І ті, і інші задаються надписами.
Приклад 4. Всім знайомі блок-схеми є графами, які виражають структуру алгоритму. Вершини цих графів – нерівноправні. Вони діляться на декілька типів (обчислювальний блок, розгалуження, початок/кінець). Інформація про тип блоку передається через його форму (прямокутник, ромб, овал). Конкретний вміст кожного блоку задається надписом всередині цього блоку. Дуги, які виходять з вершини-розгалуження, мають позначки «так» та «ні».
Дерево – це граф, який призначений для відображення таких зв’язків між об’єктами як вкладеність, підлеглість, наслідування тощо.
Будується він наступним чином. Спочатку рисуємо «головну» вершину, яка не залежить ні від однієї іншої вершини. Ця вершина називається коренем дерева і є єдиною вершиною «1-го рівня». Далі додаємо вершини «2-го рівня». Їх може бути скільки завгодно, і всі вони обов’язково пов’язані з коренем – вершиною 1-го рівня, але не пов’язані одна з одною. На наступному кроці додаємо вершини 3-го рівня. Кожна з них буде пов’язана рівно з однією вершиною 2-го рівня і не пов’язана ні з однією іншою вершиною. До будь-якої вершини 2-го рівня може бути приєднано скільки завгодно вершин 3-го рівня (у тому числі, ні однієї). Наступний крок – додавання вершин 4-го рівня, кожна з яких буде пов’язана рівно з однією вершиною 3-го рівня і не пов’язана більше ні з чим. І так далі. На кожному кроці додаємо вершини чергового рівня, кожна з яких буде пов’язана рівно з однією вершиною попереднього рівня і не буде мати ніяких інших зв’язків.
Отриманий граф нагадує гіллястий кущ, який «росте зверху донизу»: верхні рівні мають менші номери, нижні – більші. Граф з прикладу 2, відображаючий склад кулькової ручки, є деревом. Корінь цього дерева – вершина «Кулькова ручка». Граф з прикладу 3 не є деревом.
Дерево може бути і неорієнтованим графом, але часто дерево орієнтоване, причому дуги направлені від верхніх вершин до нижніх. Верхня вершина називається предком для пов’язаних з нею нижніх вершин, а нижні вершини – нащадками відповідної верхньої вершини. На будь-якому дереві існує єдина вершина, яка не має предка, – корінь і може бути скільки завгодно вершин, які не мають нащадків, – листків. Всі інші вершини мають рівно одного предка і скільки завгодно нащадків.
Якщо не приймати до уваги направленість зв’язків, то в дереві з будь-якої вершини можна по лініям дійти до будь-якої іншої вершини, причому по одному єдиному шляху.
У вигляді дерева зручно зображати системи, в яких нижні вершини в деякому сенсі «підпорядковані» верхнім. Верхня вершина може зображати керівника, нижня – підлеглого; верхня – систему, нижні – її компоненти; верхня – множину об’єктів, нижні – підмножини, які входять до множини; верхня вершина – предка, нижні – нащадків тощо.
Класифікація та наслідування
Приклад 5. Побудувати граф класифікації геометричних об’єктів
Розв’язок: Серед геометричних об’єктів можна виділити лінії, плоскі фігури та об’ємні тіла. Серед ліній, у свою чергу, виділяють прямі, криві та ломані. Серед плоских фігур – кола, еліпси, паралелограми, трапеції тощо.
Слід відмітити, що класифікація, у даному випадку, неповна. Наприклад, відсутній первинний геометричний об’єкт, з якого все починається, – точка. Наведена класифікація не є деревом. Об’єкт «квадрат» має одразу двох предків – прямокутник і ромб. Що означає, що будь-який квадрат володіє всіма властивостями прямокутника і в той же самий час всіма властивостями ромба.
Завдання:
I. Розв’язати наступні задачі:
1. Відобразити у вигляді графа структуру наступних об’єктів:
1) велосипед; 2) черевик.
2. Нехай структура системи, яка зображується графом, наведена на рисунку. Назвіть об’єкти, які мають таку структуру.
3. На рисунку наведена схема організації танкового батальйону ФРН за станом на середину 70-х років XX ст. Ромбами позначені танки, які входять в той чи інший підрозділ. Порахуйте кількість танків в танковій роті і загальну кількість танків в батальйоні.
4. Зобразити у вигляді графа інформацію про організацію мотострілкового батальйону СРСР:
Мотострілковий батальйон армії СРСР
В середині 70-х років мотострілковий батальйон Радянської Армії нараховував 395 чоловік і мав наступну структуру. На чолі стояв командир батальйону. Йому підпорядковувалися управління і штаб, 3 мотострілкові роти, взвод зв’язку, мінометна батарея, протитанковий взвод, відділення технічного обслуговування, взвод забезпечення і батальйонний медичний пункт. В управління батальйоном входили сам комбат, замісник по політичній частині, замісник по технічній частині і технік батальйону. Штаб складався з начальника штабу, начальника зв’язку, інструктора-дозиметриста, писаря та водія бронетранспортеру. Начальник зв’язку був командиром взводу зв’язку (ще 12 чоловік). Мінометна батарея складалася з управління (10 чоловік) і двох взводів по 20 чоловік, в кожному – по 3 120-мм міномети. Протитанковий взвод складався з відділення станкових протитанкових гранатометів (8 чоловік, 2 гранатомети СПГ-9) та двох відділень протитанкових ракет (по 6 чоловік і по 2 ПТУРС у відділенні). Відділення технічного обслуговування: командир відділення, водій-автослюсар та старший механік. Взвод постачання: командир взводу, його замісник, господарська частина (3 чоловіки) і автотранспортне відділення (4 чоловіки). Батальйонний медичний пункт: начальник пункту, шофер-санітар та 2 санітари.
Мотострілкова рота складалася з управління (командир роти, замісник по політичні частині, старшина роти), кулеметного відділення і 3 мотострілкових взводів. Кулеметне відділення складалося з командира відділення, водія бронетранспортера та двох кулеметних розрахунків, у кожному кулеметник та помічник кулеметника. Мотострілковий взвод мав командира взводу, замісника командира і 3 мотострілкові відділення. В кожному відділенні: командир відділення, кулеметник, гранатометник, помічник гранатометника, старший автоматник, 3 автоматника та водій бронетранспортера.
5. Побудувати граф класифікації за наступними даними. Чи є він деревом?
Біологічна класифікація – 1
Відповідно до біологічної класифікації виділяють 3 домени (надцарства): археї, бактерії та еукаріоти. До імперії еукаріотів відносяться царства грибів, рослин та тварин. До царства тварин відносяться типи членистоногих, молюсків, голкошкірих, кишковопорожнинних, хордових та інші. До типу хордових відносяться класи риб, амфібій, рептилій, ссавців, птахів. До класу ссавців відносять ряд китів, ластоногих, хижих, гризунів, копитних та інші. До ряду хижих відносять родини ведмежих, єнотових, псових, кошачих та інші. До родини псових відносяться роди лисиць, єнотовидних собак, собак, фенеків та інші. До роду собак відносяться собаки домашні, вовки, шакали, койоти. До виду собак домашніх відносяться вівчарки, спаніелі, водолази, сербернари, болонки та інші.
II. Розв’язати одну з наступних творчих задач на вибір:
1. Класифікуйте свої знайомих (не менше 20 чоловік) за ознакою вашого знайомства (однокласники, друзі з одного двору, гравці однієї команди тощо). Представте результат у вигляді графа. Чи є отриманий граф деревом? Чи є такі особи, які попали одразу в декілька класів?
2. Виберіть з телепрограми на поточний тиждень передачі, які представляють для вас інтерес (не менше 20). Класифікуйте їх:
1) за датою,
2) по телеканалам,
3) по категорії (художні фільми, мультфільми, спортивні передачі тощо).
Представте результат у вигляді графа. Чи є отриманий граф деревом? Чи є такі передачі, які попали одразу в декілька класів?
3. Класифікуйте відомі вам книги (не менше 20):
1) за жанром (підручники, пригодницькі, фантастика, довідники та інші);
2) за часом видання (в один клас можна об’єднати книги, які видані за деякий проміжок часу);
3) за містом видання.
Представити результати у вигляді графа. Чи є отриманий граф деревом? Чи є такі книги, які попали одразу в декілька класів?
4. Представте у вигляді графа свій родовід за батьківською та материнською лініями.
Контрольні запитання:
PAGE 1
Шимон О.М. (ЖДУ, кафедра прикладної математики та інформатики)
Геометричний об’єкт
6
8
12
Березівка
Дубівка
Біла
Соснівка
Паста
Наконечник
Трубочка
Верхня частина
Нижня частина
Стержень
Ковпачок
Корпус
Кулькова ручка
Лінія
Плоска фігура
Об’ємне тіло
Пряма
Ломана
Коло
Трапеція
Еліпс
Крива
Паралелограм
Прямокутник
Ромб
Квадрат
Куля
Конус
Призма
Піраміда