Информационни модели на графики
Практическа работа
№10 "Схеми, графики и дървета" (задачи 3 - 5)
Информационни модели на графики
Графиката е визуално средство за представяне на състава и структурата на системата. Графиката се състои от върхове, свързани с линии. Ако линията е насочена (със стрелка), тогава тя се нарича дъга; ненасочена линия (без стрелка) се нарича ръб. Линия, която излиза от някакъв връх и влиза в него, се нарича цикъл. Върховете могат да бъдат изобразени като кръгове, овали, точки, правоъгълници и т.н.
Ако обектите на определена система са изобразени като върхове, а връзките между тях са линии, тогава ще получим информационен модел на разглежданата система под формата на графика.
По-рано разгледахме графики - диаграми на връзките, отразяващи съществуващите връзки между обектите.
Например графика, отразяваща "презаписаната" връзка между обекти от клас "деца", може да изглежда като следната фигура:
Връзката „кореспондират“ („пишат си писма“) е двупосочна (симетрична). Следователно съответните върхове са свързани с линии без стрелки (ръбове). Графиката се нарича неориентирана, ако нейните върхове са свързани с ръбове.
Извиква се път по върховете и ръбовете на графиката, който включва всеки ръб на графиката най-много веднъж верига.
Пример за верига: Юра-Аня-Витя-Коля.
Нарича се верига, чийто начален и краен връх съвпадат цикъл.
Пример за цикъл: Аня - Коля - Витя - Аня.
Графиката, която отразява връзката „пише букви“ между едни и същи обекти от класа „деца“, изглежда различно. Стрелковите линии (дъги) му придават съвсем различно значение:
Графиката се извиква ориентирана, ако върховете му са свързани с дъги.
Графиката се извиква балансиран, ако неговите върхове или ребра (дъги) се характеризират с някаква допълнителна информация - теглото на връх или ребро (дъги).
На фигурата по-долу информацията за градовете на Златния пръстен е представена чрез претеглена графика: теглата на върховете му - годината на основаване на градовете, теглото на ръбовете - разстоянието в километри между градовете.
Извиква се графика с цикъл мрежа.
Следващата фигура показва информационния модел на приказката за принцесата жаба под формата на графика.
Върховете на тази графика са символи и предмети от приказката, дъгите са връзките между тях. За разлика от предишните примери, тук всички връзки са различни. Следователно те се подписват до съответните дъги.
Такава графика се нарича семантична мрежа. Смята се, че всяка информация може да бъде представена под формата на семантична мрежа, която ще отразява обекти (концепции) и връзки (връзки) между тях.
Използване на графики за решаване на проблеми
Графиките са удобни за използване при решаване на някои класове задачи.
По колко начина трима трима ученици могат да бъдат настанени подред на три стола? Запишете всички възможни случаи.
Решението на този проблем е най-удобно представено като дърво. За неговия корен връх вземаме произволна точка от равнината O.
Всеки от тримата ученици може да седне на първия стол - нека ги обозначим A, B и C. На диаграмата това съответства на три клона, излизащи от точка O:
Чрез поставяне на ученик А на първия стол, ученик Б или С може да седне на втория стол. Ако ученик Б седне на първия стол, тогава А или С може да седне на втория стол. И ако С седне на първия стол, тогава A може да седи на второто или B. Това отговаря на диаграмата на два клона, излизащи от всеки връх на първото ниво:
Очевидно е, че третият стол във всеки случай ще бъде зает от останалия студент. Това съответства на един клон на дървото, който „расте“ от предишните клони.