графы

Графы и их применение

ФИО преподавателя:
e-mail:

История появления графов

История появления графов

История появления графов

Задача о трёх домах и трёх колодцах
Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались.

История появления графов

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

История появления графов

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

История появления графов

Проблема четырех красок математическая задача предложенная Шотландским физиком Фредериком Гутри в 1852 как головоломка. Теорема о пяти красках, утверждающая, что достаточно пяти цветов, имела короткое несложное доказательство и была доказана в конце 19 века, но доказательство для случая с четырьмя красками вызвало значительные трудности. Более 100 лет задача для случая четырех красок не была решена.

История появления графов

Эта задача была решена только в 1976 году. В 1976 году Апель и Хейкен опубликовали решение этой задачи, которое базировалось на переборе вариантов с помощью компьютера.
 

История появления графов

В 1976 году ведущие математики всего мира получили письма с почтовым штемпелем «Четырех красок достаточно». В письмах была статья математиков Кеннета Аппеля и Вольфа Хакена из Иллинойского университета, содержащая доказательство теоремы.

История появления графов

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

История появления графов

В 1957 году учёный Келли разработал теорию перечисления деревьев в попытке найти изомер углевода.

История появления графов

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

Понятие графа

Графом в математике называется конечная совокупность точек, именуемых вершинами; некоторые из них соединены друг с другом линиями, называемыми ребрами графа.
 

Понятие графа

Вершины, прилегающие к одному и тому же ребру, называются смежными. Два ребра, у которых есть общая вершина, также называются смежными(или соседними).






Граф с шестью вершинами и семью ребрами.

Элементы графа

Петля это дуга, начальная и конечная вершина которой совпадают.
 

Нулевой граф

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






Рис. Нулевой граф

Полный граф

Полным называется граф, в котором каждые две вершины смежные.
 

Неполный граф

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

Степень графа

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






Нечётная степень Чётная степень

Степень графа

Степень графа

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

Лемма о рукопожатиях

В любом графе число нечётных вершин графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

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

Задача1 . В шахматный клуб пришли 7 человек, они сыграли между собой несколько партий. Могло ли так оказаться, что каждый из них сыграл ровно 3 партии? Каждую партию играют два человека.

Задача 1. В шахматный клуб пришли 7 человек, они сыграли между собой несколько партий. Могло ли так оказаться, что каждый из них сыграл ровно 3 партии? Каждую партию играют два человека.
Решение:
7 человек – это 7 вершин, 3- степень каждой вершины.
Нет, не сушествует, так как это нечётное число вершин нечётных степеней. Это противоречит Лемме о рукопожатиях.

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

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

Одним росчерком пера

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