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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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