Введение в теорию графов 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику Н.Д.Угриновича.

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

Advertisements

Похожие презентации

Введение в теорию графов. ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ

Advertisements

Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,

Графы Граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки – вершины графа Линии – рёбра графа Вершины, соединенные ребром,

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ И ЕГО ЭЛЕМЕНТОВ. ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ.

Информационные модели на графах Болгова Н.А.- Учитель информатики МБОУ СОШ с УИОП с.Тербуны.

ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.

V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E – множества, отображение инциденции f: Е V&V множества Е в V&V Основы.

Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.

Алексеева Е.В., учитель информатики и ИКТ МОУ «Сланцевская СОШ 3» Введение в теорию графов 11 класс начать.

Это раздел математики изучающий случайные события, находит зависимости между их появлениями, таким образом вычисляя вероятности их появлений.

Разработка элективного курса по теории ориентированых графов и приложений Муниципальное бюджетное образовательное учреждение «Котлубанская средняя общеобразовательная.

ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.

Информационные модели на графах Наглядным средством представления и структуры системы является граф.

Презентация по Информатике Тема: «Графы» Выполнил: Бычков Георгий.

Методическая разработка урока раздела учебной программы по информатике 7 класс тема: «Информационные модели на графах» Выполнила : учитель информатики.

Воробьева Людмила Васильевна МБОУ «СОШ 9» город Вязники, Владимирской обл.

1. Основные понятия теории графов 1. Основные понятия теории графов 2. Степень вершины Введение 5. Ориентированные графы 6. Изоморфизм графов 7. Плоские.

Маршрут, цепь, цикл Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны (т.е. соединены). Например:

Лекция 5 Теория графов, сетей, социальные сети и институты.

Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.

Транксрипт:

Введение в теорию графов 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику Н.Д.Угриновича

Введение в теорию Цель: проектирование компьютерных сетей, телефонных линий, трубопроводов Задача: минимизировать затраты на прокладку коммуникаций Здание, к которому проводятся коммуникации

Основные понятия Граф G G = (V,R) V – множество вершин, R – множество ребер (R) = Ø Примеры: Населенные пункты – дороги, Вершины треугольника – стороны треугольника, Перекрестки улиц – улицы. Множества V и R – конечные, если можно перечислить все ребра и вершины графа. Мощность множества V равна 5, множества R равна 8.

Основные понятия Граф G V – множество вершин, R – множество ребер V 1 и V 2 – смежные вершины, соединяемые одним ребром R 12. Ребро и любая из его вершин – инцидентные. Количество инцидентных ребер вершины – степень вершины. Маршрут графа – последовательность чередующихся вершин и ребер. Цикл графа (замкнутый маршрут) – если начальная и конечная вершина маршрута совпадают. Например, в графе G: V1 R12 V2 R23 V3 R34 V4 R14 V1 V2 R23 V3 R35 V5 R25 V2 Простая цепь – маршрут, если все его вершины и ребра различны. Длина маршрута = количеству входящих в него ребер.

Основные понятия Граф G V – множество вершин, R – множество ребер Одна вершина достижима из другой, если между ними проложен маршрут. Связный граф – если каждая вершина является достижимой из любой другой. Изолированные вершины – вершины, не имеющие инцидентных ребер. Степень таких вершин нулевая. Изолированные вершины недостижимы из других вершин.

Ориентированные графы (орграфы) Каждое ребро (дуга) имеет одно направление Пример: в системе улиц имеются улицы с односторонним движением. Понятия: входящая степень вершины, исходящая степень вершины

Работа самостоятельно: указать множество вершин и их степени, множество ребер, мощность, конечность, наличие циклов, изолированных вершин, связность графов.