litceysel.ru
добавить свой файл
1 2 3
ЛАБОРАТОРНАЯ РАБОТА



«ПРЕДСТАВЛЕНИЕ ГРАФОВ. АЛГОРИТМЫ НА ГРАФАХ»


    1. Цель работы


Изучить способы представления графов с помощью матриц: матрица смежностей, матрица инцидентности, матрица достижимости, другие матричные представления

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


    1. Порядок выполнения работы




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

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

      3. Написать, отладить программу и получить контрольный пример в соответствии со своим вариантом.

      4. В отчет по лабораторной работе включается:

  • Титульный лист

  • Постановка задачи

  • математическая постановка задачи.

  • Описание программы

  • Структура входных данных

  • Структура выходных данных

  • Алгоритм программы, включая алгоритм решения задачи
  • Выводы


  • Приложение:

  • исходный текст программы;

  • контрольные примеры.




    1. Задания

Во всех задачах под термином "граф" понимается: (а) - "неориентированный граф"; (б) - "ориентированный граф". Необходимо выполнить задание (а) и (б), если процедуры разные для ориентированного и неориентированного графа.

Задание 1. Изучение способов представления графов с помощью матриц

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

  2. Напишите функцию, осуществляющую переход от представления графа с помощью матрицы инцидентности к представлению графа с помощью матрицы смежностей.
    Указание [Липский, 1988, с.114]. Для произвольного неориентированного графа матрица смежностей B выражается через матрицу инцидентности A следующим образом: B=AxAT-diag [d1,...,dn], где AT - транспонированная матрица A, di- степень i-ой вершины, diag [d1,...,dn] - матрица размерности nxn с элементами d1,...,dn, расположенными на главной диагонали.

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

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

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

Указание. Необходимо найти сумму чисел в строке матрицы смежности, соответствующей данной вершине.

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

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


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

  4. Проверьте, имеет ли граф, заданный матрицей смежности, петли.

Указание. Проверьте наличие на главной диагонали матрицы смежности элементов, не равных 0.

  1. Посчитайте количество кратных ребер в графе, заданном матрицей смежности.

  2. В графе, заданном матрицей смежности, определите количество петель.

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

Указание. Найдите максимальный элемент в матрице смежности.

  1. Посчитайте число вершин в графе (граф задан матрицей смежности), от которых отходит более m ребер.

Указание. Найдите количество сумм строк в матрице смежности, больших m.

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

Указание. Суммы строк в матрице смежности равны 0.

  1. Определите, каково максимальное (минимальное) количество ребер, выходящих от одной вершины в графе, заданном матрицей смежности?

Указание. Найдите max сумм строк в матрице смежности.

  1. Напишите программу, определяющую среднее количество ребер в графе, заданном матрицей смежности?

Указание. Среднее арифметическое элементов матрицы смежности.
  1. Установите, является ли граф, заданный матрицей смежности, регулярным (в регулярном графе степень всех вершин одинакова)?


Указание. Суммы в строках матрицы смежности одинаковы.

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

Указание. Все элементы матрицы смежности равны 1.

  1. Постройте матрицу смежности графа с выброшенной k-ой вершиной. Установите, будет ли граф связным, если удалить заданную вершину?

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

  3. Посчитайте количество ребер в графе, заданном матрицей инцидентности.

  4. Проверьте, есть ли в графе, заданном матрицей инцидентности, кратные ребра.

  5. Проверьте, имеет ли граф, заданный матрицей инцидентности, петли.

  6. Посчитайте количество кратных ребер в графе, заданном матрицей инцидентности.

  7. В графе, заданном матрицей инцидентности, определите количество петель.

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

  9. Посчитайте число вершин в графе (граф задан матрицей инцидентности), от которых отходит более m ребер.

  10. Определите, существуют ли в графе, заданном матрицей инцидентности, изолированные вершины?

  11. Определите, каково максимальное (минимальное) количество ребер, отходящих от одной вершины в графе, заданном матрицей инцидентности?

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

  13. Определите, каково среднее количество ребер в графе, заданном матрицей инцидентности?

  14. Определите, является ли граф, заданный матрицей инцидентности, регулярным (в регулярном графе степень всех вершин одинакова)?
  15. Определите, является ли граф, заданный матрицей инцидентности, полным (в полном графе любые две вершины смежны)?


  16. Определите, является ли граф, заданный матрицей инцидентности, звездой (звезда - граф, у которого одна вершина соединена со всеми, а у остальных степень равна 1)?

  17. Определите, является ли граф, заданный матрицей инцидентности, кольцом (кольцо - связный граф, степень каждой вершины которого равна 2)?

Задание 2. Реализация алгоритмов на графах, представленных с помощью матриц

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

  2. Граф задан матрицей смежности (матрицей достижимости). Определите, минимальную длину пути между двумя заданными вершинами?

  3. Граф задан матрицей смежности (матрицей достижимости). Определите, количество путей в графе путей от вершины A до вершины B длины не более m?

  4. Граф задан матрицей смежности (матрицей достижимости). Определите, является ли граф связным?

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

  1. Граф задан матрицей смежности (матрицей достижимости). Определите, является ли заданный граф деревом.

