Ход работы. 1.Выполнить приведенные ниже задачи

1.Выполнить приведенные ниже задачи

Задание №1

1)Сколько вершин? Какие смежные, а какие нет?

2)Сколько ребер? Какие смежные, а какие нет?

Задание №2

А) Будут ли графы изоморфны?

Б) Будут ли графы изоморфны?

В)Построить граф, изоморфный любому из б).

Задание №3

Определить степени (полустепени) вершин

А)

Б)

Задание №4

Определить: Маршрут, цепь, простую цепь, цикл, простой цикл.

1. v₁, v₃, v₁, v₄

2. v₁, v₄, v₃, v₂, v₅

3. v₁, v₃, v₅, v₂, v₃, v₄, v₁

4. v₁, v₃, v₄, v₁

5. v₁, v₃, v₅, v₂, v₃, v₄

Задание 5.

Приведите пример ориентированного и неориентированного графа. Для заданных вершин u, v найдите все цепи и простые цепи их связывающие.

Задание 6.

Приведите пример ориентированного и неориентированного графа. Для заданной вершины v постройте цикл (контур), простой цикл (простой контур) ее содержащий

Задание 7.

Найти матрицы смежности и инциденций для графов.

Задание 8.

Построить изображение графа (орграфа). Найти степени (полустепени) вершин. Постройте матрицу инцидентности этого графа.

а) 0 1 1 0 0 0 б) 1 0 1 1 0 0

0 0 1 1 0 0 0 0 0 1 1 0

1 0 0 0 0 1 1 0 0 0 0 1

1 1 1 0 0 1 1 1 0 1 0 0

0 0 0 0 0 1 0 1 0 0 2 0

1 0 1 1 0 0 0 0 1 0 0 0

Задание9.

Дана матрица A(D) или B(D)

Найти матрицу B(D) или A(D)

1)A(D)=

2)B(D)=

Задание10. Приведите пример

1) Полного графа К₃, К₄

2) Регулярного графа при k=2, 3, 4

3) Полностью несвязного графа N₃, N₅

4) Двудольного графа К₃К₅, К₁К₈

5) Плоского графа с пятью вершинами

6) Планарного графа с пятью вершинами

2.Форма отчета

1.Прорешать представленные задачи в тетради

2.Оценить свою работу по следующей схеме:

5 задач – 3 балла

6 задач - 4 балла

7 задач – 5 баллов

3. Задание на внеаудиторную самостоятельную работу

1. Граф задан диаграммой.

1) Составьте для него матрицу смежности

2) Постройте матрицу инцидентности

3) Укажите степени(полустепени) вершин графа

4) Найдите длину пути из вершины v1 в вершину v5, составьте маршруты длины 5, цепь и простую цепь, соединяющие эти вершины

5) Постройте простой цикл, содержащий вершину v4

6) Определите вид заданного графа

a)

б)

2. Ответить на контрольные вопросы

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

1. Степень (полустепень) вершины?

2. Свойства изоморфизма?

3.Цепь, простая цепь, цикл, простой цикл, контур?

4. Матрица смежности для ориентированных и неориентированных графов, псевдографов?

5. Матрица инцидентности для ориентированных и неориентированных графов?

Литература

1. В.Н. Нефедов «Курс дискретной математики»

г. Москва, изд. МАИ, 2010 год

2. В. Новиков «Курс дискретной математики для программистов»

г. Москва, 2012 год

3.М.С. Спирина, П.А. Спирин «Дискретная математика»- М.: Издательский центр «Академия», 2008 год