Презентация к уроку математики "Графы"

ТОГАПОУ Техникум отраслевых технологий

ГРАФЫ

Выполнил студент 2 курса Беляев Олег

Преподаватель Кобзева Н.П.

История возникновения теории графов

Математические графы с дворянским титулом "граф" связывает общее происхождение от лат. слова "графио" - пишу.

Впервые основы теории графов появились в работе члена Петербургской академии наук,  выдающегося математика Леонардо Эйлера, где он описывал решение головоломок и математических развлекательных задач.

Среди них знаменитая задача о Кенигсбергских мостах. Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград), поставил задачу: можно ли пройти по всем семи мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз.

В1736 году задача о семи мостах заинтересовала Леонарда Эйлера. Он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.

История возникновения теории графов

История возникновения теории графов

Если, внимательно рассмотреть географическую карту, можно заметить, что есть еще один – граф, состоящий из границ между странами (областями, районами).

В 1852 году английский студент Френсис Гутри раскрашивал карту Великобритании. Каждое графство он выделял цветом. Выбор красок у него был невелик, и приходилось их использовать повторно. Гутри старался, чтобы два графства, имеющие общий участок границы, были окрашены в разные цвета. Это заставило его задуматься о том, какого наименьшего числа красок достаточно для раскрашивания любой карты. Гутри считал, что четырех красок всегда хватит, но доказать это не мог.

Первые решения данной задачи появились в 1879 году. Доказательство опубликовал Альфред Кемпе- британский математик, а год спустя Питер Тэт - шотландский математик и физик.

Существует задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Возможно ли провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена польским математиком Куратовским в 1930 году.

В 1975 году преподавателем архитектуры Будапешта Эрне Рубиком для развития пространственного воображения у студентов изобрел головоломку Кубик Рубика.

В 1859 г. английский математик Уильям Гамильтон выпустил в продажу головоломку. Она представляла собой деревянный додекаэдр(12-гранник), в вершинах которого вбиты гвоздики. Каждая из 20 вершин была помечена названием одного из крупных городов мира – Дели, Брюссель и т.д. Требовалось найти замкнутый путь, проходящий по ребрам додекаэдра и позволяющий побывать в каждой его вершине по одному разу. Путь следовало отмечать с помощью шнура, зацепляя его за гвоздики.

Решить все эти задачи или доказать, что они не имеют решений возможно с помощью теории графов!

Основные понятия теории графов

Граф – это набор точек, каждые из которых соединены линиями. Точки – называются вершинами, а соединяющие их линии ребрами.

Графы, в которых не построены все возможные ребра, называются неполными графами

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом

Основные понятия теории графов

Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Графы, в которых построены все возможные ребра, называются полными графами

Основные понятия теории графов

Маршрутом в графе называется последовательность рёбер, в которой соседние рёбра имеют общую вершину. Первая вершина называется нача­лом маршрута, последняя — концом.

Путём (или цепью) в графе называется маршрут, в котором нет повто­ряющихся рёбер. Если в пути нет повторяющихся вершин, его называют простым путём. Длина маршрута равна количеству рёбер в порядке их про­хождения. Расстоянием между вершинами в графе называют длину крат­чайшего пути от одной вершины до другой.

Граф-путь с 6 вершинами

Цикл — это путь, у которого совпадают начало и конец. Если в цик­ле все вершины разные, его называют простым циклом. Если в цикле все рёбра разные, то такой цикл называется эйлеровым. Маршрут, содержа­щий все рёбра или все вершины графа, называется обходом графа.

Цикл графа 1, 2, 5, 4, 3, 1

Виды графов

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

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

Виды графов

Если в связном графе после удаления ребра граф превратится в несвяз­ный, такое ребро называют мостом. На рисунке граф с 6 мостами выделены красным.

Виды графов

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым.

Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.

Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.

Виды графов

• Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
• Граф является эйлеровым тогда и только тогда, когда он связан и имеет не более двух нечетных вершин.

Виды графов

Особым видом графа является дерево. Деревом называется любой связный граф, не имеющий циклов.

В дереве нельзя вернуться в исходную вершину, двигаясь по рёбрам и проходя по одному ребру не более одного раза.

В дереве любые две вершины соединены ровно одним путём.

В дереве есть вершина, из которой выходит только одно ребро. Такая вершина называется висячей.

При удалении любого ребра из дерева граф становится несвяз­ным.

Плоским графом называют такой граф, который можно нарисовать на плоскости так, чтобы его рёбра не пересекались нигде, кроме вершин.

Виды графов

Ориентированный граф — это граф, рёбрам которого присвоено направление, т.е. нанесены стрелочки. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами.

Неориентированный граф — это граф, в котором все ребра являются неупорядоченными парами вершин, т.е. возможно прохождение из вершины в вершину в обоих направлениях.

СПАСИБО ЗА ВНИМАНИЕ!