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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: Контрольная. Предмет: Математика. Добавлен: 08.12.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


Содержание

Введение

1. Графы, орграфы, деревья

2. Операции над графами

3. Хранение графов в ЭВМ

4. Задача о максимальном потоке

5. Построение максимального потока. Примеры разбираемых задач

Литература

Введение

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

Позже Д.К. Максвелл и Г.Р. Кирхгоф на основе исследования электрических цепей сформулировали некоторые принципы сетевого анализа. Были разработаны методы расчета наибольшей пропускной способности телефонных линий. В 40-х годах в результате развития теории исследования операций был разработан ряд математических методов, необходимых для анализа больших систем. В 50-60-х годах проводились работы по построению новых сетевых моделей и разработке алгоритмов их решения на основе элементов теории графов.

Графы, орграфы, деревья

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

Основы теории графов разработал Л. Эйлер, решавший задачу о разработке замкнутого маршрута движения по мостам в г. Кенигсберге. При решении задачи он обозначил каждую часть суши точкой, а каждый мост - линией, их соединяющей. В результате был получен граф (рис. 1).

Эйлер доказал, что такая задача решения не имеет.

Эйлер Леонард (1707-1783) швейцарский математик, механик, физик, астроном. Автор более 800 работ по различным разделам математики и другим наукам.

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

Пусть на плоскости задано некоторое множество вершин X и множество U соединяющих их дуг. Графом называют бинарное отношение множества X и множеств U: G = = (X; U), или, иначе ?: X > К Здесь ? - отображение инциденций.

Граф называется ориентированным, если указано направление дуг и неориентированным, если такое направление не указано. Примером неориентированного графа является карта дорог.

Граф называется петлей, если его начало и конец совпадают.

Две вершины называются смежными, если существует соединяющая их дуга.

Ребро uj называется инцидентным вершине хj, если оно выходит или входит в вершину.

Степенью (валентностью) вершины называется число инцидентных ей ребер. Кратностью пары вершин называется число соединяющих их ребер или дуг.

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

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

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

Контур - это конечный путь, у которого начальная и конечная вершины совпадают. Контур называется элементарным, если все его вершины различны (кроме начальной и конечной). Контур единичной дуги называется петлей.

В неориентированном графе понятие дуга, путь, контур заменяются соответственно на ребро, цепь, цикл.

Ребро - отрезок, соединяющий две вершины, цепь - последовательность ребер.

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

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

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

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

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

На рисунке 3 ребро к - мост, а на рисунке 4 вершина 1 - точка сочленения.

Неразделимым называется связный граф, не имеющий точек сочленения.

Блоком графа называют максимальный неразделимый подграф.

На рисунке 5 приведен граф G и его блоки А, В, С и D.

Дерево это конечный, связный, не ориентированный граф, не имеющий циклов.

Характеристическое свойство деревьев состоит в том, что любые две вершины дерева соединены единственной цепью.

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

Кирхгоф Густав (1824-1887) немецкий физик, механик, математик.

Развитие теории графов (деревьев) связано с именем немецкого химика Кели, который успешно применил ее для решения задач органической химии (для изучения изомеров углеводородов с заданным числом атомов).

Совокупность деревьев называется лесом.

Если все вершины графа принадлежат дереву, то он называется покрывающим. Пусть дано множество вершин графа. Одну из вершин, например х1, примем за начальную, которую назовем корнем дерева. Из этой вершины проводим ребра к остальным вершинам х2, х3 и т.д.

Простейшее дерево состоит из двух вершин, соединенных ребром.

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

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

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

Пусть имеется х1, х2,, хn вершин и u1, u2, um дуг, их содержащих. Матрицей смежности S порядка п называется матрица, состоящая из чисел S., равных сумме чисел ориентированных ребер, идущих из х в х. (или чисел неориентированных ребер, соединяющих эти вершины). Если дуга отсутствует, то Sr = 0.

Матрица смежности для ориентированного и неориентированного графа, вообще говоря, имеет разный вид. Запишем матрицу смежности 5, для ориентированного графа, изображенного на рисунке 7:

Матрицей инциденции Т размера m x n называется матрица, состоящая из чисел:

Запишем матрицу инциденции для графа, изображенного на рисунке 7:

Операции над графами

Объединением двух, или более графов G1, U G2 U … U Gn называется граф, у которого множество вершин и множество дуг объединены (рис. 8).

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

Будем говорить, что вершина иj конусирует граф G, если она смежная со всеми вершинами графа.

Произведением двух графов называется граф

G1 * G2 = {(Xj1; Xj2) Є G1 * G2}.

Вершина представляет собой бинарное отношение, т.е. вершин у нас будет 6.

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

Через два рукава перекинуты семь мостов: а, Ь, с, d, e, ?, g. Можно ли спланировать прогулку таким образом, чтобы по каждому мосту пройти только один раз и вернуться в начальное положение? Поставим в соответствие каждому мосту ребро графа, а суше вершину (рис. 11).

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


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.