Основные ПОНЯТИЯ ТЕОРИИ ГРАФОВ. Граф И ЕГО СВОЙСТВА ПРИМЕРЫ ГРАФОВ.

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



Advertisements
Похожие презентации
Домашнее задание «Применение графа» ВСПОМНИМ… Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью.
Advertisements

Фигура (граф), которую можно начертить не отрывая карандаш от бумаги, называется уникурсальной.
Тайны граф в. Обучающее занятие по теории графов Выполнили: ученики 8 «А» класса МОУ гимназии «Дмитров» Руководитель: Москевич Л.В.
V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E – множества, отображение инциденции f: Е V&V множества Е в V&V Основы.
Решение задач с помощью графов. Кенигсбергские мосты Можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?
1. Познакомить слушающих с определением графа. 2. Понять, как решаются задачи с помощью графов. 3. Закономерности, которые необходимо соблюдать при решении.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ И ЕГО ЭЛЕМЕНТОВ. ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ.
ЕГО ВЕЛИЧЕСТВО ГРАФ. Введение С дворянским титулом «граф» эту тему связывает только общее происхождение от латинского слова «графио» - пишу. ГРА Ф ИО.
Проект: «Графы». Цели проекта: изучить теорию «Граф», изучить теорию «Граф», развить навыки самостоятельной работы, развить навыки самостоятельной работы,
1. Основные понятия теории графов 1. Основные понятия теории графов 2. Степень вершины Введение 5. Ориентированные графы 6. Изоморфизм графов 7. Плоские.
Определение графа Фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек, называется плоским графом, или.
примеры геометрических фигур и букв нашего алфавита, которые можно изобразить, не отрывая карандаша.
Тема: Графы Преподаватель Белгородцева Н.А. Дискретная математика.
Дата проведения занятия. Задача о Кенигсбергских мостах: Пройти по всем мостам так, чтобы на каждом побывать лишь один раз и вернуться к тому месту, откуда.
ГРАФЫ … ГРАФЫ ??? ГРАФЫ ??? ГРАФЫ !!! ГРАФЫ !!!. Задача 1 Между девятью планетами Солнечной системы установлено космическое сообщение. Рейсовые ракеты.
Учитель математики Егорчева Виктория Андреевна г г. Муниципальное общеобразовательное бюджетное учреждение – средняя общеобразовательная школа.
Графы Цели урока Повторить определения, теоремы теории графов Научиться строить графы Научиться применять графы к решению практических задач.
Графы Построить конверт не отрывая карандаша от бумаги и не проводя по одной линии дважды.
Графы Автор: Баум Маргарита Муниципальное автономное общеобразовательное учреждение Тисульская средняя общеобразовательная школа 1 Руководитель: Пода Надежда.
Графы Автор: Баум Маргарита Муниципальное автономное общеобразовательное учреждение Тисульская средняя общеобразовательная школа 1 Руководитель: Пода Надежда.
Транксрипт:

Основные ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Граф И ЕГО СВОЙСТВА ПРИМЕРЫ ГРАФОВ

ЗАДАЧА: НАЙТИ КРАЙЧАЙШИЙ ПУТЬ. Решение. Дано: Иа-Иа (О) Винни-Пух (В) Пятачок (П) Кролик (К) Надо: Найти кратчайший путь

РЕШЕНИЕ:

ГРАФЫ Вершины ГРАФА РЕБРА ГРАФА НУЛЕВОЙ ГРАФ НЕПОЛНЫЙ ГРАФ НОЛНЫЙ ГРАФ Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2

ЗАКОНОМЕРНОСТИ СТЕПЕНЬ ВЕРШИНЫ 1) Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа. 2) Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива не только для полного, но и для любого графа. Число нечетных вершин любого графа четно.

Кенигсбергские мосты 1) Невозможно начертить граф с нечетным числом нечетных вершин. 2) Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине 3) Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. 4) Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». Фигура (граф), которую можно начертить не отрывая карандаш от бумаги, называется уникурсальной.

Путь в графе. Цикл. Путем в графе … конец пути… Циклом Эйлеровой линией

Связные графы. Две вершины графа называются связными … вершины называются не связными… Граф называется связным… Граф называется несвязным … Мостом НАЗЫВАЕТСЯ …

ДЕРЕВЬЯ Деревом НАЗЫВАЕТСЯ Всякое ребро в дереве является мостом. Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева. Для каждой пары вершин дерева существует единственный путь, их соединяющий.

Изоморфные графы. Плоские ГРАФЫ. изоморфными (одинаковыми)ГРАФАМИ НАЗЫВАЕТСЯ…. плоским графом НАЗВАЕТСЯ… Гранью плоского графа называется …

Формула ЭЙЛЕРА В-Р+Г=2 Ребро графа называется ориентированным ребром… ориентированным графом называется … Степенью выхода вершины … Степенью входа вершины… Путем называется Ориентированным циклом называется … расстоянием между вершинами графа…