Элементы теории графов. Задачи, сводящиеся к графам - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Элементы теории графов. Задачи, сводящиеся к графам, слайд №1

Элементы теории графов. Задачи, сводящиеся к графам, слайд №2

Элементы теории графов. Задачи, сводящиеся к графам, слайд №3

Элементы теории графов. Задачи, сводящиеся к графам, слайд №4

Элементы теории графов. Задачи, сводящиеся к графам, слайд №5

Элементы теории графов. Задачи, сводящиеся к графам, слайд №6

Элементы теории графов. Задачи, сводящиеся к графам, слайд №7

Элементы теории графов. Задачи, сводящиеся к графам, слайд №8

Элементы теории графов. Задачи, сводящиеся к графам, слайд №9

Элементы теории графов. Задачи, сводящиеся к графам, слайд №10

Элементы теории графов. Задачи, сводящиеся к графам, слайд №11

Элементы теории графов. Задачи, сводящиеся к графам, слайд №12

Элементы теории графов. Задачи, сводящиеся к графам, слайд №13

Элементы теории графов. Задачи, сводящиеся к графам, слайд №14

Элементы теории графов. Задачи, сводящиеся к графам, слайд №15

Элементы теории графов. Задачи, сводящиеся к графам, слайд №16

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Элементы теории графов. Задачи, сводящиеся к графам. Доклад-сообщение содержит 16 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Элементы теории графов. Задачи, сводящиеся к графам. Проверила: Елова О.И. Подготовила студентка 1-го курса Факультета инженерной механики Кафедры стандартизации, сертификации и управления качеством производства нефтегазового оборудования Группы МП-15-06 Настенко Т.В.

Слайд 2

Описание слайда:

Содержание: Теория графов. История возникновения. Что же такое граф? Связность. Теоремы о связности. Задача о кёнигсбергских мостах. Выводы Эйлера. Примеры задач. «Деревья» . Приложение.

Слайд 3

Описание слайда:

ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения.

Слайд 4

Описание слайда:

История возникновения теории Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах , ставшей впоследствии одной из классических задач теории графов.

Слайд 5

Описание слайда:

Что же такое граф? Граф G =< V, E > есть совокупность множества вершин V и множества рёбер (дуг) , причем E ⊆ V × V есть множество упорядоченных пар < x, y > для ориентированного графа и E ⊆ {{x, y} : (x, y ∈ V)&(x 6= y)} для неориентированного графа (при этом для неориентированного графа считаем, что ребра {a, b} и {b, a} совпадают {a, b} = {b, a}). Граф неориентированный, если все его ребра не ориентированы, и граф ориентированный, если все его ребра ориентированы.

Слайд 6

Описание слайда:

Слайд 7

Описание слайда:

Связность Пусть граф G — неориентированный. Две вершины a и b называются связанными, если существует путь S с начальной вершиной a и конечной вершиной b, S =< a, a1, ..., an, b >. Если S проходит через какую-нибудь вершину ai более одного раза, то можно, очевидно, удалить его циклический участок и при этом остающиеся ребра будут составлять путь S 0 из a в b. Отсюда следует, что связанные путем вершины связаны и простым путем. Граф называется связным, если любая его пара вершин связана.

Слайд 8

Описание слайда:

Теоремы о связности. Если в конечном неориентированном простом графе G ровно две вершины a и b имеют нечетную локальную степень, то они связаны. Если неориентированный простой граф G имеет n вершин и k связных компонент, то максимальное число ребер в G равно N(n, k) = 0.5(n − k)(n − k + 1). Простой неориентированный граф с n вершинами и с числом ребер, большим, чем N(n, 2) = 0.5(n − 1)(n − 2) связан.

Слайд 9

Описание слайда:

Задача о кёнигсбергских мостах.

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Примеры задач: Задача 1. Лист бумаги Плюшкин (Н.В.Гоголь "Мертвые души") разрезает на три части. Некоторые из полученных листов он также разрезает на три части. Несколько новых листков он вновь разрезает на три более мелкие части и так далее. Сколько Плюшкин получает листиков бумаги, если разрезает листов? Решение. Будем считать листы бумаги вершинами графа. При разрезании одного листка на три части число листков увеличивается на два (появляются три новых вместо одного). Если же было разрезано листов, то образовалосьлистов.