ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

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

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

Информационные модели на графах.

Секция «Математика»

Графы и их применение.

Автор:

Яковлева

Юлия Владимировна,

ученица 8 «А» класса

Руководитель:

Марчик Светлана Артуровна,

Учитель математики

г. Саяногорск

2016г.

Содержание

Введение...................................................................................................................……...... 2

1.1. Цели……...............................................................................................................…….... 2

1.2.Задачи………………………………………………………………………………………….. 2

1.3. Актуальность и новизна..............................................................................................…….... 2

1.4. Гипотезы.......................................................................................................................…….... 2

2. История графов………………………………………………………………………....………. 2

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

4. Виды графов..…………...….…………………………………………………..……….............. 3

5. Маршрут. Путь. Контур..............………….......................................................................... 3

6. Информационные модели на графах……………................................................................. 4

7. Деревья………..................................................................................................................…….... 4

8. Использование графов при решении задач....................................................................…….... 5

9. Вывод................................................................................................................……..................... 5

10. Заключение.................................................................................................................................. 5

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

Приложения.....................................………….........................................................................… 35

Введение.

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

1.1.Цель.

Целью работы является ознакомление с понятием «граф», с его основными элементами.

Задачи.

· Научиться составлять графы по словесному описанию отношений между предметами и существами.

· Научиться читать графы: определять отношения между предметами и существами.

· Развить логическое и образное мышление, воображение.

· Проиллюстрировать применение математики на практике.

· Показать связь с другими областями знаний.

· Познакомиться с историческими сведениями.

· Исследовать роль графов в нашей жизни.

· Научиться решать задачи при помощи графов.

Актуальность и новизна.

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

Гипотезы.

· Если изучить теорию графов, то произойдёт повышение интереса к математике.

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

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

Эйлер (1707-1782, российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук) положил начало теории графов, как математической дисциплины в его знаменитом рассуждении о Кенигсбергских мостах.

Однако эта статья Эйлера, датированная 1736 годом, была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины 19 столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок поддавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса.

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

Граф – набор точек, соединенных между собой ребрами или дугами.

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

Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

Ребро – отрезок (или дуга), соединяющий вершины графа. Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, называются смежными (или соседними).

Петля – две дуги, соединяющие две смежные вершины графа.

Виды графов.

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

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

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

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

Маршрут. Путь. Контур.

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

Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).

Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

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

Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).

Информационные модели на графах.

Цикл – цепь, начальная и конечная вершины которой совпадают.

Сеть – граф с циклами.

На рисунке в виде графа представлена информационная модель сказки про Царевну-лягушку.

Вершины этого графа — персонажи и предметы из сказки, дуги — связи между ними.

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

Деревья.

Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчинённости, называются иерархическими системами (системами с иерархической структурой).

Например, иерархическую структуру имеет школа, потому что в ней установлены следующие отношения подчинённости: директор — заместители директора — учителя — ученики.

Иерархическую структуру имеют системы, элементы которых связаны отношением «входит в состав».

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

Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка — обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один ко многим». Вершины, не имеющие порождённых вершин, называются листьями.

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