Проект "Его величество граф"

Проект по теории графов «Его величество граф»

Выполнила: ученица 7Б класса, АОУ школы № 6 Исхакова Дания

Учитель: Кондрашова С.И.

г. Долгопрудный, 2016 г.

проект «ЕГО ВЕЛИЧЕСТВО ГРАФ»

Введение

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

История возникновения графов

Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер , рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.

Что такое граф

В математике определение графа дается так:

Графом называется конечное множество точек, некоторые из которых соединены линиями.

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

Рёбра графа

Вершина графа

Что такое граф

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

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

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

ГАМИЛЬТОНОВЫМ ПУТЕМ (ЦИКЛОМ) ГРАФА

называется путь(цикл), проходящий через

каждую его вершину только один раз.

Граф, содержащий гамильтонов цикл, называется гамильтоновым .

A

B

(C, D, A, B, E) – гамильтонов путь

D

E

C

B

u

r

t

A

s

C

ЦИКЛ – ПУТЬ, У КОТОРОГО СОВПАДАЮТ НАЧАЛО И КОНЕЦ.

8

Деревом называется связный граф, не имеющий циклов

D

F

B

C

E

A

G, H, E, B, A - ВИСЯЧИЕ ВЕРШИНЫ

H

G

9

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

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

Решая задачу О кенигсбергских мостах, Эйлер сформулировал свойства графа:

« Невозможно начертить граф с нечетным числом нечетных вершин»

9

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

Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.

9

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

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

9

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

Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то такой граф начертить «одним росчерком» невозможно.

9

Практическое задание:

9

Логические задачи

9

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

Решение.

9

Задача:

Шахматный турнир проводится по круговой системе, при которой каждый участник встречается с каждым ровно один раз.

Известно, что в настоящий момент:

• Ваня сыграл шесть партий;
• Толя сыграл пять партий;
• Леша и Дима сыграли по три партии;
• Семен и Илья сыграли по две партии;
• Женя сыграл одну партию.

Пригласить старшеклассников для показа. Лена Павловна им торжественно вручает: ватман, ручку, клей, кружки и серпантин

Требуется определить:

с кем сыграл Леша.

9

Для решения задачи будем использовать геометрическое представление графа

Изобразим участников турнира точками

Для каждой точки укажем ее имя

и количество партий, сыгранные этим игроком

Т оля (5)

Л еша (3)

В аня (6)

Д има (3)

Число в скобках называют степенью вершины, оно показывает сколько ребер выходит из данной вершины

Ж еня (1)

С емен (2)

И лья (2)

9

Теперь однозначно определяются ребра вершины Т.

С учетом ребра ВТ надо построить четыре ребра

Начать построение ребер следует с вершины В,

так как это единственная вершина,

которая соединяется со всеми другими вершинами графа

Т оля (5)

Л еша (3)

В аня (6)

Д има (3)

Все возможные ребра теперь построены для вершин Ж, В, Т,

и для вершин С и И

Ж еня (1)

С емен (2)

И лья (2)

9

Теперь становится очевидным, каким должно быть недостающее ребро.

Оно должно соединить вершины Л и Д

Т оля (5)

Л еша (3)

В аня (6)

Д има (3)

Ж еня (1)

Леша играл с Толей, Ваней и Димой

С емен (2)

И лья (2)

9

Практическое задание:

Задача : В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта - в корзинах А. Б, Г; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д - третьего. Пронумеруйте каждую корзину так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно); в корзине № 2-второго и т.д.

Решение: Составим граф:

9

Применение графов

Лабиринт - это граф. А исследовать его - это найти путь в этом графе.

9

Первый многосвязный садовый лабиринт был сооружён в 1820-е годы в Чевнинге в Великобритании.

9

Граф для садового лабиринта

9

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

9

Выводы

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

В математике даже есть специальный раздел, который так и называется: « Теория графов ».

9

9