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

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

САХАЛИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ 

Факультет математики, физики и информатики 

Кафедра информатики 
 
 
 
 
 
 
 

КУРСОВАЯ  РАБОТА ПО МАТЕМАТИКИ

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

 
 

Студентки 3 курса

специальности Прикладная математика и информатика 

Ахметовой Анастасии 

Научный руководитель:

Неешпапа  Тамара Архиповна   
 
 
 
 
 
 
 
 
 
 
 

г. Южно-Сахалинск

2011г 

     СОДЕРЖАНИЕ

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

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

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

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

Задача  о соединении городов…….……………………………………………17

      Задача  о назначении на должность………………………………….….20

Генеалогические графы………………………………………………………...23

Список  литературы……………………………………………………………..27 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ

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

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

     Ряд примеров приложений теории графов.

•  «Транспортные» задачи, в которых вершинами графа  являются пункты, а ребрами - дороги (автомобильные, железные и др.) и/или другие транспортные (например, авиационные) маршруты. Другой пример - сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами - возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.).

•  «Технологические задачи», в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги - потоки сырья, материалов и продукции между ними, заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков.

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

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

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

     ОСНОВНЫЕ  ПОНЯТИЯ ТЕОРИИ ГРАФОВ

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

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

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

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

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

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

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

      Последовательности вершин (рис. 1): 1–2–3–4–2–5 - а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 – цикл; 1–2–5–6–1 – контур. 
 
 
 
 
 
 
 

     Если  имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).

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

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

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

     Лемма. Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.

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

     ОПЕРАЦИИ  НАД ГРАФАМИ 

     Объединение графов.

       Пусть G₁(X₁,E₁) и G₂(X₂,E₂) – произвольные графы. Объединением G₁ÈG₂ графов G₁ и G₂ называется граф с множеством вершин X₁ÈX₂, и с множеством ребер (дуг) E₁ÈE_2.

     Рассмотрим  операцию на примере графов G₁(X₁,E₁) и G₂(X₂,E₂), приведенных на рис. 2. Множества вершин первого и второго графов соответственно равны X₁ = {x₁, x₂, x₃} и X₂ = {x₂, x₃, x₄}, а множество вершин результирующего графа определится как X = X₁ÈX₂ = {x₁, x₂, x₃, x₄}. Аналогично определяем множества дуг графа:

     E₁ = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₃, x₃)}.   E₂ = {(x₂, x₄), (x₃, x₂)_, (x₄, x₂)}.

     E = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₃, x₃), (x₂, x₄), (x₃, x₂)_, (x₄, x₂)}.

      Результирующий граф G(X,E)  =  G₁(X₁,E₁)ÈG₂(X₂,E₂) также приведен на рис. 2. 

       Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

       G₁ÈG₂  = G₂ÈG₁ – свойство коммутативности;

     G₁È(G₂ÈG₃) = (G₁ÈG₂)ÈG₃ – свойство ассоциативности.

     Для графов с одним и тем же множеством вершин справедлива следующая теорема.

     Теорема. Пусть G₁ и G₂ – два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин X, и пусть A₁ и A₂ – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G₁ÈG₂ является матрица A = A₁ÈA₂, образованная поэлементным логическим сложением матриц A₁ и A₂.

     Рассмотрим  выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G₁(X₁,E₁) и G₂(X₂,E₂)  – графы без параллельных ребер и  множества X₁ и X₂ вершин этих графов не совпадают. Пусть A₁ и A₂ – матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом.

     В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как X₁ÈX₂. Построим вспомогательные графы G’₁ и G’₂, множества вершин которых есть множество X₁ÈX₂, а множество ребер (дуг) определяется множествами E₁ для графа G^’₁ и E₂ для графа G^’₂. Очевидно, что матрицы A’₁ и A’₂ смежности вершин этих графов могут быть получены из матриц A₁ и A₂ путем добавления в них дополнительных столбцов и строк с нулевыми элементами.

     Применив  к графам G’₁ и G’₂ теорему, найдем матрицу смежности вершин графа G’₁ÈG’₂ как A’₁ÈA’₂. Очевидно, что полученной матрице смежности вершин  соответствует граф, множество вершин которого равно X₁ÈX₂, а множество ребер определяется, как E₁ÈE₂, что соответствует операции объединения графов.