Графы_7634




Графы

Математические и только.

Автор: Михайленко Александра ученица СОШ №1 г. Пугачёва

План:

Введение

Цель работы

История графов

Свойства и разновидности графов

Интересные задачи с графами

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

Вывод

Список литературы

«Математика — это язык, на котором написана книга природы»

Г. Галилей

Введение

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

«У всякого человека в отдельности и у всех вместе есть, можно сказать, известная цель, стремясь к которой они одно избирают, другого избегают»

Аристотель

Цель работы



Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» — пишу. Но кто придумал эти графы? Где они применяются? Все ли они одинаковые или есть разновидности? На эти вопросы мне и следует ответить.

«Мы не можем понять эту формулу, и мы не знаем, что она значит, но мы доказали ее и поэтому знаем, что она должна быть достоверной»

Некий профессор математики об одной из теорем Л. Эйлера



История графов

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

Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград), поставил задачу (1736), известную в математике как задача о семи кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз. Наш петербургский знаменитый математик швейцарского происхождения Леонард Эйлер блестяще решил эту задачу.

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

Графы в физике реферат

Рисунок 1

Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки называют вершинами графа, а линии, которые соединяют вершины — ребрами графа. На рисунке 1 из вершин А, С, Е выходят по 3 ребра, а из вершины В -5 ребер. Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, — четными. Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа.

«Математическая истина, независимо от того, в Париже или в Тулузе, одна и та же»

Блез Паскаль

Свойства и разновидности графа

Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.



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

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

Задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков — К. Берж, О. Оре, А. Зыков.

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

Графы в физике реферат

Рисунок 2

Если подсчитать число ребер графа, изображенного на рисунке 2, то это число и будет равно 10, этот граф полный. Заметим, что если полный граф имеет n вершин, то количество ребер будет равно

n(n-1)/2

Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2.

Эйлеров и полуэйлеровый граф

Граф называется эйлеровым, если существует цикл без повторения ребер обходящий все вершины графа. Граф называется полуэйлеровым, если существует маршрут без повторения ребер (эйлеров путь), обходящий все ребра графа ровно один раз. На рисунке 3 изображены: А) эйлеров граф, В) полуэйлеров граф и С) граф, не являющийся ни эйлеровым, ни полуэйлеровым. Существует много загадок типа “можно ли нарисовать данную фигуру, не отрывая ручку от бумаги”, что и соответствует эйлерову или полуэйлерову графу.

История графыИнтересные задача на графыА)Графы в физике рефератВ)С)

Рисунок 3

«В математике следует помнить не формулы, а процессы мышления»

В. П. Ермаков

Задачи с графами

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

Вот, например, как выглядит последняя американская версия известной задачи Дьюдени:

1. Смит, Джонс и Робинсон работают в одной поездной бригаде машинистом, кондуктором и кочегаром. Профессии их названы не обязательно в том же порядке, что и фамилии. В поезде, который обслуживает бригада, едут трое пассажиров с теми же фамилиями. В дальнейшем каждого пассажира мы будем почтительно называть «мистер» (м-р)

2. М-р Робинсон живет в Лос-Анджелесе.

3. Кондуктор живет в Омахе.

4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.

5. Пассажир – однофамилец кондуктора живет в Чикаго.

6. Кондуктор и один из пассажиров, известный специалист по математической физике, ходят в одну церковь.

7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.

Как фамилия машиниста?

Здесь 1-5 – номера ходов, в скобках – номера пунктов задачи, на основании которых сделаны ходы (выводы).

Графы в физике реферат

Далее следует из п.7, что кочегар не Смит, следовательно, Смит-машинист.

А всегда ли можно так изобразить любой граф на плоскости, чтобы его рёбра не пересекались? Впервые этот вопрос возник при решении старой головоломки. Вот как её описывает Льюис Кэрролл.

Три человека жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам. Однажды эти люди перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались. Первоначальный вариант, изображенный на рисунке, по этой причине их не устраивал (рисунок 1).

Интересные задачи на графы

Рисунок 1

На втором рисунке изображена очередная попытка продолжить тропинки, на которых осталось непроведенных только одна тропинка (рисунок 2). Но эта задача до сих пор не решена.

История графы

«Математика — это язык, на котором говорят все точные науки»

Н.И. Лобачевский

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

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

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

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

Графы и биология

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

Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

Графы и информация

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

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

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

Графы и физика

Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.

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

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

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

«Математика принадлежит к числу тех наук, которые ясны сами по себе»

К. Якоби

Вывод

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

Список литературы:

Энциклопедический словарь юного математика

Я познаю мир «математика»

Школьная энциклопедия «математика»

Википедия????








sitemap
sitemap