ВЫПОЛНИЛ: УЧЕНИК 11 КЛАССА «А» ЛОБЖА АРТЕМ ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: ОУ СОШ 51 Образовательное учреждение: г. Комсомольск – на – Амуре, 2012 год.

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



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

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

ВЫПОЛНИЛ: УЧЕНИК 11 КЛАССА «А» ЛОБЖА АРТЕМ ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: ОУ СОШ 51 Образовательное учреждение: г. Комсомольск – на – Амуре, 2012 год

/ 10 СОДЕРЖАНИЕ: ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: 2 ОУ СОШ 51 Образовательное учреждение: С ОДЕРЖАНИЕ ДАННОЙ ПРЕЗЕНТАЦИИ : 1 Общие понятия теории графов; 2 Эйлеровы и полу эйлеровы графы; 3 Гамильтоновы графы; 4 «Деревья»: определение и простейшие свойства; Г ЛАВА 1 Г ЛАВА 2Г ЛАВА 3Г ЛАВА 4

/ 10 ОБЩИЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ: ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: 3 Г ЛАВА 1 Г ЛАВА 2Г ЛАВА 3Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: Д ЛЯ НАЧАЛА, ДАДИМ ОПРЕДЕЛЕНИЕ ТЕРМИНА «ГРАФ». ГРАФ - НАБОР ТОЧЕК ( ЭТИ ТОЧКИ НАЗЫВАЮТСЯ ВЕРШИНАМИ), НЕКОТОРЫЕ ИЗ КОТОРЫХ ОБЪЯВЛЯЮТСЯ СМЕЖНЫМИ ( ИЛИ СОСЕДНИМИ ). С ЧИТАЕТСЯ, ЧТО СМЕЖНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ МЕЖДУ СОБОЙ РЕБРАМИ( ИЛИ ДУГАМИ ). Т АКИМ ОБРАЗОМ, РЕБРО ОПРЕДЕЛЯЕТСЯ ПАРОЙ ВЕРШИН. Д ВА РЕБРА, У КОТОРЫХ ЕСТЬ ОБЩАЯ ВЕРШИНА, ТАКЖЕ НАЗЫВАЮТСЯ СМЕЖНЫМИ ( ИЛИ СОСЕДНИМИ ) ( СМ. СХЕМУ ): ПРИМЕР ГРАФА:

/ 10 СХЕМА: ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: Г ЛАВА 1 Г ЛАВА 2Г ЛАВА 3Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: Вершины графа; Ребра графа; Дуги графа; «Петля» графа; НА ДАННОЙ СХЕМЕ ВЫ СМОЖЕТЕ УВИДЕТЬ ОСНОВНЫЕ КОМПОНЕНТЫ, ИЗ КОТОРЫХ СОСТОИТ ГРАФ: 4

/ 10 СХЕМА: ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: Г ЛАВА 1 Г ЛАВА 2Г ЛАВА 3Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: 5 Виды графов: На нынешний момент выделяют три основных вида графов: Если в графе допускается существование повторяющихся ребер, то граф называется МУЛЬТИГРАФОМ; Если в графе, кроме того, допускается существование петель, т.е. ребер, соединяющих вершину саму с собой, то граф называется ПСЕВДОГРАФОМ; Граф называется ОРИЕНТИРОВАННЫМ (или ОРГРАФОМ), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет.

/ 10 ОБЩИЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ: ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: Г ЛАВА 1 Г ЛАВА 2Г ЛАВА 3Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: 6 ЦИКЛ: ПРОСТОЙ ПУТЬ: Существуют всего четыре последовательности вершин в графе: МАРШРУТ В ГРАФЕ – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают НАПРАВЛЕНИЕ). Заметим, что в маршруте могут повторяться вершины, но не ребра. 1 МАРШРУТ: КОНТУР:

/ 10 ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: Г ЛАВА 1 Г ЛАВА 2Г ЛАВА 3Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: 7 ЦИКЛ: ПРОСТОЙ ПУТЬ: Маршрут называется ЦИКЛОМ, если в нем первая вершина совпадает с последней; 2 МАРШРУТ: КОНТУР: ОБЩИЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ: Существуют всего четыре последовательности вершин в графе:

/ 10 ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: Г ЛАВА 1 Г ЛАВА 2Г ЛАВА 3Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: 8 ЦИКЛ: ПРОСТОЙ ПУТЬ: ПУТЬ В ГРАФЕ (иногда говорят ПРОСТОЙ ПУТЬ) – это маршрут без повторения вершин (а значит, и ребер); 3 МАРШРУТ: КОНТУР: ОБЩИЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ: Существуют всего четыре последовательности вершин в графе:

/ 10 ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: Г ЛАВА 1 Г ЛАВА 2Г ЛАВА 3Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: 9 ЦИКЛ: ПРОСТОЙ ПУТЬ: КОНТУР – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней; 4 МАРШРУТ: КОНТУР: ОБЩИЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ: Существуют всего четыре последовательности вершин в графе:

