Проект: «Графы». Цели проекта: изучить теорию «Граф», изучить теорию «Граф», развить навыки самостоятельной работы, развить навыки самостоятельной работы, - презентация

1 Проект: «Графы»

2 Цели проекта: изучить теорию «Граф», изучить теорию «Граф», развить навыки самостоятельной работы, развить навыки самостоятельной работы, овладеть методикой исследования и экспериментирования при решении задач с использованием «Граф», овладеть методикой исследования и экспериментирования при решении задач с использованием «Граф», воспитывать толерантность. воспитывать толерантность.

3 Применение «Граф» Схема метро Схема метро Схема авиалиний

4 Применение «Граф» Вершины и ребра этих графов отвечают соответственно атомам и химическим связям между ними (химия). Вершины и ребра этих графов отвечают соответственно атомам и химическим связям между ними (химия).атомам Схема электрической цепи (физика)

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

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

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

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

9 Задача. Первенство класса. В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина с Андреем и Борисом; Дмитрий – с Виктором и Елена – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?

10 Задача. Кто играет Ляпкина – Тяпкина? В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина – Тяпкина. - Ляпкиным – Тяпкиным буду я! – решительно заявил Гена. - Нет, я буду Ляпкиным – Тяпкиным, возразил Дима.- С раннего детства мечтал воплотить этот образ на сцене. - Ну, хорошо, уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена. - …А мне – Осипа, - не уступил ему в великодушии Дима. - Хочу быть Земляникой или Городничим,- сказал Вова. - Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно. Удастся ли распределить роли так, чтобы исполнители были довольны?

11 Решение:

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

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

14 Теория граф Эйлера Закономерность1. Закономерность1. Невозможно начертить граф с нечетным числом нечетных вершин. Невозможно начертить граф с нечетным числом нечетных вершин. Закономерность 2. Закономерность 2. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. Закономерность 3. Закономерность 3. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. Закономерность 4. Закономерность 4. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». ТЕОРЕМА. ТЕОРЕМА. Граф является эйлеровым тогда и только тогда, когда он связан и имеет не более двух нечетных вершин. Граф является эйлеровым тогда и только тогда, когда он связан и имеет не более двух нечетных вершин.

15 Вернемся теперь к задаче о кенигсбергских мостах.

16 . Деревья. Деревом называется любой связный граф, не имеющий циклов Циклом называется путь, в котором совпадают начало с концом. Путем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами Висячей вершиной называется вершина, из которой выходит ребро. ТЕОРЕМА. В дереве число вершин на одну больше числа ребер.

17 Часть генеалогического дерева знаменитого дворянского рода- писателя Льва Николаевича Толстого. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.

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

19 Ориентированные графы. Граф, на рёбрах которого расставлены стрелки, называется ориентированным.

20 Леонард Эйлер ( ) Портрет работы Иогана Кеннга. 1881г