Урок 25
Информационни модели на графики

Практическа работа
№10 "Схеми, графики и дървета" (задачи 3 - 5)

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

Графиката е визуално средство за представяне на състава и структурата на системата. Графиката се състои от върхове, свързани с линии. Ако линията е насочена (със стрелка), тогава тя се нарича дъга; ненасочена линия (без стрелка) се нарича ръб. Линия, която излиза от някакъв връх и влиза в него, се нарича цикъл. Върховете могат да бъдат изобразени като кръгове, овали, точки, правоъгълници и т.н.

Ако обектите на определена система са изобразени като върхове, а връзките между тях са линии, тогава ще получим информационен модел на разглежданата система под формата на графика.

По-рано разгледахме графики - диаграми на връзките, отразяващи съществуващите връзки между обектите.

Например графика, отразяваща "презаписаната" връзка между обекти от клас "деца", може да изглежда като следната фигура:

Връзката „кореспондират“ („пишат си писма“) е двупосочна (симетрична). Следователно съответните върхове са свързани с линии без стрелки (ръбове). Графиката се нарича неориентирана, ако нейните върхове са свързани с ръбове.

Извиква се път по върховете и ръбовете на графиката, който включва всеки ръб на графиката най-много веднъж верига.
Пример за верига: Юра-Аня-Витя-Коля.

Нарича се верига, чийто начален и краен връх съвпадат цикъл.
Пример за цикъл: Аня - Коля - Витя - Аня.

Графиката, която отразява връзката „пише букви“ между едни и същи обекти от класа „деца“, изглежда различно. Стрелковите линии (дъги) му придават съвсем различно значение:

Графиката се извиква ориентирана, ако върховете му са свързани с дъги.

Графиката се извиква балансиран, ако неговите върхове или ребра (дъги) се характеризират с някаква допълнителна информация - теглото на връх или ребро (дъги).

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

Извиква се графика с цикъл мрежа.

Следващата фигура показва информационния модел на приказката за принцесата жаба под формата на графика.

Върховете на тази графика са символи и предмети от приказката, дъгите са връзките между тях. За разлика от предишните примери, тук всички връзки са различни. Следователно те се подписват до съответните дъги.

Такава графика се нарича семантична мрежа. Смята се, че всяка информация може да бъде представена под формата на семантична мрежа, която ще отразява обекти (концепции) и връзки (връзки) между тях.

Използване на графики за решаване на проблеми

Графиките са удобни за използване при решаване на някои класове задачи.

По колко начина трима трима ученици могат да бъдат настанени подред на три стола? Запишете всички възможни случаи.

Решението на този проблем е най-удобно представено като дърво. За неговия корен връх вземаме произволна точка от равнината O.

Всеки от тримата ученици може да седне на първия стол - нека ги обозначим A, B и C. На диаграмата това съответства на три клона, излизащи от точка O:

Чрез поставяне на ученик А на първия стол, ученик Б или С може да седне на втория стол. Ако ученик Б седне на първия стол, тогава А или С може да седне на втория стол. И ако С седне на първия стол, тогава A може да седи на второто или B. Това отговаря на диаграмата на два клона, излизащи от всеки връх на първото ниво:

Очевидно е, че третият стол във всеки случай ще бъде зает от останалия студент. Това съответства на един клон на дървото, който „расте“ от предишните клони.

Нека запишем всички пътища от върховете на първото ниво до върховете на третото ниво: A-B-C, A-C-B, B-A-C, B-C-A, C-A-B, C-B-A. Всеки от писмените пътища определя една от опциите за настаняване на учениците на столове. Тъй като няма други начини, необходимият брой начини е 6.

Не е нужно да изграждате дърво, ако не е необходимо да записвате всички възможни опции, а просто трябва да посочите техния брой. В този случай трябва да разсъждавате по следния начин: един от трима души може да седне на първия стол, един от останалите двама на втория и един останал на третия: 3 * 2 * 1 = 6.

За да донесе подмладяващи ябълки на Цар-Отец, Иван Царевич трябва да намери единствения истински път към вълшебната градина. Иван Царевич срещна стар гарван на разклонение в трите пътя и ето съветите, които чу от него:

Летящ оттам гълъб прошепна на Иван Царевич, че само един съвет от гарвана е правилен и че е наложително да се върви по пътеки в различни посоки. Нашият герой изпълни задачата и се озова в магическа градина. По кой маршрут е тръгнал?

