Проектное исследование по теме "Начальные понятия теории графов"

Слайд 1

Проектное исследование по теме: «НАЧАЛЬНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ» Учеников 11 класса МБОУ СОШ №8 Рыбалкина Евгения Стародубцева Александра

Слайд 2

необходимость решать алгебраические и математические задачи различными способами. Объект исследования: процесс решения нестандартных задач. Предмет исследования: развитие навыка построения графических схем, развитие умения решать нетипичные задачи курсов алгебры и математики. Актуальность:

Слайд 3

узнать о значении теории графов; научиться применять полученные знания в реальной жизни. Цель

Слайд 4

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

Слайд 5

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых . Граф

Слайд 6

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

Слайд 7

Аркадий , Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? Задача

Слайд 8

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

Слайд 9

Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки — ребрами графа. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; Длины отрезков и расположение точек произвольны. Например, все три фигуры на рисунке изображают один и тот же граф. Задача

Слайд 10

Рассмотрим процесс соединения точек А, Б, В, Г, Д ребрами. 1. Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему, изображенную на рисунке Такая схема, состоящая из «изолированных» вершин, называется нулевым графом. 2. Ситуация, когда совершены еще не все рукопожатия, может схематически быть изображена, например, с помощью рисунка З: пожали руки А и Б, А и Г, Д и Г, В и Д. Графы, в которых не построены все возможные ребра , называются неполными графами. 3. На рисунке 4 изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом . Задача Если подсчитать число ребер графа, изображенного на рисунке 4, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.

Слайд 11

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2 Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2: Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа . Задача

Слайд 12

1 . Задачи о мостах. 2. Логические задачи 3. Задачи о "правильном" раскрашивании карт 4. Задачи на построение уникурсальных графов ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ШКОЛЬНОМ КУРСЕ МАТЕМАТИКИ.

Слайд 13

Были решены задачи с использованием графов, приведены примеры различных задач из других областей науки и техники. С помощью графов решать задачи очень удобно, интересно, увлекательно, можно рассмотреть несколько вариантов решения одной и той же задачи и выбрать наиболее легкое, удобное, красивое, интересное решение задачи. ЗАКЛЮЧЕНИЕ

Слайд 14

http:// sch216.narod.ru/nayka/doc/graf.htm http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_% D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 http:// school-sector.relarn.ru/dckt/projects/ctrana/graf/gr1.htm http://www.intuit.ru/studies/courses/101/101/lecture/1549 Источники