Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)
План:
1. Определение графа. Простой граф.
2. Мультиграф. Псевдограф. Полный граф.
3. Матрицы смежности и инцидентности. Изоморфизм графов
Ключевые слова: графа, простой граф, мультиграф, псевдограф, полный граф, матрицы смежности и инцидентности, изоморфизм.
1. Определение графа. Простой граф.
Введем основные понятия и рассмотрим способы задания графов.
Многие отношения на конечных множествах можно изобразить в виде рисунков. Например, отношение хry = {(x, y)∈A: x < y}, где A = {1, 2, 3, 4}, или в явном виде r = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}, можно изобразить на плоскости в виде точек с координатами (x, y).
Представим на плоскости некоторое конечное множество V точек и конечный набор X линий, соединяющих некоторые пары точек из V. Простым примером подобной геометрической конфигурации может служить любая схема автомобильных дорог, связывающих города некоторой области, которые мы можем обозначить буквами А, В, С, D (Рисунок
Для многих задач оказывается несущественным, как соединяются точки – отрезками или дугами. Важно лишь то, что каждая линия соединяет какие-либо две точки из заданного набора точек. Введенная пара множеств (V, X) допускает также и другие интерпретации и является предметом детального изучения в разных разделах математики.
П ри рассмотрении подобных задач достаточно ограничиться исследованием совокупности двух конечных множеств V и X, где V – непустое множество; X – некоторый набор элементов из множества V вида {v_i, v_j}.
Элементы множества V называются вершинами, а элементы множества X – ребрами.

Во множестве X могут встречаться пары с одинаковыми элементами вида {v, v}, а также одинаковые пары. Ребра вида {v, v} называются петлями. Одинаковые пары в X называются кратными, или параллельными ребрами.

Количество одинаковых пар {v_i, v_j} в X называются кратностью ребра {v_i, v_j}.
Про множество V и множество X будем говорить, что они определяют граф с кратными ребрами и петлями, или псевдограф G = (V, X).

Рассмотрим чертеж вида

города



ребра

дороги

вершины