Граф с какими свойствами называют деревом Что такое корень дерева, ветви, листья?
Пожалуйста, войдите или зарегистрируйтесь для публикации ответа на этот вопрос.
решение вопроса
Связанных вопросов не найдено
Обучайтесь и развивайтесь всесторонне вместе с нами, делитесь знаниями и накопленным опытом, расширяйте границы знаний и ваших умений.
поделиться знаниями или
запомнить страничку
- Все категории
- экономические 43,679
- гуманитарные 33,657
- юридические 17,917
- школьный раздел 612,616
- разное 16,911
Популярное на сайте:
Как быстро выучить стихотворение наизусть? Запоминание стихов является стандартным заданием во многих школах.
Как научится читать по диагонали? Скорость чтения зависит от скорости восприятия каждого отдельного слова в тексте.
Как быстро и эффективно исправить почерк? Люди часто предполагают, что каллиграфия и почерк являются синонимами, но это не так.
Как научится говорить грамотно и правильно? Общение на хорошем, уверенном и естественном русском языке является достижимой целью.
- Обратная связь
- Правила сайта
Иерархия. Деревья. Графы — создание
Цель: сформировать представление о деревьях как графах, изображающих иерархические системы, закрепить умения строить графы, осуществить контроль знаний, усилить междисциплинарные связи школьном образовании.
· Образовательные: проверить знания, полученные на предыдущем уроке, познакомить с понятиями иерархия, иерархическая система, дерево, совершенствовать умения строить графы при решении задач в различных учебных предметах.
· Развивающие: развитие творческих способностей, логического мышления учащихся, развитие умений делать анализ, выделяя объекты и обозначая связи между ними.
· Воспитательные: воспитание самостоятельности при выполнении заданий, умения самостоятельно оценивать результат своей деятельности.
· Здоровьесберегающая: соблюдение правил ТБ, смена деятельности обучающихся во избежание переутомления.
1. Организационный момент.
Приветствие учащихся, отметка отсутствующих.
2. Проверка домашнего задания.
Проверка теоретического материала.
3. Изучение нового материала
Ответьте на следующие вопросы:
1. Что такое модель?
2. Назовите виды моделей (натурные и информационные)
3. Приведите примеры материальных моделей, не упомянутые в параграфе.
4. Назовите типы информационных моделей (вербальные, графические, табличные, математические)
5. Что такое информационная модель? (и.м. – это описание в той или иной форме объекта моделирования)
6. Можно ли карту города назвать информационной моделью? Ответ поясните.
7. Что такое компьютерная информационная модель? (информационные модели, реализованные на компьютере)
8. В чем преимущество компьютерных информационных моделей перед теоретическими?
Данные, используемые в любой информационной модели, всегда определенным образом упорядочены, структурированы. Иначе можно сказать так: данные, на которых базируется информационная модель, представляют собой систему со всеми характерными признаками – элементным составом, структурой, назначением. Такие структурированные системы данных часто называют структурами данных.
Мы рассмотрим несколько часто используемых видов описания структур данных: графы, иерархические структуры (деревья) и таблицы.
(Записывают тему урока в тетрадь)
В разговорной речи мы часто используем словесное (вербальное) представление информации. Например, словестное описание некоторой местности: «Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино». По такому описанию довольно трудно представить себе эту местность, нелегко и запомнить описание. А представьте себе, что поселков не 5, а 25! Всё гораздо понятнее становится из схемы (на ней поселки обозначены первыми буквами своих названий)
Это не карта местности. Здесь не выднржаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом.
Глядя на этот граф, легко понять структуру дорожной системы в данной местности. Построенный граф позволяет, апример, ответить на вопрос: через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино. Видно, что есть два возможных пути:
Очевидно, первый путь более выгодный, он короче. Однако, если по какой-то причине дорога между К и Б окажется непроезжей, то единственным остается второй путь. Граф на рисунке 1 еще называют сетью.
Для сети характерна возможность множества различных путей перемещения по ребрам между некоторыми парами вершин.
Для сетей также характерно наличие замкнутых путей, которые называют циклами. На рис.1 имеется цикл К-Д-Б-К. Кстати, термин «дорожная сеть» используется и в разговорной речи.
Граф изображенный на рис.1 является неориентированным графом. На нем каждое ребро обозначает наличие дорожной связи между двумя пунктами. Но дорожная связь действует одинаково в обе стороны. Такую связь еще называют симметричной.
Рассмотрим другой пример графа
Граф на рис.2 показывает возможные варианты переливания крови. Группы крови обозначены вершинами графа. А стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови.
Связи между вершинами данного графа несимметричны и поэтому изображаются направленными линиями со стрелками. Такие линии принято называть дугами. Граф с такими свойствами называется ориентированным. Линия, выходящая и входящая в одну и ту же вершину, называется петлей.
Итак, запишем словарь урока:
Граф [graph — от греч. — пишу, изображаю] – это средство для наглядного представления состава и структуры системы.
Вершины графа – это компоненты системы изображаемые кружками, овалами, прямоугольниками и пр.
Дуги – это направленные линии (стрелки), связывающие компоненты между собой определенным образом.
Ребра – это ненаправленные линии, связывающие компоненты между собой определенным образом.
Петля – это ребро, соединяющее вершину с нею самой.
Вершины, которым не соответствует ни одно ребро, называются «изолированными».
Сеть – это граф, в котором вершины связаны между собой по принципу «многие ко многим»
Число ребер, соединяющих две фиксированные вершины, может быть произвольным, поскольку оно определяется количеством и характером связей между соответствующими этим вершинам объектами, В то же время каждому ребру соответствует не более двух вершин.
Следующий тип структур – это иерархические структуры (деревья)
Иерархическую структуру имеют, например, системы административного управления, между элементами которых установлены отношения подчиненности. На рис.3 изображен граф, отражающий иерархическую административную структуру нашего государства.
Такой граф называется деревом. Основным свойством дерева является то, что между любыми двумя его вершинами существует единственный путь. Деревья не содержат циклов и петель.
Запишем в словарь урока:
Дерево – это граф, предназначенный для отображения вложенности, подчиненности, наследования и т.п. между объектами. В таком графе нет связанных по замкнутой линии вершин. Каждая вершина связана только с верхней и не связана больше ни с чем.
Обычно у дерева, отображающего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. От нее идут ветви дерева. От корня начинается отсчет уровней дерева. Каждая вершина дерева (кроме корня) имеет одну исходную вершину на предыдущем уровне и может иметь множество порожденных вершин на следующем уровне. Такой принцип связи называется «один ко многим», в отличие от сети – там связь «многие ко многим». Вершины, которые не имеют порожденных вершин, называются листьями. На рис.3 листьями являются вершины, обозначающие города.
Иерархическими являются различные системы классификации в науке. (например, в биологии весь животный мир Земли рассматривается как система, которая делится на типы животных, типы делятся на классы, классы состоят из отрядов, отряды – из семейств, семейства делятся на роды, роды – на виды. Имеем шестиуровневую иерархическую структуру.
При изучении информатики вам также приходилось встречаться с иерархическими системами. Например, система хранения файлов на магнитных дисках организована по иерархическому принципу.
Одной из наиболее часто встречающихся структур информационных моделей является таблица. Таблица – универсальное средство представления информации. Чаще всего мы пользуемся прямоугольными таблицами. Простейшая таблица состоит из строк и граф (столбцов). Пересечение строки и столбца образует ячейку.
Год издания
«Сказка о царе Салтане»
Данная таблица является примером таблицы типа «объект – свойство». Каждая строка такой таблицы относится к конкретному объекту. В нашем примере объект – это автор книги.
Другой тип таблиц называется «объект – объект». Такие таблицы отражают взаимосвязь между различными объектами. Примером является таблица успеваемости учеников по разным предметам. Эта таблица отражает связь между объектами двух типов: учениками и изучаемыми дисциплинами. Оценка (расположена в ячейке) является характеристикой такой связи.
Русский язык
Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами (системами с иерархической структурой).
Например, иерархическую структуру имеет школа, потому что в ней установлены следующие отношения подчиненности: директор — заместители директора — учителя — ученики.
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.
Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка — обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один ко многим». Вершины, не имеющие порожденных вершин, называются листьями».
По иерархическому принципу организована система хранения файлов во внешней памяти.
Как вы думаете, что в информатике составлено по иерархическому типу? (система хранения файлов).
Вы знаете, что по определенному признаку (принадлежность, назначение, содержимое, время создания и т. д.) файлы целесообразно объединять в папки . Папки, в свою очередь, могут вкладываться в другие папки и т. д.
Для того чтобы найти файл в иерархической файловой структуре, можно указать путь к файлу. В путь к файлу входят записываемые через разделитель «\» логическое имя диска и последовательность имен вложенных друг в друга папок, в последней из которых находится нужный файл.
Например, пути к файлам на рис. 2.35 можно записать так:
С:\Проекты\История\
С:\Проекты\Информатика\
С:\Рисунки\
4. Выполнение практической работы
5. Подведение итогов урока
Обобщение деятельности учащихся на уроке. Выставление оценок.
Просмотрено: 0%
Просмотрено: 0%
Рабочие листы к Вашему уроку:
Рабочие листы
к вашим урокам
Краткое описание документа:
Цель: сформировать представление о деревьях как графах, изображающих иерархические системы, закрепить умения строить графы, осуществить контроль знаний, усилить междисциплинарные связи школьном образовании. Задачи: Образовательные: проверить знания, полученные на предыдущем уроке, познакомить с понятиями иерархия, иерархическая система, дерево, совершенствовать умения строить графы при решении задач в различных учебных предметах.Развивающие: развитие творческих способностей, логического мышления учащихся, развитие умений делать анализ, выделяя объекты и обозначая связи между ними.Воспитательные: воспитание самостоятельности при выполнениизаданий, умения самостоятельно оценивать результат своей деятельности. Здоровьесберегающая: соблюдение правил ТБ, смена деятельности обучающихся во избежание переутомления. ХОД УРОКА 1. Организационный момент. Приветствие учащихся, отметка отсутствующих. 2. Проверка домашнего задания. Проверка теоретического материала. 3. Изучение нового материала Ответьте на следующие вопросы: Что такое модель?Назовите виды моделей (натурные и информационные)Приведите примеры материальных моделей, не упомянутые в параграфе.Назовите типы информационных моделей (вербальные, графические, табличные, математические)Что такое информационная модель? (и.м. – это описание в той или иной форме объекта моделирования)Можно ли карту города назвать информационной моделью? Ответ поясните.Что такое компьютерная информационная модель? (информационные модели, реализованные на компьютере)В чем преимущество компьютерных информационных моделей перед теоретическими? Данные, используемые в любой информационной модели, всегда определенным образом упорядочены, структурированы. Иначе можно сказать так: данные, на которых базируется информационная модель, представляют собой систему со всеми характерными признаками – элементным составом, структурой, назначением. Такие структурированные системы данных часто называют структурами данных. Мы рассмотрим несколько часто используемых видов описания структур данных: графы, иерархические структуры (деревья) и таблицы. (Записывают тему урока в тетрадь) Графы В разговорной речи мы часто используем словесное (вербальное) представление информации. Например, словестное описание некоторой местности: «Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино». По такому описанию довольно трудно представить себе эту местность, нелегко и запомнить описание. А представьте себе, что поселков не 5, а 25! Всё гораздо понятнее становится из схемы (на ней поселки обозначены первыми буквами своих названий) Это не карта местности. Здесь не выднржаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом. Глядя на этот граф, легко понять структуру дорожной системы в данной местности. Построенный граф позволяет, апример, ответить на вопрос: через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино. Видно, что есть два возможных пути: Р-К-Б-МР-К-Д-Б-М Очевидно, первый путь более выгодный, он короче. Однако, если по какой-то причине дорога между К и Б окажется непроезжей, то единственным остается второй путь. Граф на рисунке 1 еще называют сетью.
Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:
6 501 239 материалов в базе
Материал подходит для УМК
«Информатика. Углубленный уровень (в 2-ух частях) », Поляков К.Ю., Еремин Е.А. Больше материалов по этому УМК
Выберите элементы которые относятся к графу дереву
Главное меню
Соглашение
Регистрация
Английский язык
Астрономия
Белорусский язык
Информатика
Итальянский язык
Краеведение
Литература
Математика
Немецкий язык
Обществознание
Окружающий мир
Русский язык
Технология
Физкультура
Для учителей
Дошкольникам
VIP — доступ
Автор: Гаязова Резеда Рафилевна | ID: 17277 | Дата: 10.5.2022
Помещать страницу в закладки могут только зарегистрированные пользователи
Зарегистрироваться
Получение сертификата
о прохождении теста
1. Информационные модели на графах
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними — отрезками или дугами.
Основы теории графов как математической науки заложил в \(1736\) г. Леонард Эйлер , рассматривая задачу о Кёнигсбергских мостах. Сегодня эта задача стала классической.
Графом называется конечное множество точек, некоторые из которых соединены линиями.
Обрати внимание!
Точки называются вершинами графа, а соединяющие линии — рёбрами.
Количество рёбер, выходящих из вершины графа, называется степенью вершины .
Обрати внимание!
Вершина графа, имеющая нечётную степень, называется нечётной, а чётную степень — чётной.
Изолированная вершина — вершина, степень которой равна \(0\).
Конечная вершина графа — вершина, степень которой равна \(1\).
Направленная линия (со стрелкой) называется дугой .
Линия ненаправленная (без стрелки) называется ребром .
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлёй .
Рассмотрим отношение «дети переписываются» (пишут письма друг другу). Отношение является двусторонним, поэтому вершины соединены линиями без стрелок.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
Граф, в котором все вершины соединены рёбрами, называется неориентированным .
Цепь — путь по вершинам и рёбрам, включающий любое ребро графа не более одного раза.
Цикл — цепь, начальная и конечная вершины которой совпадают.
Граф с циклом называют сетью .
Ориентированный граф — граф, рёбрам которого присвоено направление.
С помощью таких графов могут быть представлены схемы односторонних отношений.
Если все вершины графа чётные, то можно одним росчерком пера начертить граф. При этом начать движение можно с любой вершины и закончить в той же вершине.
Граф с двумя нечётными вершинами также можно начертить одним росчерком. Начинать движение надо с одной нечётной вершины, а заканчивать в другой.