Исследовательская работа на тему "Графы"

Выполнила: Мухина Анна, ученица 9А класса Руководитель: Колчанова Г.Р. учитель математики

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

Цель: рассмотреть решение задач с использованием «Граф», рассмотреть «Графы» на примерах алгоритмов и родословных деревьев Задачи:  Изучить научно- популярную литературу по  Проанализировать результаты проведенных данному вопросу. экспериментов

 Граф - система, которая интуитивно может быть рассмотрена      как множество кружков и множество соединяющих их. Кружки      называются вершинами графа, линии со стрелками - дугами,      без стрелок -ребрами.  Начало теории графов датируют 1736 г., когда Л. Эйлер решил      популярную в то время «задачу о кенигсбергских мостах».  Термин «граф» впервые был введен спустя 200 лет (в 1936 г .) Д. Кенигом.  Математические графы с дворянским титулом «граф» связывает общее  Графами являются алгоритмы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего. происхождение от латинского слова «графио» - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог. Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами.    Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину.

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

 Рассмотрим задачу о поиске выхода из лабиринта, коридоры которого не возникает, например, при блуждании обязательно находятся на одном уровне. Подобная ситуация в пещерах или катакомбах. Корт  На рисунке изображен интересный пример лабиринта в саду Хемптон  Построим соответствующий ему граф. Коридоры лабиринта – это ребра графа, а перекрестки, тупики, входы и выходы – это вершины.  Теперь хорошо видно, что в центр лабиринта можно попасть, следуя по  И, соответственно, выйти из центра следующим вершинам: 1 - 4 - 7 - 10 - 9 - 11 - 12 - 13. лабиринта по маршруту: 13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.

Подробнее графы мы рассмотрим на двух примерах:  Алгоритмы  Родословные деревья

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

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

Использует графы и дворянство, только здесь они представлены в виде генеалогических деревьев. Мы рассмотрим два знаменитых рода.

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

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