Теория графов - Реферат

Государственное автономное профессионально-образовательное учреждение Реферат по предмету: "Дискретная математика" по теме: "Теория графов"Теория графов является одним из разделов дискретной математики, который исследует свойства конечных или счетных множеств с заданными отношениями между их элементами. Впервые понятие "граф" ввел в 1936 году венгерский математик Денеш Кeниг. Однако первая работа по теории графов была написана еще в 1736 году Леонардом Эйлером, в которой он решил "задачу о Кенигсбергских мостах". 1 представлена схема центральной части города Кенигсберг (ныне Калининград), которая включает два берега реки, два острова в ней и семь соединяющих их мостов. Современная теория графов дает исключительно удобный аппарат для моделирования структурных свойств различных систем и отношений между объектами разной природы.Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Например, граф для задачи 1 можно нарисовать по-другому: Такие одинаковые, но по-разному нарисованные графы, называются изоморфными. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной. С понятием степени вершины связана одна из основных теорем теории графов - теорема о честности числа нечетных вершин. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра - провода, их соединяющие.Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года "Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал: "Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Чтобы найти ответ, продолжим письмо Эйлера к Маринони: "Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них.Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа. Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек. Граф, в котором каждая пара вершин соединена ребром, называется полным. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k. Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа. Во всяком графе с n вершинами, где n больше или равно 2, всегда найдутся две или более вершины с одинаковыми степенями. Если граф имеет n вершин, то каждая из них может иметь степень 0, 1, 2, ..., (n-1). В самом деле, эта вершина должна быть соединена с (n-1) вершиной, в том числе и с А, но ведь А оказалась изолированной. Если в графе с n вершинами (n больше или равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.В данном пункте будут рассмотрены некоторые задачи, при решении которых используется теория графов. Учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок; Без сомнения, эту задачу можно решить путем обыкновенного перебора всех возможных вариантов, но решение будет наиболее простым, если вычертить граф в виде дерева. Рассмотрим еще одну задачу, решением которой также является граф.

Содержание

Введение

1. Теоретический материал

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

3. Основные определения теории графов

4. Основные теоремы теории графов

5. Задачи на применение теории графов

6. Применение теории графов в школьном курсе математики

7. Приложение теории графов в различных областях науки и техники

Вывод

Список использованной литературы