Информатика 9 класс
Урок№2 - Графы.
На этом уроке вы узнаете о графах, о том, какие бывают графы и из каких элементов они состоят, для каких целей они создаются. Научитесь различать ориентированные и неориентированные графы, строить деревья. Научитесь решать задачи на определение количества путей в графе, используемые при государственной итоговой аттестации.
На прошлом уроке мы уже говорили о том, что одним из методов познания является моделирование, рассматривали различные классификации моделей и выделили в качестве предмета нашего рассмотрения информационные модели. Среди них можно выделить графические информационные модели, к которым относятся карты, чертежи, схемы, диаграммы, графики и предмет сегодняшнего рассмотрения — графы.
Если рассматривать группу объектов вместе с имеющимися между ними связями как единое целое, то можно говорить о системе. Мы можем графически изобразить объекты системы вершинами, а связи между ними линиями (рёбрами). В этом случае мы получим информационную модель системы в форме графа.
Если рёбра графа имеют направление, то оно отображается стрелками, а граф называется ориентированным (направленным).
Вершины графа могут отображаться точками, кругами, прямоугольниками и т.д.
Если вершины или ребра графа характеризуются некоторой дополнительной информацией — весом вершины или ребра, то такой граф называют взвешенным.
С помощью взвешенных графов удобно изображать дороги между населенными пунктами. Например, в приведенном примере указана протяжённость дорог в километрах.
Проведём путь, проходящий по вершинам и ребрам графа так, чтобы любое ребро входило в него не более одного раза. Такой путь называется цепью. Цепь, у которой совпадают начальная и конечная вершины, называется циклом.
Граф с циклом называется сетью.Если персонажей некоторого литературного произведения, мультфильма или сериала представить вершинами графа, а связи между ними изобразить рёбрами, то получится граф, который называют семантической сетью.
Информационные модели в виде графов широко используются в повседневной жизни.
Например, при проектировании нового жилого района можно здания обозначить как вершины графа, а дороги, коммуникации и т.д. — ребрами графа. По таким графам удобно, например, прогнозировать загрузку дорог и находить оптимальные транспортные маршруты. Другим примером является схема метрополитена. Вершинами в графе в этом случае являются станции метро.
Граф, в котором отсутствуют циклы, называется деревом.
В этом случае между любыми двумя вершинами существует только один путь.
С помощью дерева удобно представлять иерархическую систему.
У дерева выделяется одна главная вершина, которую называют корнем.
Каждая вершина дерева, исключая корень, может иметь только одного предка (вершина верхнего уровня), но при этом может порождать множество потомков, отображаемых вершинами нижнего уровня. Вершины, у которых отсутствуют порожденные вершины, называются листьями.
Одним из известных применений графов является генеалогическое или родословное дерево, на котором отображаются родственные связи.
Существуют задачи, которые удобно решать с помощью графов.
Например, если мы хотим отобразить все возможные варианты трехзначных чисел, которые могут получиться из цифр 7 и 8.
С помощью графов удобно решать задачи на определение выигрышной стратегии игроков.
Задача на анализ информации, представленной в виде графа, является одной из предлагаемых на государственной итоговой аттестации по информатике.
Итак, сегодня вы узнали о том, какие бывают графы и из каких элементов они состоят, для каких целей создаются. Получили представление об ориентированных и неориентированных графах, деревьях. Научились решать задачи на определение количества путей в графе, используемые при государственной итоговой аттестации. Закрепите полученные знания на практике, выполнив упражнения.
Вводятся понятия — Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра и пути. Дерево. Корень, лист, вершина.
25 просмотров
516
154
1 месяц назад 00:09:42 1
Информатика 9 класс. Встроенные функции (УМК БОСОВА Л.Л., БОСОВА А.Ю.)
1 месяц назад 00:17:06 1
Отзыв о ГУАП от студента информатики
1 месяц назад 00:09:06 1
Организация вычислений в электронных таблицах | Информатика 9 класс #19 | Инфоурок
1 месяц назад 00:13:03 1
КАК СДАТЬ ЕГЭ НА 270+ ЗА МЕСЯЦ ПОДГОТОВКИ | стратегия, советы, опыт, планер
1 месяц назад 02:51:31 1
Электронные таблицы. Задания 3, 9, 18, 22. МИНИ-ЩЕЛЧОК перед досрочным ЕГЭ по информатике 2024
1 месяц назад 01:13:00 1
Решаем ВСЕ задания 8 из банка ФИПИ для ОГЭ по русскому языку
1 месяц назад 01:50:54 1
Задание 9 // КЕГЭ по информатике 2024
1 месяц назад 00:08:21 1
Информатика 7 класс (Урок№9 - Основы информационной безопасности и защиты информации.)
1 месяц назад 01:44:30 1
Слив заданий №9-15. Это будет на ЕГЭ 2024 по русскому языку.
1 месяц назад 00:43:23 1
Задание 14. ОГЭ информатика “Электронные таблицы и диаграммы“ (Примитивные решения) часть 1
1 месяц назад 00:03:02 1
Информатика 11 класс (Урок№9 - Компьютерное моделирование.)
1 месяц назад 01:56:59 1
Задание №3 с 0 до 100 за 1 веб. 1 урок “Матрица ++“ | ЕГЭ по информатике 2024 | Артем Flash
1 месяц назад 02:59:24 1
Программирование. Задания 2, 5, 8, 12, 14. МИНИ-ЩЕЛЧОК перед досрочным ЕГЭ по информатике 2024
1 месяц назад 00:25:13 1
Разбор 8 задания ЕГЭ Информатика 2024| Юрий Николаевич
1 месяц назад 00:57:10 1
Профильный ЕГЭ 2023. Задача 4. Преобразование выражений. 10 класс
1 месяц назад 02:10:43 1
Официальный пробник ФИПИ от 5 марта 2024 | ЕГЭ информатика 2024 | Артем ФЛЭШ
1 месяц назад 01:43:19 1
Разбор самого сложного варианта ОГЭ по информатике
1 месяц назад 02:20:45 1
Анализ результатов и разбор заданий пробного ЕГЭ от от /dev/inf
1 месяц назад 03:15:28 1
ВСЕ ЗАДАЧИ №27 с официальных ЕГЭ с 2017 года по 2023 | Информатика ЕГЭ 2023 | Умскул
1 месяц назад 00:07:39 1
Локальные и глобальные компьютерные сети | Информатика 9 класс #22 | Инфоурок
1 месяц назад 04:38:33 12
Вся ГРАФИКА для параметров за 5 часов | №18 ЕГЭ 2024 по математике
1 месяц назад 01:46:18 1
Полный разбор ОГЭ 2024 по информатике
1 месяц назад 00:06:54 1
Самые простые задания из ОГЭ по русскому языку 2024. Как набрать минимальный балл?
1 месяц назад 01:12:15 1
Французская литература сегодня. Лекция В.А. Нуриева в ИИЯ МПГУ