Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [ 17 ] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

ляется вроде бы достаточно хорошо с задачей отсеивания неизоморф ных сетей.

Вычисляется A{Gi) для i=l, 2. Затем переставляются строки и столбцы A{Gi) и A-{G2) так, чтобы элементы иа главной диагонали оказались в нисходящем порядке. Если d и Gg изоморфны и все диаг нальные элементы различны, то при этой перестановке должны по. читься идентичные матрицы. Если нет, то данные две сети не мо •

Переугорпдачешш А (g,) Переупорядоченная (G ,

A(G,)

2 3 4

2 3 4

2 3 4

1 1

0 1

1 0 1

1 1 2

0 3 0 ц,

0 1

2 1 1

2 0 2 x

1 0

1 0 1

1 3 0

0 3 0 0

с 1

0 1 0

1 0 2

2 0 2 2

1 0

0 1 0

1 2 0

2 0 2 2

a(G2)

a(g,)

a(g,)

2 3 4

2 3 4

2 3 4

1 1

3 00

3 1

0 2

3 0 0

12 <-

1 2

1 1

0-2 2

18 <iu

0 1

2 0

0 2 2

2 1

0 2 2

A(G2)

Рис. 2.2.19.

быть изоморфными. Если матрицы идентичны, можно продолжить проверку с A{Gi), A{Gi), .... A{Gi) для i=l, 2. Значение k определяется имеющимся бюджетом машинных ресурсов. Если все из проверенных матриц совпадают, то весьма правдоподобно, но не обязательно истинно, что Gi и Ga изоморфны.В дальнейшем эту процедуру мы будем называть методом СПС (сравнение порядков смежности).

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

На рис. 2.2.19 работа метода СПС проиллюстрирована на примере двух сетей с рис. 2.2.18. Факт неизоморфности Gi и Gg становится ясным достаточно рано на основании следующего: 1) переупорядоченные матрицы A%Gi) не совпадают по элементам вне главной диагонали и 2) не равны диагональные элементы A{Gi). Как для A%Gi), так и для AGz) переупорядочение выполнено заменой строк и столбцов 2 и 3. Обратите внимание на перемещение элементов, стоящих на пересечении пар строк - столбцов.



Упражнения 2.2

2.2.1. Изобразите все неизоморфные сети с пятью вершинами. Их 34.

2.2.2. Изобразите все неизоморфные деревья с восемью вершинами. Их 23. Ю2.3. Докажите теорему 2.2.1 методом математической индукции.

хЗЛ. Докажите следствие 2.2.1.

ТгЙб. Алгоритм СВЯЗЫВАНИЕ (правильность). Проверьте правильность алгорит-ча СВЯЗЫВАНИЕ.

-!й2.2.6. Ллгоритж СВЯЗЫВАНИЕ (реализация, проверка). Реализуйте и проверьте дг1Г0ритм СВЯЗЫВАНИЕ. Один интересный способ реализовать операцию слияния Использует матрицу смежности и операцию двоичного ИЛИ (см. приложение Б). Для слияния вершины vj с вершиной и,- просто добавьте строку R (/), соответствующую Vj-, к строке, соответствующей и,-, используя форму двоичного сложения ИЛИ. Затем добавьте столбец C(j) к столбцу C(i) и занесите нуль в диагональный элемент feTpOKH R(i). После удаления R(j) и С(/) результирующая матрица будет представлять сеть после слияния.

;i.2.7. Алгоритм СВЯЗЫВАНИЕ (анализ). Используя реализацию из упр. 2.2.6, ,г!5ризведите анализ сложности алгоритма СВЯЗЫВАНИЕ.

5.3.8. Алгоритм ПРОВЕРКА ДЕРЕВА (разработка). Воспользуйтесь алгоритмом ..ЕЯЗЫВАНИЕ при разработке алгоритма ПРОВЕРКА ДЕРЕВА, определяющего, v.Bi4eTCH ли данная сеть деревом.

