VI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Начальное представление о графах
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Очень часто на уроках математики и в конкурсных олимпиадных заданиях попадаются логические задачи. Мне хотелось научиться правильно находить ответы. Поэтому, чтобы проверить верность своего решения, я нашла в литературе такое математическое понятие, как ГРАФ.
В своей работе я хочу рассказать, что я узнала про графы, как их можно использовать при решении несложных логических задач. Привести примеры решения задач с помощью графов из онлайн-олимпиад, в которых я участвовала.
Целью данной работы является познакомиться с начальными понятиями из раздела математики теория графов, применить эти знания на практике.
Задачи работы для себя я обозначила так:
Найти в литературе информацию о графах.
Изучить начальные понятия графа.
Привести примеры решений нескольких олимпиадных задач, соответствующих для моего возраста и уровня подготовки с помощью графов.
История появления графов
Т еория графов зародилась в ходе решения головоломок около 250 лет назад. Великий швейцарский, немецкий и российский математик и механик Леона́рд Э́йлер в 1736 году доказал первую теорему (Теорема - (др.- греч. θεώρημα «доказательство, вид; взгляд; представление, положение») — утверждение, выводимое в рамках рассматриваемой теории из множества аксиом посредством использования конечного множества правил вывода.)по теории графов. Связана она была с решением задачи (головоломки) о семи Кёнигсбергских мостах.
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам через реку Преголя, не проходя ни по одному из них дважды? Многие пытались решить эту задачу и теоретически, и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
Л еонард Эйлер смог решить эту занимательную задачку. Он доказал, что задача не имеет решения. Для решения он каждую часть суши обозначил ТОЧКОЙ, а каждый мост – ЛИНИЕЙ. Получилась упрощенная схема города – ГРАФ.
До конца XIX века графы применялись лишь для решения занимательных задач, не привлекая математиков.
На рубеже XIX-XX веков интерес к теории графов увеличился, потому что возросло число работ в области комбинаторики (Комбинаторика - раздел математики, изучающий все возможные перестановки элементов, цифр, каких-либо данных и т. п.).
Как отдельная дисциплина, теория графов впервые была представлена в работе венгерского математика Денеша Кёнига в 1936 году. Он назвал графом схемы, состоящие из множества точек и связывающих эти точки отрезки прямых или кривых.
В современном мире графы очень широко применяются в различных науках, не только в математике, но и физике, генеалогии, биологии, истории, статистике, комбинаторике, информатике и др.
Использование теории графов специалистами из разных наук привело к разной терминологии и различному обозначению. В своей работе я выбрала наиболее часто употребляемые понятия и обозначения.
Основные понятия теории графов.
Граф — абстрактный математический объект, представляющий собой множество вершин графа (ТОЧКИ) и набор рёбер (ЛИНИИ), то есть соединений между парами вершин. (Например, за множество вершин можно взять множество автовокзалов Пермского края, которые обслуживает компания Пермский Автовокзал, а за множество рёбер взять регулярные рейсы этой компании между городами края.)
Определение графа по Л. Березиной: Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек.
Математическое определение графа – упорядоченная пара G=(v,w), где v – некоторое конечное множество элементов {а, в, с,…,v}, а w – некоторый набор пар элементов из v.
Элементы v – это вершины или узлы графа. Элементы w – ребра графа. Вершины обозначаются на рисунке точками, кружочками, маленькими квадратиками.
Пример графа: МОЙ ДНЕВНОЙ ПУТЬ
V={Д, С, Ш, М, Т}
Число вершин графа G называется его порядком. (Значит, порядок нашего графа равен 5).
Число ребёр графа G его размером. (Размер нашего графа 8).
Вершины Д и С называются концевыми вершинами или просто концами ребра (ДС). Ребро соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.( В нашем случае соседними вершинами будут Д и С, С и Ш, Ш и М, Д и Ш, Д и М, Ш и Т, Д и Т, М и Т.)
Два ребра называются смежными, если они имеют общий конец (общую вершину). (В нашем примере смежные ребра ДС и ДТ, ДС и СШ, ДС и ДШ, ДС и ДМ, ДШ и ШМ, ДШ и ШТ, СШ и ШМ, ТШ и ШМ, СШ и ДШ, СШ и ШТ, ДШ и ДМ, ДШ и ДТ, ДМ и ДТ, ДМ и МШ, ДМ и МТ, ДТ и ШТ, ДТ и МТ, ШМ и МТ, ШТ и МТ).
Две вершины графа называются связными, если существует путь, связывающий эти вершины. Граф называется связным, если любая из его вершин связна. (Наш граф связный).
Степенью вершины называется число ребер графа, которому принадлежит эта вершина. Вершина графа степени 0, называется изолированной, а степени 1 – висячей. (В моём примере найдём степени вершин. Степень Д = 4, степень С = 2, степень Ш = 4, степень М = 3, степень Т = 3. Сумма всех степеней – 16)
Вершина называется нечётной, если её степень число нечётное, чётной - число чётное. (Рассмотрим наш пример. Вершины Д, Ш и С – чётные. Вершины М и Т – нечётные.)
Эйлеровым путем в графе называется путь, содержащий все ребра графа. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Граф, содержащий Эйлеров цикл, называется Эйлеровым.
Эйлеровым графом называется связный граф, у которого все вершины чётные.
Для решения подобных задач, нужно запомнить несколько правил.
Ч исло нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Если ровно две вершины графа нечётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом нужно начинать с одной из нечётных вершин и завершить его в другой нечётной вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Решение задач с помощью графов
Н а основании этих правил нетрудно решать задачки на построение уникурсальной линии – это замкнутая линия, которую можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз.
Ч тобы решить задачи такого вида, нужно всего лишь найти количество нечётных вершин данных графов. Если нечётных вершин будет более двух, то задача не имеет решения.
Виды графов и решение задач
Г рафы – деревья – это связные графы, не имеющие циклов. Деревьями являются графы всевозможных классификаций, сортировок.
Задача из олимпиады, которую я решила с помощью графа-дерева:
Получилось 18 вариантов:
Д вудольные графы. Граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое его ребро имело один конец красный, а другой синий.
С помощью двудольных графов я решу такую логическую задачу:
Три клоуна Епифан, Сидор и Гриша вышли на арену цирка в красной, синей и зелёной рубашках, в красных, синих и зелёных брюках, а также в красных, синих и зелёных туфлях. Интересно, что у каждого клоуна рубашка, брюки и туфли разного цвета. Известно, что Епифан был в зелёной рубашке, Сидор - в красных брюках.
Как был одет Гриша?
Р ешение: построим множество рубашек Р, множество брюк Б, множество туфлей Т, множество клоунов К. Если точкам из Р, Б, Т, будет соответствовать вершина из К, то будем соединять их сплошной линией, если не соответствует, то пунктирной. Решение этой задачи сведется к нахождению 9-ти сплошных отрезков. Если какая-то точка оказывается соединенной с двумя точками из других множеств пунктирными линиями, то с третьей точкой её необходимо соединить сплошной линией.
Ответ: Клоун Гриша одет в красную рубашку, зелёные брюки и синие туфли.
Заключение
В заключение моей работы хочу сказать, что считаю задачи и цели достигнутыми.
Я изучила некоторую научную литературу по теме. Постаралась разобраться в теории графов. Научилась ещё одним способом решать задачки – головоломки.
Работа над этой темой очень увлекла меня. Есть большой простор для дальнейшей работы.
Список литературы
Березина Л. «Графы и их применение», М.: Просвещение, 1979 г.
Генкин С.А., Интенберг И.В., Фомин Д.В. «Ленинградские математические кружки», Киров: АСА, 1994 г.
Ф. Папи, Ж. Папи «Дети и графы», М.: Педагогика, 1974