Указание. Граф должен быть связным, а количество его ребер на единицу больше количества вершин.

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

  2. Граф задан матрицей смежности (матрицей достижимости). Определите количество путей длины 3 из i-ой вершины в j-ю вершину данного графа.

  3. Граф задан матрицей смежности (матрицей достижимости). Найдите все вершины, в которые существует путь длины не более 3 из заданной вершины.
  4. Граф задан матрицей смежности (матрицей достижимости). Найдите все вершины, в которые существует путь из заданной вершины.


  5. Граф задан матрицей смежности. Найдите все вершины, из которых существует путь в заданную вершину.

  6. [Касьянов,Сабельфельд,1986] Граф задан матрицей смежности (матрицей достижимости). Найдите все вершины заданного графа, недостижимые от его заданной вершины.

  7. [Лэнгсам, Огенстейн, Тененбаум, 1989, с.389] Напишите программу, которая по заданной матрице смежностей и двум вершинам графа вычисляет: (а) количество путей заданной длины между данными двумя вершинами; (б) общее количество путей между заданными двумя вершинами; (в) длину кратчайшего пути между заданными двумя вершинами.

  8. [Касьянов,Сабельфельд,1986] Определите, верно ли, что для любой пары вершин заданного ориентированного графа одна из этих вершин достижима от другой.

  9. Найдите все вершины ориентированного графа, к которым существует путь заданной длины от выделенной его вершины.

  10. [Касьянов, Сабельфельд, 1986] Найдите все вершины ориентированного графа, от которых существует путь заданной длины к выделенной вершине.

  11. [Касьянов, Сабельфельд, 1986] Источником ориентированного графа назовем вершину, из которой достижимы все другие вершины; стоком - вершину, достижимую из всех других вершин. Найдите все источники и стоки данного ориентированного графа с помощью представления графа в виде матрицы смежностей.

  12. Источником ориентированного графа назовем вершину, из которой достижимы все другие вершины, а стоком - вершину, достижимую из всех других вершин. Найдите все источники и стоки данного ориентированного графа с помощью представления графа в виде матрицы достижимости.
  13. Расстояние d(vi,vj) между вершинами vi и vj графа G равно наименьшему из целых чисел n, для которых (i,j)-й элемент aij(n) матрицы An (A - матрица смежностей графа G) отличен от нуля, т.е. d(vi,vj)=min {n: aij(n)-0}. Если граф связный, то "vi,vj приведенный выше минимум достигается при конечных n. Найдите расстояние между заданными двумя вершинами графа.


  14. Расстоянием между вершинами v и w называется длина кратчайшей цепи из v в w. Центром графа G называется такая вершина v, что максимальное расстояние между v и любой другой вершиной является наименьшим из всех возможных. Это расстояние называется радиусом графа. Найдите центр и радиус заданного графа.

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

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

  17. Обозначим R(vi) - множество вершин, достижимых из вершины vi, а Q(vj) - множество вершин, из которых можно достигнуть vj, тогда R(vi)Q(vj) - это множество таких вершин, каждая из которых принадлежит по крайней мере одному пути, идущему от vi к vj. Эти вершины называются существенными (неотъемлемыми) относительно вершин vi и vj, а все остальные вершины называются несущественными (избыточными). Для данных двух вершин графа найдите существенные вершины.

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

  19. [Касьянов, Сабельфельд, 1986] Найдите минимальное подмножество вершин заданного ориентированного графа, от каждой вершины которого достижимы все остальные его вершины.




    1. Теоретические сведения

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

Пусть G - помеченный граф порядка n, V={1,2,...,n}. Матрица смежностей неориентированного графа - это матрица B=[Bij] размерности |V|x|V|, где

Матрица смежностей ориентированного графа - это матрица B=[Bij] размерности |V|x|V|, где



Легко видеть, что матрица смежностей неориентированного графа всегда симметрична, поэтому для ее представления достаточно хранить только ее верхний треугольник. Приведем пример:

Неориентированный граф

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






Конечно, для ориентированного графа это не так. Приведем пример:

Ориентированный граф

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





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

Основной недостаток использования матрицы смежностей заключается в том, что она занимает память объема |V|2 даже тогда, когда граф содержит только O(|V|) ребер. Уже начальное заполнение матрицы смежностей посредством "естественной" процедуры требует времени O(|V|2), что сводит на нет алгоритмы сложности O(|V|) при работе с графами, содержащими лишь O(|V|) ребер. Впрочем, на практике это неудобство можно иногда уменьшить, если хранить целую строку (столбец) матрицы в одном машинном слове (это возможно для малых |V|). В большинстве алгоритмов на графах каждое ребро графа G необходимо рассматривать по крайней мере один раз. Поэтому в случае представления графа матрицей смежностей для большинства алгоритмов требуется время вычисления, по крайней мере, пропорциональное |V|2.



следующая страница >>