Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Порядок выполнения задания

  • 4.5.1. Разработать алгоритм и программу перехода от способа Л представления графа к способу В. Номер варианта задания определяет значения Ап В (табл. 4.1). Оценить вычислительную сложность разработанного алгоритма.
  • 4.5.2. Разработать алгоритм и программу проверки отношений и выполнения операций над графами. Отношения и операции определяются номером варианта задания (табл. 4.1). Считать, что в качестве исходных данных выступают один или два графа в зависимости от варианта задания. Исходные графы заданы и вводятся перечнями их вершин и ребер. Графы могут быть неориентированными и ориентированными. Для представления графов в памяти ЭВМ взять способ В. Тестовые примеры придумать самостоятельно. Оценить сложность алгоритма и программы по времени и используемой памяти.

Варианты

Таблица 4.1

Номер

варианта

Способ

представления графа

Отношения и операции над графами

А

В

1

1

2

Операция объединения

2

1

3

Отношение включения

3

2

3

Операция дополнения

4

2

4

Отождествление двух заданных вершин

5

3

4

Удаление заданной вершины Удаление заданного ребра

6

1

4

Отношение равенства

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>