Методические указания к заданиям 4, 5.

Определение: Графом G(V,E)называется совокупность двух множеств – непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е – множество ребер).

Пусть v₁, v₂ – вершины, е=( v₁, v₂) – соединяющее их ребро. Тогда вершина v₁ и ребро е инцидентны, вершина v₂ и ребро е также инцидентны. Два ребра, инидентные одной вершине, называются смежными, две вершины, инцидентные одному ребру, также называютя смежными.

Обычно граф изображают диаграммой: вершины – точками, ребра – линиями.

П

e₃

ример:

V₆

О

e₇

пределение: Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (орграфом).

В этом случае элементы множества Е называются дугами. Первая вершина пары называется началом дуги, вторая – ее концом.

Р ебро, у которого начало и конец совпадают, называется петлей.

Пример:

Определение: Количество ребер, инцидентных вершине v, называется валентностью (степенью) вершины (Обозначается: d(v)).

"vÎV 0£d(v)£p-1, где p-вершин графа.

Если валентность вершины равна 0, то вершина называется изолированной, если валентность вершины равна 1, то вершина называется концевой (висячей).

Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода, а входящих – полустепенью захода.

Обозначается соответственно: d^-(v), d⁺(v).

Теорема Эйлера: Сумма степеней вершин графа равна удвоенному количеству ребер:

Способы задания графов.

Пусть граф G(V,E) – конечен.

v₁, v₂, ... , v_n – вершины графа, е₁, е₂, ... , е_m – ребра графа.

1. Матрица инцидентности – прямоугольная матрица n строк и m столбцов, в которой элемент

Для ориентированного графа:

Если e_i – петля, а v_j – инцидентная ей вершина, то с_ij =a, где a- любое число, отличное от 0,1,-1.

V₁

e₂

V₃

Пример 1:

е₃

V₄

e₁

_e4

e₅

V₂

Рисунок 1

Матрица инцидентности для данного графа имеет следующий вид:

V₂

e₂

Рисунок 2

Матрица инцидентности для данного графа имеет следующий вид:

Матрица смежности – это квадратная матрица, столбцы и строки которой соответствуют вершинам графа и элемент d_ij равен количеству ребер, инцидентных вершинам v_i и v_j, для ориетированного графа элемент d_ij равен количеству ребер с началом в вершине v_i и концом в вершине v_j.

Пример 2:

Матрица смежности для графа на рисунке 1 имеет вид:

Матрица смежности для графа на рисунке 2 имеет вид:

Пример 3:

Пример 4:

Изоморфность графов.

Два графа G₁ (V₁,E₁) и G₂ (V₂,E₂) изоморфны, если существует: h: V₁ V₂, cохраняющая смежность: l₁=(u,v)

Обозначается: ₁~G₂

Пример.

Т

v₂

ри внешне различные диаграммы являются диаграммами одного и того же графа

v₁

w₂

Числовая характеристика, одинаковая для всех изоморфных графов называется инвариантом графа p(G), g(G) – инварианты.

Двудольный граф (биграф, четный граф) – это граф G(V,E), такой что если множество V разбито на 2 непересекающихся множества V₁ и V₂ , причем всякое ребро из Е инцидентно вершине их V₂ и вершине из V_2.

Множества V₁ и V₂ называются долями.

Если двудольный граф содержит все ребра, соединенные V₁ и V₂, то он называется полным двудольным графом.

Если V₁=m, V₂=n, то полный двудольный граф обозначается К_m,n

Пример.

Диаграмма графа К_3,5

Теорема.

Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину.

Эйлеров цикл – простой цикл, содержащий все ребра графа.

Эйлеров граф – это граф, содержащий эйлеров цикл.

Две вершины называются связанными, если существует соединяющая их простая цепь.

Теорема Эйлера.

Конечный неориентированный граф G эйлеров тогда и только тогда, когда он связан и степени всех его вершин четны.

Граф, в котором все вершины связаны, называется связным.

Гамильтонов цикл – цикл, в котором каждая вершина встречается 1 раз.

Вариант 1.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «равенство отрезков».

Задание № 4.

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

Вариант 2.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «быть старше».

Задание № 4 .

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[N,A] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

Вариант 3.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «быть подчиненным».

Задание № 4 .

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[N,A] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

Вариант 4.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «быть выше ростом».

Задание № 4 .

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[N,A] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

Вариант 5.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «быть знакомым».

Задание № 4 .

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[N,A] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

Вариант 6.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «фигуры подобны».

Задание № 4 .

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[N,A] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

В ариант 7.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «окружности не пересекаются или совпадают».

Задание № 4 .

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[N,A] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

Вариант 8.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «число x больше или равно числа y».

Задание № 4 .

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[N,A] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

Вариант 9.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «число x меньше или равно числа y».

Задание № 4 .

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[N,A] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

Вариант 10.

Задание №1.

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграмм Эйлера-Венна.

Задание №2.

С помощью таблицы истинности установите эквивалентны ли данные формулы:

Задание № 3.

Проверьте является ли данное отношение отношением эквивалентности.

Отношение «число x больше числа y».

Задание № 4 .

Нарисовать на плоскости граф G=[V,E] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности r_ijграфа G.

Задание № 5.

Нарисовать на плоскости орграф G=[N,A] (единственный с точностью до изоморфизма), имеющий заданную матрицу _ijсвоей матрицей смежности. Найти матрицу инцидентности c_ijграфа G.

ЛИТЕРАТУРА

1. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. - М.: Высшая школа, 1976.

2. Березина Л.Ю. Графы и их применение. – М.: Просвещение, 1979.

3. Берж К. Теория графов и ее применение. – М.: ИЛ, 1962.

4. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1977.

5. Гиндикин С.Г. Алгебра логики в задачах. – М.: Наука, 1979.

6. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1987.

7. Дориченко С.А., Ященко В.В. 25 этюдов о шифрах. – М.: ТЕИС, 1994.

8. Евстигнеев В.А. Применение теории графов в программировании. – М.: Наука, 1985.

9. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.

   10. . Зыков А.А. Основы теории графов. – М.: Наука , 1987.

11. Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику. – М.: ИЛ, 1963.

12. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергия, 1980.

13. Липский В. Комбинаторикм для программистов. – М.: Мир, 1988.

14. МелиховА.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971.

15. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 1992.

16. Никольская И.Л. Математическая логика. – М.: Высшая школа, 1981.

17. Оре О. Теория графов. – М.: Наука , 1980.

18. Сигорский В.П. Математический аппарат инженера. – Киев: Техника, 1975.

19. Харари Ф. Теория графов. – М.: Мир, 1973.

20. Яблонский С.В. Введение в дискретную математику. – М.: Наука , 1986.

21. Яблонский С.В. Методические разработки по курсу «Элементы дискретной математики». – М.: Издательство

22. МГУ, 1971.

23. Новиков Ф.А. Дискретная математика для программистов. –СПб: Питер, 2001.