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

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

      им. Н.Г. ЧЕРНЫШЕВСКОГО 

    Кафедра компьютерной алгебры

    и теории чисел

 
 
 
 

Реферат на тему: 
 

ГРАФЫ. АЛГОРИТМ ОБХОДА ГРАФА В ГЛУБИНУ 

Выполнила: студентка 1-го курса механико-математического факультета, группа №111,специальность «Прикладная математика и информатика»            ****** Валерия

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

******** М.В. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Саратов ,2010

 

    СОДЕРЖАНИЕ

1. Введение                 
2. Из истории теории графов
3. Основные понятия теории графов
4. Способы представления графов в компьютере
5. Алгоритм обхода графа в глубину
6. Заключение
7. Список литературы

Введение

       В последнее время исследования в  областях, традиционно относящихся  к дискретной математике, занимают все более заметное место. Наряду с такими классическими разделами математики, как математический анализ, дифференциальные уравнения, в учебных планах специальности "Прикладная математика и информатика" и многих других специальностей появились разделы по математической логике, алгебре, комбинаторике и теории графов. Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       Из  истории теории графов.

       Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Хотя, теория графов многократно переоткрывалась разными  авторами при решении различных  прикладных задач.

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

 

       

       рис. 1 

       

2. Задача  о трех домах и  трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году.

       

       рис. 2 

       

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

         
 
 
 
 
 

       Рис. 3

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

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

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

         
 

         

Рис. 4 
 

       Пусть U, V – вершины, а E – ребро, соединяющее их. В этом случае вершины и ребро называются инцидентными. Степень вершины – это число ребер, инцидентных ей. Ребра, инцидентные одной вершины, а также вершины, соединенные одним ребром, называются смежными.

       Ориентированным называется граф, в котором - множество упорядоченных пар вершин вида (x,y), где x называется началом, а y – концом дуги. Дугу (x, y) часто записывают как . Граф, все ребра которого ориентированные, называется орграфом, а его ребра – дугами.

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

       На  рисунке 5 и 6 представлены примеры ориентированного и неориентированного графов соответственно.  

        Рис. 5 
 

        Рис. 6  

Подграфом называется граф G′(V′,E′), где и/или .

• Если V′ = V, то G′ называется остовным подграфом G.
• Если , то граф G′ называется собственным подграфом графа G.
• Подграф G′(V′,E′) называется правильным подграфом графа G(V,E), если G′ содержит все возможные рёбра G.

 

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

• Если , то путь замкнут, иначе открыт.
• Если все ребра различны, то путь называется цепью.
• Если все вершины (а значит, и ребра) различны, то путь называется простой цепью.
• Замкнутая цепь называется циклом.
• Замкнутая простая цепь называется  простым циклом.
• Граф без циклов называется ациклическим.
• Для орграфов цепь называется путем, а цикл – контуром.

Рис. 7 

Пример

В графе, диаграмма  которого приведена на рис.7:

1. v₁, v₃, v₁, v₄ – путь, но не цепь;
2. v₁, v₃, v₅, v₂, v₃, v₄ – цепь, но не простая цепь;
3. v₁, v₄, v₃, v₂, v₅ – простая цепь;
4. v₁, v₃, v₅, v₂, v₃, v₄, v₁ – цикл, но не простой цикл;
5. v₁, v₃, v₄, v₁ – простой цикл.

Способы представления графов в компьютере

 

       Конструирование структур данных для представления  в программе объектов математической модели – это основа искусства практического программирования. Выбор наилучшего представления определяется требованиями конкретной задачи.

       Известны  различные способы представления  графов в памяти компьютера, которые  различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) – объема памяти для каждого представления. Здесь p – число вершин, а q – число ребер.     

• матрица инциденций;
• матрица смежности;
• список смежности;
• массив ребер.

       Матрица инциденций

       Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа 

       

       а для орграфа

       

                                                                                                  

                

       Рис. 8  

       На  рисунке 1 представлен неориентированный граф и соответствующая матрица инциденций.

       Для матрицы инциденций  n(p,q) = V(pq).

        

       Матрица смежности

       Представление графа с помощью квадратной булевой  матрицы M, отражающей смежность вершин, называется матрицей смежности, где  

       

 

        

         Рис 9. 

       На  рисунке 2 представлен неориентированный  граф и соответствующая матрица  смежности.

       Для матрицы смежности n(p,q) = V(p²).

       Списки  смежности 

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

       N : record v : 1..p; n :↑ N end record,

       называется  списком смежности. В случае представления неориентированных графов списками смежности n(p,q) = V(p+2q), а в случае ориентированных графов n(p,q) = V(p+q).

       Массив  ребер

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

       E : array [1..q] of record b,e : 1..p end record,

       отражающего список пар смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = V(2q). 

Алгоритм  обхода графа в  глубину

 

       Мной  рассматривается алгоритм обхода графа  в глубину (называемый иногда стандартным  обходом).

       Данный  алгоритм осуществляется образом:

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

 

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