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

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

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

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

4 Весовая матрица 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 Таблица «Схема дорог»

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

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

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

8 Решение

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

10

11