-
Курсы
-
Другое
Курс повышения квалификации
Курс повышения квалификации
Курс повышения квалификации
Курс профессиональной переподготовки
1 слайд
ВВЕДЕНИЕ
В
ТЕОРИЮ
ГРАФОВ
Выполнила: Рогозянская Л.М. учитель информатики МКОУ Жилинская СОШ
2 слайд
ЗАДАЧА:
Для игры в локальной сети необходимо соединить компьютерным кабелем шесть домов
РЕШЕНИЕ ЗАДАЧИ:
Определение маршрута прокладки кабеля минимальной длины, но при этом подходящего к каждому дому.
Для решения таких задач используют теорию графов.
1
4
5
3
6
2
400
700
100
200
100
800
200
300
200
600
3 слайд
1
4
5
3
6
2
100
200
100
200
300
200
Экономия: 2500 м кабеля
4 слайд
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
v5
v2
v3
v1
v4
R34
R45
R15
R23
R35
R34
R12
R14
V-ВЕРШИНЫ (населенные пункты, компьютеры, элементы блок-схем, логические элементы, стационарные телефоны и т.д.
R-Ребра (дороги, линии связи между компьютерами, стороны геометрических фигур)
Смежные вершины
(соединенные ребром)
5 слайд
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
v5
v2
v3
v1
v4
R34
R45
R15
R23
R35
R34
R12
R14
количество вершин и количество ребер определяют мощность множеств V и R
G=(V,R) - граф G
Ребро и любая из его двух
вершин называются инцидентными
Степень вершины –
количество инцидентных ей рёбер
V-5 R-8
6 слайд
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
v5
v2
v3
v1
v4
R34
R45
R15
R23
R35
R34
R12
R14
МАРШРУТ ГРАФА –ПОСЛЕДОВАТЕЛЬНОСТЬ ЧЕРЕДУЮЩИХСЯ ВЕРШИН И РЕБЕР
Простая цепь - все его вершины и ребра различны
Замкнутая цепь – начальная и конечная вершины совпадают
Связной граф – любая вершина достижима из любой другой вершины
Изолированные вершины - не имеют инцидентных ребер (например v6)
v6
7 слайд
Ориентированные
дуги
Входящая и исходящая степень вершины
Взвешенные
Ребра имеют числовые величины
Вес сети (сумма весов всех ребер)
ТИПЫ ГРАФОВ
8 слайд
ОПИСАНИЕ ГРАФА С
ПОМОЩЬЮ МАТРИЦЫ СМЕЖНОСТИ
R51
ВЕС СЕТИ =
240
Рабочие листы
к вашим урокам
Скачать
презентацию можно использовать на уроке профильного курса информатики в 11 классе при изучении темы "графы и их свойства", (учебник Н.Д.Угринович) В презентации рассматриваются основные понятия графов: вершины, ребра, смежные вершины, степень вершины. Маршруты графов: простая цепь, замкнутая цепь. Рассматриваются типы графов: ориентированные(дуги, входящая и исходящая степень вершины) и взыешенные(Ребра имеют числовые величины и вес сети).
В презентации приводится описание графа с помощью матрицы смежности.
7 366 349 материалов в базе
Настоящий материал опубликован пользователем Рогозянская Людмила Михайловна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВам будут доступны для скачивания все 359 888 материалов из нашего маркетплейса.
Мини-курс
4 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.