Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Домашка (ППЗ).doc
Скачиваний:
63
Добавлен:
15.05.2015
Размер:
662.02 Кб
Скачать

Практическое занятие 1. Способы задания графов. Части и подграфы графов.

Контрольные вопросы:

  1. Мультиграф.

  2. Ориентированное ребро.

  3. Кратные ребра.

  4. Граф.

  5. Ориентированный мультиграф.

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

  7. Петля.

  8. Псевдограф.

  9. Смежные вершины.

  10. Смежные ребра.

  11. Степень вершины.

  12. Конечный граф.

  13. Матрица смежности графа.

  14. Матрица инцидентности мультиграфа.

  15. Часть графа.

  16. Подграф графа.

План занятия.

  1. Теоретический диктант.

  2. Решение типовых задач.

Номер задания

Аудиторная работа

Домашняя работа

1

1)

2)

2

1)

2)

3

1)

2)

4

1)

2)

5

1)

2)

Задание 1.ГрафGзадан графически. Задать графG

а) аналитически;

б) с помощью матрицы смежности;

в) с помощью списка дуг;

г) с помощью структуры смежности.

1) G: 2)G:

Задание 2.Для графаиз задания 1 выписать и изобразить одну часть и один подграф.

Задание 3.Изобразить графически следующие графы:

а)граф, заданный матрицей смежности:

1)2)

б)граф 6 порядка, заданный списком дуг:

1) 2)

в)граф, заданный с помощью структуры смежности

1) a - a, d 2) a - b, e

b - b, c, d b - a, c

c - a c - c, b

d - - d - d

e - e, a

Задание 4.Составить матрицу инцидентности следующих мультиграфов:

1) G: 2)G:

Задание 5.Изобразить графически мультиграфы, заданные матрицей инцидентности:

1)2)

Практическое занятие 2. Операции над графами.

Контрольные вопросы:

  1. Операция удаления ребра.

  2. Операция добавления ребра.

  3. Операция удаления вершины.

  4. Операция добавления вершины.

  5. Операция введения вершины в ребро (операция подразделения ребра).

  6. Операция отождествления вершин (операция стягивания ребра).

  7. Операция расщепления вершины.

  8. Дополнение графа.

План занятия.

  1. Теоретический диктант.

  2. Проверка домашнего задания.

  3. Решение типовых задач.

Номер задания

Аудиторная работа

Домашняя работа

1

а),б)

в)

Задание 1.Выполнить следующие операции над графомG:

a)G: б)G: в)G:

1) Удалить ребро (2,3);

2) Добавить ребро (1,5);

3) Удалить вершину 3;

4) Добавить вершину 7;

5) Ввести вершину 5 в ребро(4,1);

6) Отождествить вершины 2и3;

7) Расщепить вершину 3 по разбиениюмножества,;

8) Построить дополнение

Практическое занятие 3. Бинарные операции над графами.

Контрольные вопросы:

  1. Пересечение графов.

  2. Объединение графов.

  3. Кольцевая сумма графов.

  4. Соединение графов.

  5. Произведение графов.

  6. Композиция графов.

План занятия.

  1. Теоретический диктант.

  2. Проверка домашнего задания.

  3. Решение типовых задач.

Номер задания

Аудиторная работа

Домашняя работа

1

а)

б)

Задание 1.Для графовинайти графы(Записать аналитически и изобразить графически).

а)

G1: G2:

б) G1: G2:

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]