Головна

завдання

  1. II. ЗАВДАННЯ № 1
  2. III. практичне завдання
  3. IV. Завдання для підготовки до практичної роботи №1
  4. IV. Завдання для підготовки до практичної роботи №2
  5. IV. практичне завдання
  6. Г.2 Завдання основне
  7. діагностичне завдання

I. Пошук гамільтонова шляху (ДП) в графі.

1.1. Для заданого графічно, орієнтованого графа скласти матрицю R1 досяжності не більше ніж за один крок.

1.2. Знайти ДП в графі, використовуючи алгоритм Фаулкса.

1.3. Знайти ДП в графі, використовуючи алгоритм Робертса і Флореса для початкової вершини, обраної в п. 1.2.

1.4. Знайти ДП в графі для початкової вершини, обраної в п. 1.2, використовуючи стандартну програму на ЕОМ, порівняти отримані результати.

1.5. Запропонувати словесний опис завдання, що відповідає заданому графу.

2. Визначення зв'язності графа.

2.1. Для заданого за допомогою матриці суміжності неорієнтованого графа знайти зв'язкові компоненти, використовуючи алгоритм Фаулкса.

2.2. Уявити заданий граф графічно.

2.3. Знайти зв'язкові компоненти в графі, використовуючи стандартну програму на ЕОМ. Порівняти отримані результати.

2.4. Запропонувати словесний опис завдання, що відповідає заданому графу.

3. Пошук ейлерового шляху (ЕП) в графі.

3.1. Для заданого графічно неориентированного графа скласти матрицю досяжності за один крок.

3.2. Знайти ЕП в графі, використовуючи алгоритм, наведений нижче в методичних вказівках.

3.3. Знайти ЕП в графі для початкової вершини, обраної в п. 3.2, використовуючи стандартну програму на ЕОМ. Порівняти отримані результати.

3.4. Запропонувати словесне зміст завдання, що відповідає заданому графу.

4. Пошук сильних компонент, базового і домінуючого множин в графі.

4.1. Для заданого викладачем графа знайти матриці досяжності L, і контрдостіжімості Q.

4.2. Знайти сильні компоненти графа. Скласти конденсацію графа.

4.3. Запропонувати алгоритми знаходження базового і домінуючого множин в графі.

4.4. Знайти за допомогою запропонованих алгоритмів базове і домінуючі безлічі.

4.5. Запропонувати словесне зміст завдання, що відповідає заданому графу.

5. Скласти звіт. Відповісти на контрольні питання.



Вихідні дані (завжди апріорна інформація). | Методичні вказівки

Робота 1. ДОСЛІДЖЕННЯ І ОПИС КІНЦЕВОГО АВТОМАТА | Методичні вказівки | Методичні вказівки | Лабораторні роботи з курсу: ДМ | Загальні відомості | Методичні вказівки | Визначення гамільтонова шляху в графі | Визначення зв'язності графа | Визначення ейлерового шляху в графі | Знаходження сильних компонент, базового і домінуючого множин |

© um.co.ua - учбові матеріали та реферати