Нека обозначим левия, средния и десния път с L, C и P. Възможните маршрути са представени под формата на графика. В този случай маркираме върховете на гарвана с по-„смели“ ръбове. Тъй като само един от съветите на гарвана е правилен, то на графиката той ще съответства на маршрут с един „дебел“ ръб. Този маршрут е обозначен с допълнителна пунктирана линия:

Накратко за основното

Графиката е визуално средство за представяне на състава и структурата на системата. Графиката се състои от върхове, свързани с линии. Насочената линия се нарича дъга, а ненасочената линия се нарича ръб. Линия, която излиза от някакъв връх и влиза в него, се нарича цикъл. Графиката се нарича претеглена, ако нейните върхове или ръбове (дъги) се характеризират с някаква допълнителна информация - теглото на връх или ребро (дъги).

Път по върховете и ръбовете на графика, който включва всеки ръб на графиката най-много веднъж, се нарича верига. Верига, чийто начален и краен връх съвпадат, се нарича цикъл. Един вид графика, съдържаща цикли, се нарича мрежа.

Йерархията е подреждането на части или елементи от едно цяло по ред от най-високо до най-ниско. Системи, чиито елементи са във връзката "е разнообразие", "е част от" и други отношения на подчинение се наричат йерархични системи (системи с йерархична структура).

Графиката на йерархична система се нарича дърво. Отличителна черта на дървото е, че между всеки два негови върха има само един път. Дърветата не съдържат цикли и цикли.

Въпроси и задачи

1. Определете приказка, за която следващата графика определя връзката между знаците.

(Пиле Ryaba)

2. Три пътеки се изкачват по хълма от различни страни и се сближават на върха. Избройте многото маршрути, по които можете да се качите нагоре и надолу по хълма. Решете същия проблем, ако трябва да следвате различни пътища нагоре и надолу.

3. Колко трицифрени числа могат да бъдат написани с числата 1, 3, 5 и 7, при условие че числото не съдържа същите числа?

4. За направата на вериги се използват мъниста, маркирани с букви: A, B, C, D, E. На първо място във веригата е една от мънистата A, C, E. На второто - всяка гласна, ако първата буква е съгласна и всяка съгласна, ако първата гласна.

На трето място е една от мънистата C, D, E, която не е на първо място във веригата. Колко вериги могат да бъдат създадени съгласно това правило?

5. В центъра на далечната гора имаше голяма поляна - най-удивителното място в Страната на децата. Върху него имаше три кладенци: единият със сода, вторият с мляко и третият с плодова напитка. Някога трима приятели Фантик, Грибок и Дружок построили къщи на поляната и живели цялото лято в гората. Други деца обичаха да им идват на гости, да пият мляко, сода или плодова напитка, да се разхождат по горските пътеки. Но веднъж бившите приятели изпаднаха и всеки от тях реши да прокара свои собствени пътеки към кладенците, така че да не се пресичат с пътищата на съседите.

(Проблемът няма решение. Пътеките не могат да бъдат изчертани, така че да не се пресичат).

Практическа работа No10
"Схеми, графики и дървета" (задачи 3 - 5)

Задача 3. Семантична мрежа. Разходка с автобус

един. Отворете файла Ride.doc от папката Blanks.

2. Начертайте диаграма на връзката, когато пътувате в автобуса. На редовете, които показват връзки, подпишете имената им (като използвате глаголи).

3. Запазете резултата от вашата работа във вашата собствена папка във файл с име Пътуване 1.

Задача 4. Воден цикъл в природата

Ще приемем, че водният цикъл в природата се осигурява от взаимодействието на следните обекти: резервоари (океани, морета, езера, резервоари, езера и др.), Реки, подпочвени води, атмосфера, облаци, почва, растения.

Представете си водния цикъл в природата под формата на графика (семантична мрежа), в която изброените обекти са върховете, а дъгите са отношенията между тях, които осигуряват движението на водата.

Запазете резултата от вашата работа във вашата собствена папка във файл с име Цикълът.

Задача 5. Аритметични изрази

Използвайки графиката, можете да зададете последователността за изчисляване на аритметичен израз. Такава графика е дърво, чиито листа са числа, а останалите върхове са операции. Дъгите се свързват върхова операция с върхови операнди. Например за аритметичен израз 5 x (3 + 7) x (8 - 2) дървото ще изглежда така:

Изградете дърво за аритметичен израз: 6 x 4 + 7 x (9 - 1).

Запазете резултата от вашата работа във вашата собствена папка във файл с име Израз.

Урок 25Информационни модели на графики

Практическа работа №10 "Схеми, графики и дървета" (задачи 3 - 5)