Графы Граф состоит из вершин, связанных линиями - рёбрами. Вершины графа изображаются кругами, овалами, точками, прямоугольниками и т. д. Объекты представляются.

Презентация:



Advertisements
Похожие презентации
ГРАФИЧЕСКИЕ ИНФОРМАЦИОННЫЕ МОДЕЛИ МОДЕЛИРОВАНИЕ И ФОРМАЛИЗАЦИЯ.
Advertisements

ГРАФИЧЕСКИЕ ИНФОРМАЦИОННЫЕ МОДЕЛИ МОДЕЛИРОВАНИЕ И ФОРМАЛИЗАЦИЯ.
ГРАФИЧЕСКИЕ ИНФОРМАЦИОННЫЕ МОДЕЛИ МОДЕЛИРОВАНИЕ И ФОРМАЛИЗАЦИЯ.
Информационные модели на графах Наглядным средством представления и структуры системы является граф.
ГРАФИЧЕСКИЕ ИНФОРМАЦИОННЫЕ МОДЕЛИ. Структуры данных.
Информационные модели на графах Болгова Н.А.- Учитель информатики МБОУ СОШ с УИОП с.Тербуны.
Проверочная работа Вариант 1 Вариант Проверочная работа Вариант 1 Вариант 2 2.
ГРАФЫ Граф – это совокупность точек, соединенных между собой линиями. Граф – это совокупность точек, соединенных между собой линиями. Служит для наглядного.
Впервые основы теории графов появились в работах Леонарда Эйлера ( ; швейцарский, немецкий и российский математик), в которых он описывал решение.
Графы и сети Каверина Ольга Геннадьевна учитель информатики и ИКТ МБОУ «Новониколаевская СОШ 2» р.п. Новониколаевский Волгоградская область.
Информационные модели на графах Информатика и ИКТ 7 класс Гимназия 1 г. Новокуйбышевска Учитель информатики: Красакова О.Н.
Графы и их применение (подготовка к ЕГЭ) Мастер – класс учитель Майсова Т.Б.
Графы и их применение Мастер-класс 12 февраля ГМО учителей информатики.
Граф отображает элементный состав системы и структуру связей между элементами этой системы А B C D F K.
Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,
Сжатие информации Алгоритм Хаффмана. Сжатие информации Сжатие данных – сокращение объема данных при сохранении закодированного в них содержания.
Л.Л. Босова, УМК по информатике для 5-7 классов Москва, 2007 СХЕМЫ.
Для описания строения различных систем, состоящих из связанных между собой элементов, часто используют графические схемы, изображая элементы точками (кружками,
Графы Граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки – вершины графа Линии – рёбра графа Вершины, соединенные ребром,
Информационные модели на графах. Состав графа Наглядным средством представления состава и структуры системы является граф. Граф состоит из вершин, связанных.
Транксрипт:

Графы Граф состоит из вершин, связанных линиями - рёбрами. Вершины графа изображаются кругами, овалами, точками, прямоугольниками и т. д. Объекты представляются как вершины графа, а связи – как его рёбра.

Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин или рёбер. Взвешенный граф D E A C B 90 Протяжённость дорог в километрах

Сеть и дерево Цепь – путь по вершинам и рёбрам граф, в который любое ребро графа входит не более одного раза. Дерево – это граф, в котором нет циклов Цикл - цепь, начальная и конечная вершины которой совпадают. Сеть - граф с циклом.

Весовая матрица ABCDE A 5090 B50 90 C 8060 D80 70 E Таблица «Схема дорог» D E A C B 90 Взвешенный граф Если между парой населённых пунктов существует дорога, то в ячейку на пересечении соответствующих строки и столбца записывается число, равное её длине. Пустые клетки в таблице означают, что дорог между соответствующими населёнными пунктами нет. D E A C B 90 Граф схемы дорог Одной и той же таблице могут соответствовать графы, внешне не похожие друг на друга ABCDE A 5090 B50 90 C 8060 D80 70 E Таблица «Схема дорог»

Весовая матрица D E A C B 90 ABCDE A 5090 B50 90 C 8060 D80 70 E Найти кратчайшее расстояние между А и D E D D

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? Нельзя переходить через занятый узел.

В фрагменте базы данных представлены сведения о родственных отношениях. Таб­ли­ца 1 IDФа­ми­лия_И.О.Пол 1108Козак Е.Р.Ж 1010Котова М.С.Ж 1047Лацис Н.Б.Ж 1037Белых С.Б.Ж 1083Петрич В.И.Ж 1025Саенко А.И.Ж 1071Белых А.И.М 1012Белых И.А.М 1098Белых Т.А.М 1096Белых Я.А.М 1051Мугабе Р.ХМ 1121Петрич Л.Р.М 1086Петрич Р.С.М Таб­ли­ца 2 ID_Ро­ди­те­ляID_Ре­бен­ка Определите на основании приведенных данных фамилию и инициалы внучки Белых И.А. 1) Белых С.Б. 2) Козак Е.Р. 3) Петрич В.И. 4) Петрич Л.Р.

Решение

Решить задачу с помощью графа