Основные определения и понятия темы

Граф, мультиграф, часть графа, подграф графа, матрица смежности, матрица инцидентности, операция удаления ребра, операция добавления ребра, операция удаления вершины, операция добавления вершины, операция введения вершины в ребро (операция подразделения ребра), операция отождествления вершин (операция стягивания ребра), операция расщепления вершины, дополнение графа, пересечение графов, объединение графов, кольцевая сумма графов, соединение графов, произведение графов, композиция графов, маршрут графа, матрица маршрутов, матрица смежности, сильная компонента графа, матрица расстояний графа, расстояние между вершинами графа, эксцентриситет вершины графа, диаметр и радиус связного неорграфа, периферийная вершина, центральная вершина.

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

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

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

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

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

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

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

	: :		: :
	: :		: :
	: :		: :
	: :		: :
	: :		: :
	: :		: :
	: :		: :
	: :		: :
	: :		: :
	: :		: :

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

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

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

	:		:
	:		:
	:		:
	:		:
	:		:
	:		:
	:		:
	:		:
	:		:
	:		:

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

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

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

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

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

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

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

	:		:
	:		:
	:		:
	:		:
	:		:
	:		:
	:		:
	:		:
	:		:
	:		: