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

Министерство Образования Российской Федерации
Новосибирский Государственный Технический Университет
Кафедра Прикладной Математики

Курсовая работа

по практикуму на ЭВМ: «Структуры данных и алгоритмы»

Факультет:                ПМИ

Группа:                      ПМ-71

Студентка:                Калашникова О.А.

Преподаватель:         Еланцева И.Л.

Новосибирск 2008

1. Условия задачи.

Известно, что заданный граф  - не дерево. Проверить, можно ли удалить из него одну вершину (вместе  с инцидентными ей ребрами), чтобы в результате получилось дерево.

2. Анализ задачи.

Дано:  <G (V, E), I> – граф (по условию – не дерево)

           V – множество вершин

           E – множество ребер

           I– множество индексов вершин, I={1,2,3,…,n}

Результат:G` (V`, E`) – дерево

                  V`= V-1

                  E`= E-n, где n – количество смежных с E ребер

Понятия теории графов, применяемые в данной задачи.

Пусть V – непустое множество, V⁽²⁾ – множество всех его двухэлементных подмножеств. Пара (V,E), где E – произвольное подмножество множества V⁽²⁾, называется графом. Элементы множества V называются вершинами графа, а элементы множества E – ребрами. Итак, граф – это конечное множество V вершин и множество E ребер, EV⁽²⁾.

Дерево – связный граф, не содержащий циклов.

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

Теорема: для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u,v) – маршрут.

ВершинаV и ребро Е называются инцидентными, если V является одним из концов ребра Е, и не инцидентными в противном случае.

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

Пусть V - вершина графа G. Тогда операцию построения графа Н=G-Vназы­вают удалением вершины V. Построенный в результате этой операции граф Н со­держит все ребра множества Е_(G) кроме инцидентных вершине V, а V(н)=V(g)\{V}.

Пусть E - ребро графа G. Тогда операцию построения графа Н=G-Eназывают удалением ребра Е. Построенный в результате этой операции граф Н содержит все вершины графа G, а Е(H)=Е(G)\{E}.

Обход графа – это некоторое систематическое прохождение его вершин.

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

Вершина v_i достижима из вершины v_j, если существует путь из v_j в v_i.

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

Граф может быть однозначно представлен структурой смежности своих вершин. Структура смежности состоит из списков Adj [x] вершин графа, смежных с вершиной х. Списки Adj [x] составляются для каждой вершины графа.  

Метод решения:

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

i=0

повторять

  v[i]=0

   i=i+1

   пока i<n

Проверка графа на связность (идет с помощью компонент связанности графа, т.к. в теории графов – дерево это связный граф):

Повторять

Если, то

{

  Повторять

 

    Повторять

Повторять

Если то

 Пока

 

 Пока

  Если , то

   

     Повторять

    

     

     Пока

Пока

Пока не просмотрим все вершины графа

3. Структура основных входных и выходных данных.

Выходные данные

Внешнее представление

Граф представляется списком смежности вершин. Он организуется следующим образом:

n

v₁ deg v₁ v₁₁ v₁₂ v₁₃…v_{1,deg v1}

v₂ deg v₂ v₂₁ v₂₂ v₂₃…v_{2,deg v2}

……………………………….

v_n deg v_n v_n1 v_n2 v_n3…v_{n,deg vn}

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

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