/ 10 ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: Г ЛАВА 1 Г ЛАВА 2 Г ЛАВА 3Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: 10 ЭЙЛЕРОВЫ И ПОЛУЭЙЛЕРОВЫ ГРАФЫ: ФОРМУЛИРОВКА ЗАДАЧИ: Можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз? Именно с задач, поставленных и решенных в этом разделе, началась теория графов. Философ ИММАНУИЛ КАНТ, гуляя по г. Кенигсбергу, поставил задачу (1736), известную в математике как ЗАДАЧА О СЕМИ КЕНИГСБЕРГСКИХ МОСТАХ. Знаменитый математик швейцарского происхождения ЛЕОНАРД ЭЙЛЕР блестяще решил эту задачу:

/ 10 ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: Г ЛАВА 1 Г ЛАВА 2 Г ЛАВА 3Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: 11 ЭЙЛЕРОВЫ И ПОЛУЭЙЛЕРОВЫ ГРАФЫ: В соответствии с поставленной КАНТОМ (и решенной ЭЙЛЕРОМ) задачей можно дать следующие определения: 1 Граф (или мультиграф без петель) называется ЭЙЛЕРОВЫМ, если существует цикл без повторения ребер (такой цикл называют ЭЙЛЕРОВЫМ), обходящий все вершины графа. 2 Граф называется ПОЛУЭЙЛЕРОВЫМ, если существует маршрут без повторения ребер (ЭЙЛЕРОВ ПУТЬ), обходящий все ребра графа ровно один раз. Виды графов: ЭЙЛЕРОВ ГРАФ: ПОЛУЭЙЛЕРОВ ГРАФ:

/ 10 ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: Г ЛАВА 1Г ЛАВА 2 Г ЛАВА 3 Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: ГАМИЛЬТОНОВЫ ГРАФЫ: Кратко рассмотрим проблему, связанную с возможным обходом всех вершин в графе: существует ли в данном (СВЯЗНОМ) графе цикл (ИЛИ МАРШРУТ), обходящий каждую вершину (кроме первой) ТОЛЬКО ОДИН РАЗ? ГАМИЛЬТОНОВ ГРАФ: Если такой цикл существует (в этом случае такой цикл будет контуром), то граф называется ГАМИЛЬТОНОВЫМ, и соответствующий цикл также называют гамильтоновым циклом. 12 ПОЛУГАМИЛЬТОНОВ ГРАФ: Если такой цикл (маршрут) существует (в этом случае такой маршрут будет путем), то граф называется ПОЛУГАМИЛЬТОНОВЫМ, и соответствующий путь также называют полугамильтоновым путем. ГАМИЛЬТОНОВ ГРАФ: ПОЛУГАМИЛЬТОНОВ ГРАФ:

/ 10 «ДЕРЕВЬЯ»: ОПРЕДЕЛЕНИЕ И ПРОСТЕЙШИЕ СВОЙСТВА ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: 13 Г ЛАВА 1Г ЛАВА 2Г ЛАВА 3 Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: Д ЛЯ НАЧАЛА, ДАДИМ ОПРЕДЕЛЕНИЕ ТЕРМИНА « ДЕРЕВО ». ДЕРЕВО - СВЯЗНЫЙ ГРАФ БЕЗ КОНТУРОВ ( А ЗНАЧИТ, И БЕЗ ЦИКЛОВ ). Г РАФ ( НЕСВЯЗНЫЙ ), СОСТОЯЩИЙ ИЗ НЕСКОЛЬКИХ ДЕРЕВЬЕВ ИНОГДА НАЗЫВАЮТ ЛЕСОМ. Н АПОМНИМ, ЧТО ВЕРШИНА В ГРАФЕ НАЗЫВАЕТСЯ ВИСЯЧЕЙ, ЕСЛИ ЕЕ СТЕПЕНЬ РАВНА ЕДИНИЦЕ. Д ЕРЕВО ДОЛЖНО ОБЯЗАТЕЛЬНО ИМЕТЬ ВИСЯЧУЮ ВЕРШИНУ, ТАК КАК ЕСЛИ БЫ СТЕПЕНЬ ВСЕХ ВЕРШИН В ДЕРЕВЕ БЫЛА БЫ БОЛЬШЕ ИЛИ РАВНА 2, ТО ПО САМОЙ ПЕРВОЙ ЛЕММЕ (Л ЕММА 1: Е СЛИ СТЕПЕНЬ ВСЕХ ВЕРШИН В ГРАФЕ БОЛЬШЕ ИЛИ РАВНА ДВУМ, ТО ГРАФ ОБЯЗАТЕЛЬНО СОДЕРЖИТ КОНТУР ) ГРАФ ДОЛЖЕН ИМЕТЬ ЦИКЛ, ЧТО ПРОТИВОРЕЧИТ ОПРЕДЕЛЕНИЮ ДЕРЕВА.

/ 10 СХЕМА: ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: 14 Г ЛАВА 1Г ЛАВА 2Г ЛАВА 3 Г ЛАВА 4 ОУ СОШ 51 Образовательное учреждение: На данной схеме отражены основные свойства «деревьев»: Простейшие свойства «деревьев»: Если граф G является «деревом», то: Число ребер (p) и число вершин в графе (q) связаны соотношением p = q – 1; Любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен; !! Граф G связен и не содержит контуров.

ВЫПОЛНИЛ: УЧЕНИК 11 КЛАССА «А» ЛОБЖА АРТЕМ СПАСИБО ЗА ВНИМАНИЕ! ОУ СОШ 51 Образовательное учреждение: г. Комсомольск – на – Амуре, 2012 год