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

Слайд 1

Министерство образования Нижегородской области ГБОУ СПО “Нижегородский автотранспортный техникум” Специальность “ Организация перевозок и управление на транспорте (по видам)” Творческая работа по математике «Основные понятия теории графов" Выполнила: Шабанова В.М. Группа: 1Э-15 Проверила: Демьянова Е.А . Нижний Новгород 2016

Слайд 2

Основоположники теории графов. Родилась теория графов в Санкт-Петербурге. Ее создателем является Л. Эйлер, который в 1736 году опубликовал решение задачи о Кенигсбергских мостах. Правило Леонарда Эйлера. 1. В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа. 2. В графе, имеющем две и только две вершины с нечетными степенями, существует обход с началом в одной вершине с нечетной степенью и концом в другой. 3. В графе, имеющем более двух вершин с нечетной степенью, такого обхода не существует. Доказательство правила Эйлера : Проходя в графе каждую вершину, за исключением начальной и конечной, мы войдём столько же раз, сколько выйдем из неё. Поэтому степени всех вершин должны быть чётными, кроме двух, а значит, Эйлеров граф имеет не более двух нечётных вершин.

Слайд 3

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

Слайд 4

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

Слайд 5

Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим участкам, четным или нечетным. Так, к участку A ведут пять мостов, а к остальным – по три моста, т. е. число мостов, ведущих к отдельным участкам, нечетно. Нельзя, прогуливаясь по городу, пройти по одному разу все мосты и вернуться обратно. Если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, но только начало обхода должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно.

Слайд 6

Кирх Гоф Кэлли Жордан В 1847 году Кирх Гоф разработал теорию деревьев для решения совместной системы линейных алгебраических уравнений, позволяющую найти значение силы тока в каждом проводнике (дуге) и в каждом контуре рассматриваемой электрической цепи. Кэлли в 1857 году, занимаясь чисто практическими задачами органической химии, открыл важный класс графов, называемый деревьями. Жордан (1869 год), независимо от Кэлли, ввел и изучал деревья как чисто математические объекты, совершенно не подозревая о значении своего открытия для современной химической науки.

Слайд 7

Д.Кениг Л.В.Канторович Начало бурного развития и практического применения теории графов было положено венгерским математиком Д. Кенигом, который опубликовал в 1936 г. монографию «Теория конечных и бесконечных графов». Российский академик Л. В. Канторович разработал метод решения транспортных задач для их сетевой постанов ки.

Слайд 8

Основные понятия и определения теории графов Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными. Граф, состоящий только из изолированных вершин, называется нуль-графом . Граф, в котором каждая пара вершин соединена ребром, называется полным. Степенью вершины называется число ребер, которым принадлежит вершина. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k . Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью. Путем от A до X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.

Слайд 9

Основные понятия и определения теории графов Циклом называется путь, в котором совпадают начальная и конечная точка. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза. Длиной пути, проложенного на цикле , называется число ребер этого пути. Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B. Граф называется связным , если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным. Деревом называется связный граф, не содержащий циклов. Трехмерной моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское – на поверхности земли. Несвязный граф, состоящий исключительно из деревьев, называется лесом . Дерево, все n вершин которого имеют номера от 1 до n , называют деревом с перенумерованными вершинами.

Слайд 10

Задача коммивояжера Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим? Жадный алгоритм “иди в ближайший (в который еще не входил) город”. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. Рассмотрим для примера сеть на рисунке представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди в ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

Слайд 11

Задача о четырех красках. Разбиение плоскости на непересекающиеся области называется картой . Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. Гипотеза не доказана до сих пор. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которая базировалось на переборе вариантов с помощью компьютера. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера . Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей.

Слайд 12

Задача Эйлера Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ? Решение . Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом.

Слайд 13

Спасибо за внимание