Основные теоремы и утверждения темы

Теорема о рукопожатии, теорема о числе маршрутов длины k графа, критерий взаимной достижимости вершин графа, теорема Эйлера, характеризационная теорема.

Рекомендуемая литература

1. С.В. Судоплатов, Е.В. Овчинникова. Элементы дискретной математики. – Москва – Новосибирск, 2002.

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

3. Г.П. Гаврилов, А.А. Сапоженко. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992.

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

1	: :	5	: :
2	: :	6	: :
3	: :	7	: :
4	: :	8	: :
9	: :	14	: :
10	: :	15	: :
11	: :	16	: :
12	: :	17	: :
13	: :	18	: :
19	: :	20	: :

Задание 1.2.Для графа G найти:

а) матрицы маршрутов длины 2 и 3;

б) все маршруты длины 2 и 3.

1	:	4	:
2	:	5	:
3	:	6	:
7	:	12	:
8	:	13	:
9	:	14	:
10	:	15	:
11	:	16	:
17	:	19	:
18	:	20	:

Задание 1.3.Для графа G из задания 1.2 найти все сильные компоненты.

Задание 1.4.Для графа G найти:

а) матрицу расстояний;

б) эксцентриситеты всех вершин;

в) диаметр и радиус;

г) периферийные вершины;

д) центральные вершины.

1	:	3	:
2	:	4	:
5	:	13	:
6	:	14	:
7	:	15	:
8	:	16	:
9	:	17	:
10	:	18	:
11	:	19	:
12	:	20	: