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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


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

Информация:

Тип работы: реферат. Добавлен: 15.05.2012. Сдан: 2011. Страниц: 14. Уникальность по antiplagiat.ru: < 30%

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


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

     Теория  графов – это раздел дискретной математики, имеющий многочисленные приложения в различных областях экономики, социологии, техники, программирования. Почему же графам оказывается столь  явное предпочтение? Стройная система  специальных терминов и обозначений  теории графов позволяют просто и  доступно описывать сложные и  тонкие вещи. Это связано еще с  тем, что графы в наглядной  графической интерпретации передают изучаемый объект. Например, в теории множеств мы с помощью орграфа  показывали бинарные отношения.
     Теория  графов многократно «открывалась»  разными авторами при решении  различных прикладных задач.
     Но  полноправно можно  сказать, что теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом  Эйлером (1707-1783: родился  в Швейцарии, жил  и работал в  России).
     Задача  о кенигсбергских мостах.
       

     Жителям Кенигсберга нравилось гулять по дорожкам, которые включали семь мостов, соединяющие два острова и  берега реки Преголя. Люди интересовались, могут ли они, начав путь с одного участка суши, обойти все мосты, посетив каждый лишь однажды, и вернуться в точку начала пути, не переплывая реку. Для решения задачи Эйлер построил граф: участки суши изобразил вершинами, а дорожки через мосты – как ребра. Сначала им была сформулирована и доказана теорема. И опираясь на эту теорему, Эйлер показал, что такого маршрута нельзя построить. Далее мы рассмотрим, как Эйлер решил эту задача.
     Кроме задачи о кенигсбергских мостах, классическими  задачами стали: задача о трех домах и трех колодцах; задача о четырех красках.
     Задача  о трех домах и  трех колодцах.  Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решения не существует) К Куратовским (1896 – 1979) в 1930 году.
H
H
H

     Задача  о четырех красках.  Разбиение плоскости на непересекающиеся области называется картой. Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которая базировалось на переборе вариантов с помощью компьютера.
     Суть  опубликованного решения состоит  в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных  контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они все сделали правильно. 

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

     Определение 1.  Графом G=G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множество E двухэлементных подмножеств множества V. Множество E называется множеством ребер. 

     Вершины vi и vj множества V называются соединенными ребром (vi, vj) или инцидентны к ребру (vi, vj), если (vi, vj)IE. Если (vi, vj) – ребро, тогда вершины vi и vj называются концами ребра (vi, vj). Ребро (vi, vj) называется также инцидентным к вершинам vi и vj. Две вершины называются смежными, если они инцидентны к одному ребру. Два ребра называются смежными, если они инцидентны к общей вершине.
     Число вершин графа G обозначим v, а число ребер - e:
      . 

     Определение 2.  Ориентированный граф или орграф G=G(V, E) – это такой граф, который состоит из множества V вершин и множества E упорядоченных пар элементов из V. Элемент множества E называется дугой. Если (vi, vj)IE, то vi называется начальной вершиной дуги (vi, vj), а vj называется конечной вершиной. 

     Геометрическое  представление графов следующее:
     1)  вершина графа – точка в  пространстве (на плоскости);
     2)  ребро неориентированного графа  – отрезок;
     3)  дуга ориентированного графа  – направленный отрезок. 

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

     Определение 3.  Граф G?(V?, E?) называется подграфом (или частью) графа G(V,E), если V? IV, E? IE. Если V?=V, то G? называется остовным подграфом G. 

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

     Определение  4.  Граф называется полным, если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через Kn.
     Определение 5.  Граф G=G(V, E) называется двудольным, если V можно представить как объединение непересекающихся множеств, скажем V=AEB, так что каждое ребро имеет вид (vi, vj), где viIA и vjIB. Двудольный граф называется полным двудольным графом Km, n, если A содержит m вершин, B содержит n вершин и для каждого viIA, vjIB имеем (vi, vj)IE.
     Пример.  Построить полный двудольный граф K2,4 и полный граф K4. 

v1
v2
v3
v4
v5
v6
x1
x2
x3
x4
Полный двудольный граф K2,4
A={v1, v2}
B={v3, v4, v5, v6}
Полный граф K4
 
 
 

2.  Связность графов. 

     Определение 6.  Пусть G=G(V, E) – граф с вершинами v0, v1, v2, …, vnIV и ребрами e1, e2, …, emIE. Маршрутом (путем) длины k из v0 в vk (или между v0 и vk) называется последовательность v0e1v1e2v2e3v3vk-1ekvk такая, что ei=(vi-1, vi).
     Таким образом, путь длины k имеет k ребер. По причине избыточности обозначений в этом определении для графа в общем случае путь будет обозначаться через v0v1v2vk.
     Если  все ребра различны, то путь называется цепью. Если все вершины различны (а значит, и ребра), то путь называется простой цепью. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим.
     Аналогично, как и для графа, для орграфа  вводятся понятия ориентированный  путь, ориентированный цикл.
     Пример  3.  Дан неориентированный граф.
v1
v2
v3
v4
v5
e1
e2
e3
e4
e6
e5
G(V, E) – граф
v1e1v2e2v3e3v1e1v2e5v5 или v1v2v3v1v2v5 – маршрут
v1v2v3v1v5 – цепь
v1v3v2v5 – простая цепь
v1v3v2v5v1 – простой цикл

     , 

     Определение 7.  Граф G=G(V, E) называется связным, если имеется цепь между любыми двумя его различными вершинами.
     Для заданного ориентированного графа  G можно построить неориентированный граф такой, что каждая ориентированная дуга G (исключая петли) станет неориентированным ребром графа . В таком случае граф называется соотнесенным графом орграфа G(V, E).
     Определение 8.  Орграф G(V, E) называется связным, если его соотнесенный граф является связным. Орграф называется сильно связным, если для любой пары вершин vi ,vjIV существует ориентированный путь из vi в vj. 
 

     3.  Изоморфизм графов. 

     Определение 9.  Функция f : G(V, E) ® G1(V1, E1) является изоморфизмом (обозначается G~G1), если f: V®V1 и f: E® E1 представляют собой взаимно однозначные соответствия. Если f:G®G1 – изоморфизм, то G и G1 называются изоморфными.
     Пример  4.  Дан неориентированный помеченный граф G1(V1; E1). Построить изоморфные ему графы. 

v3
v4
v6
v1
v2
v5
G1(V1; E1) - граф
 

     Решение.
u1
u2
u3
u4
u5
u6
x1
x2
x3
x4
x5
x6
G2(V2; E2) – граф
Изоморфизм f : G1®G2
   f (v1)=u1          f (v4)=u4       f (v1; v2)®(u1; u2)
   f (v2)=u2          f (v5)=u5             и т.д.
   f (v3)=u3          f (v6)=u6
G3(V3; E3) – граф
Изоморфизм g : G1®G3
   g (v1)=x1          g (v4)=x4       g (v1; v2)®(x1; x2)
   g (v2)=x2          g (v5)=x5           и т.д.
   g (v3)=x3          g (v6)=x6

     , 

     Теорема 1.  Изоморфизм графов есть отношение эквивалентности.
     Доказательство.  Действительно, изоморфизм обладает всеми  необходимыми свойствами отношения  эквивалентности:
     [Рефлексивность.]  G ~ G, где требуемая биекция есть тождественная функция;
     [Симметричность.]  Если G1 ~ G2 с биекцией h, то G2 ~ G1 с биекцией h- 1;
     [Транзитивность.]  Если G1 ~ G2 с биекцией h и G2 ~ G3 с биекцией g, то G1 ~ G3 с биекцией g o h.
     4.  Степень вершин. 

     Определение 10.  Степенью вершины v для неориентированного графа, обозначается d(v), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей. 

     Определение 11. Полустепенью исхода вершины v для орграфа называется количество дуг, для которых v является начальной вершиной, обозначается . Полустепенью захода вершины v называется количество дуг, для которых v является конечной вершиной, обозначается . Если , то вершина v называется истоком. Если , то вершина v называется стоком.
     Теорема 2. (Теорема Эйлера)  Сумма степеней вершин графа равна удвоенному количеству ребер:
      .
     Доказательство.  При подсчете суммы степеней вершин каждое ребро учитывается два  раза: для одного конца ребра и  для другого.
     Следствие 1.  Число вершин нечетной степени четно.
     Доказательство.  По теореме Эйлера сумма степеней всех вершин – четное число. Сумма  степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, следовательно, их четное число.
     Следствие 2.  Сумма полустепеней вершин орграфа равна удвоенному количеству дуг:
      .
     Доказательство.  Сумма полустепеней вершин орграфа равна сумме степеней вершин графа, полученного из орграфа забыванием ориентации дуг.
     Пример  5.  Определить степени вершин данного графа.
v1
v2
v3
v4
v5
e1
e2
e3
e4
e5
e5
G(V, E) – граф 

d(v1)=4          d(v4)=1
d(v2)=3          d(v5)=2
d(v3)=2 

вершина v4 - висячая

     ,
     Пример  6.  Определить полустепени исхода и захода данного орграфа.
v1
v2
v3
v4
v5
d -(v1)=1        d -(v3)=1         d -(v5)=0
d +(v1)=1        d +(v3)=2         d +(v5)=2 

d -(v2)=2        d -(v4)=2
d +(v2)=1        d +(v4)=0 

вершина v4 – исток
вершина v5 – сток
 
 
 

     5.  Представление графов в компьютере. 

     Известны  различные способы представления  графов в памяти компьютера, которые  различаются объемом занимаемой памяти и скорости выполнения операций над графами. Преставление выбирается, исходя из потребностей конкретной задачи. В подавляющем большинстве случаев  граф задается матрицей. Чаще всего  графы представляют либо матрицей смежности, либо матрицей инциденций.
     Определение 12.  Матрица смежности вершин орграфа G, содержащего n вершин-- это квадратная матрица A=[aij] n-го порядка, у которой строки и столбцы матрицы соответствуют вершинам орграфа. Элементы aij матрицы A равны числу дуг, направленных из i-й вершины в j-ю. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1.
     Матрицей  смежности вершин неориентированного графа G, содержащего n вершин, называют квадратную матрицу A=[aij] n-го порядка, у которой строки и столбцы матрицы соответствуют вершинам неориентированного графа. Элементы aij матрицы A равны числу ребер, направленных из i-й вершины в j-ю. В случае неориентированного графа G ему вместе с ребром (vi, vj) принадлежит и ребро (vj, vi), поэтому матрица смежности вершин A=[aij] будет симметрична относительно главной диагонали. 

     Определение 13.  Матрица смежности дуг орграфа -- это квадратная матрица B=[bij] m-го порядка, у которой строки и столбцы матрицы соответствуют дугам орграфа. Элементы bij матрицы B равны 1, если дуга ei непосредственно предшествует дуге ej и 0 в остальных случаях.
     Матрицей  смежности ребер  неориентированного графа является матрица B=[bij] m-го порядка, у которой строки и столбцы матрицы соответствуют ребрам графа. Элементы bij матрицы B равны 1, если ребра ei и ej имеют общую вершину, и 0 в остальных случаях. 

     Определение 14. Матрицей инциденций (инцидентности) неориентирован-ного помеченного графа с вершинами и ребрами называется матрица размерности , строки которой соответствуют вершинам, а столбцы – ребрам. Элементы матрицы инциденций неориентированного графа равны 1, если вершина инцидентна ребру , и 0 в противном случае.
     Матрицей  инциденций (инцидентности) орграфа с вершинами и дугами называется матрица размерности n?m, строки которой соответствуют вершинам, а столбцы --дугам орграфа. Элементы cij равны 1, если дуга ej исходит из i-й вершины; -1, если дуга ej заходит в i-ю вершину; 0, если дуга не инцидентна i-й вершине:
     
     Если  каждому ребру графа приписано  некоторое положительное число, то такое число называется весом, а сам граф называется взвешенным графом. Простой взвешенный граф (сеть) может быть представлен также  своей матрицей весов , где wij – вес ребра, соединяющего вершины vi и vj. Весы несуществующих ребер (дуг) полагают равными нулю или бесконечности в зависимости от приложений.
     Пример  7.  1)  Для заданного неориентированного графа построить матрицы смежностей и матрицы инциденций.
v1
v2
v3
v4
e1
e2
e3
e4
e5

     2)  Для заданного ориентированного  графа построить матрицы смежностей  и матрицы инциденций.
v1
v2
v3
v4
e1
e2
e3
e4
e5
 

     Решение.  1)  Строим матрицу смежности вершин, которая будет размерности 4?4. Строим матрицу смежности ребер, которая будет размерности 5?5. 

      ,       .
     Строим  матрицу инциденций, которая будет размерности 4?5. 

      . 

     2)  Строим матрицу смежности вершин, которая будет размерности 4?4. Строим матрицу смежности ребер, которая будет размерности 5?5.
      ,        

     Строим  матрицу инциденций, которая будет размерности 4?5.
      . 
 
 
 

     6.  Выявление маршрутов  с заданным количеством  ребер (дуг). 

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

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

     Пример  8.  Для неориентированного графа, изображенного на рисунке, найти все маршруты длины 2.
v2
v3
v1
v4
e1
e2
e3
e6
e5
e4
 

     Решение.  Составим матрицу смежности вершин P и возведем ее в квадрат. Результат возведения:
      .
и т.д.................


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


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


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


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