%2.. Разделяюи{ие вершины и мосты (доказательство). Докажите следующие две

1;оремы (критерии).

Теорема. Вершина v связной сети G является разделяющей вершиной тогда и только тогда, когда существуют две вершины и v, где v, vh v - различные вершины, такие что v принадлежит каждому пути из с/ в fj-Теорема 2.2.2. Ребро е связной сети G является мостом тогда и только тогда, когда существуют две вершины и Ua, такие, что е принадлежит каждому пути из

Vl в Dg.

L2.2.10. Представление преобразования (разработка, реализация). Разработайте и реализуйте алгоритм, который преобразует матрицу смежности в матрицу инцидентности и наоборот.

*2.2.11. Двудольные сети (доказательство). Сеть G=(V, Е) называется двудольной, если V можно разбить на два непересекающихся подмножества li и Vz, такие, что каждое ребро в Е соединяет вершину в Vi с вершиной в Уа. Докажите, что сеть двудольная тогда и только тогда, когда каждый цикл содержит четное число ребер.

2.2.12. Полные двудольные сети. Двудольная сеть (см. определение в упр. 2,2.11) называется полной, если для любых иУг и vV, (и, v)V. Пу стъ /С/я, п обозначает единственную полную двудольную сеть, где Vi=7n и l2l=«-Выведите формулу для числа ребер в Km, п-

2.2.13. Изобразите две неизоморфные сети с шестью вершинами, имеющие одинаковые последовательности степеней.

*2.2.14. Как можно было бы использовать представление в форме характеристического вектора, введенное для множеств (см. приложение Б), чтобы сэкономить память при представлении сетей? Камми недостатками обладают ваши предложения? 2.2.15. Полные сети. Сеть с М вершинами называется полной и обозначается через /Сл1, если каждые две вершины смежные. Такие сети использовались при моделировании задачи о коммивояжере. Покажите двумя различными способами, что число ребер в Км задается формулой



2.2.16. Перерисуйте и Кз.з (см. упр. 2.2.12 и 2.2.15) так, чтобы в каждой сети имелось только одно пересечение ребер, т. е. только одно пересечение в точке, не являющейся вершиной сети.

*L2.2.17. Алгоритм РАЗДВЕР (полная разработка). Полностью постройте алгоритм, который находит все разделяющие вершины в данной сети.

**2.2.18. Реализуемая последовательность степеней (доказательство). Невозрастаю-щая последовательность положительных чисел называется реализуемой, если существует сеть, для которой эта последовательность является последовательностью степеней. Докажите, что последовательностъ d, d, . . . , dj (где dd. . .уО) реализуема тогда и только тогда, когда последовательность d-X, dg-\, ... ,da,+i, da,+ 2, , djii реализуема.

**2.2.19. Алгоритм РЕАЛИЗУЕМОСТЬ (разработка). Разработайте алгоритм, основывающийся на теореме из упр. 2.2.18, который определяет, является ли конечная последовательность полояштельных целых чисел реализуемой.

*2.2.20. Какие из сетей на рис. 2.2.17 изоморфны?

**L2.2.21. Метод СПС (разработка, реализация). Разработайте и реализуйте подпрограмму для метода СПС. Что вы сделаете, когда два или более из диагональных элементов будут иметь одинаковые значения?

**L2.2.22. Эвристика изоморфизма (разработка, реализация, проверка). Разрабо-тате, реализуйте; и проверьте эвристический алгоритм для обнаружения изоморфизма. Ограничьтесь сетями не более чем с 12 вершинами.

*2.2.23. Инварианты. Попытайтесь составить список из 10 или больше сетевых инвариантов.

*2.2.24. Докажите теорему 2.2.5.

**2.2.25. Докажите следующую теорему. Если А - матрица смежности невзвешен-ной сети G и V{G)= {vi, v2, . . . , то {i, /)-й элемент матрицы А", где п>1,- это число различных маршрутов из и,- в v,- длины п в О (считайте, что у каждого ребра длина равна единице).

2.2.26. Докажите теорему 2.2.6.

2.3. Некоторые структуры данных

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

Рассмотрим преимущества и недостатки использования массивов. Среди преимуществ отметим следующие:

1. Массивы помогают объединять множества данных в осмысленные группы.

2. Имена массивов с индексами минимизируют потребность в слежении за многими элементами данных с различными именами.

3. Использование индексов обеспечивает непосредственный и автоматический доступ к любому элементу в массиве.

4. Индексация позволяет также производить с помощью циклов DO и FOR автоматическую, быструю и эффективную обработку всех данных или выделенных подмножеств данных, хранимых



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [ 17 ] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.001