Презентация по информатике на тему Информационные модели на графах (6 класс)

Информационные модели на графах Его величество Граф Граф – это наглядное средство представления состава и структуры системы. В А С дуга ребро петля вершина Неориентированный граф Неориентированный граф – это граф, вершины которого соединены ребрами. С помощью таких графов могут быть представлены схемы двухсторонних отношений. Анна Юра Витя Маша Коля Граф, отражающий отношение «переписываются» между объектами класса «дети». Цепь – это путь по вершинам и ребрам графа, включающий любое ребро не более одного раза. Анна Юра Витя Маша Коля Цикл – это цепь, начальная и конечная вершины которой совпадаю. Граф с циклами называют сетью. Анна Юра Витя Маша Коля Ориентированный граф Ориентированный граф – это граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений. Анна Юра Витя Маша Коля Граф, отражающий отношение «написал письмо» между объектами класса «дети». Взвешенный граф Взвешенный граф – это граф, у которого вершины или ребра (дуги) характеризуются некоторой дополнительной информацией (весом). Санкт-Петербург Москва Нижний Новгород Екатеринбург Новосибирск 706 421 1336 1598 Что является графом? Схема метрополитена Генеалогическое древо Граф Дракула Компьютерные сети Файловая система Графический редактор Далее Решение задач на графах Задача 1Сколько трехзначных чисел можно записать с помощью цифр 1, 3, 5, 7 при условии, что в записи числа не должно быть одинаковых цифр? 0 1 3 5 7 3 5 7 1 3 5 1 5 7 1 3 7 5 7 3 7 3 5 5 7 1 7 1 5 3 7 1 7 1 3 3 5 1 5 1 3 Ответ: 24 числа 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Решение задач на графах Задача 2 На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? А Б В Г Д Ж Е 1. А-Б-Д-Ж 2. А-Б-Г-Д-Ж 3. А-Б-Г-Ж 4. А-В-Б-Д-Ж 5. А-В-Б-Г-Д-Ж 6. А-В-Б-Г-Ж 7. А-В-Г-Д-Ж 8. А-В-Г-Ж 9. А-В-Ж 10. А-В-Е-Ж Ответ: 10 путей Решение задач на графах Задача 3 Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице.. Определите длину кратчайшего маршрута из А в F. А B C D E F A 2 4 B 2 1 7 C 4 1 3 4 D 3 3 E 7 4 3 2 F 2 А B C D E F 2 4 1 7 3 4 3 2 1. A-B-C-D-E-F (2+1+3+3+2=11) 2. A-B-C-E-F (2+1+4+2=9) 3. A-B-E-F (2+7+2=11) 4. A-C-D-E-F (4+3+3+2=12) 5. A-C-E-F (4+4+2=10) Ответ: 9 Физкультминутка Практическая работа Интерактивные задания «Графы» http://files.school-collection.edu.ru/dlrstore/9df50b64-513d-41b8-b0e9-e60371c2ffe8/%5BNS-INF_4-03-03-04%5D_%5BIM_280%5D.swf;http://files.school-collection.edu.ru/dlrstore/12fb7367-c9f0-48c7-b88a-45c5d102c376/%5BNS-INF_4-03-03-04%5D_%5BIM_281%5D.swf;http://files.school-collection.edu.ru/dlrstore/b4789518-0cbd-4228-8aa6-501cebffb3ca/%5BNS-INF_4-03-03-04%5D_%5BIM_282%5D.swf;http://files.school-collection.edu.ru/dlrstore/7b9d8fb7-6a63-41cc-8682-2b6da6c2d7b7/%5BNS-INF_4-03-03-04%5D_%5BIM_283%5D.swf;http://files.school-collection.edu.ru/dlrstore/64951a7c-0a38-45dd-a2f5-94330d32e9bf/%5BNS-INF_4-03-03-04%5D_%5BIM_284%5D.swf. Спасибо за внимание!