Терминология и обозначения.

Граф G =( V , E ) задаётся непустым множеством V и множеством E, состоящим из пар элементов V.

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

Элементы V называются вершинами, элементы Е-рёбрами графа.

Если ребро ( a , b ) принадлежит графу, то вершины a и b называются смежными.

Графы  называют изоморфными, если существует  биекция такая, что для любых

Это обозначаются так: .

Степень вершины a – количество смежных с ней вершин.

Набор степеней графа – упорядоченная по неубыванию последовательность степеней вершин.

Путь в графе – последовательность вершин , такая, что .

Длина пути – число к-1.

Говорят, что путь соединяет вершины .Простой путь – путь, в котором все вершины различны.

Цикл – путь, в котором  и все рёбра различны. Простой цикл – цикл, в котором вершины  различны.

Связный граф – такой граф, в котором для любых двух вершин имеется соединяющий их путь.

Компонента связности - связный подграф, не содержащийся в большем связном графе.

Расстояние между вершинами связного графа – длина кратчайшего простого пути, соединяющего эти вершины.

Эксцентриситет вершины – расстояние от этой вершины до наиболее удалённой от неё.

Диаметр – максимальный среди всех эксцентриситетов вершин.

Радиус – минимальный среди всех эксцентриситетов вершин.

Центральная вершина – вершина, эксцентриситет которой равен радиусу графа.

Эйлеров цикл – цикл, проходящий через все рёбра графа.

Гамильтонов цикл – простой цикл, проходящий через все вершины графа.

Двудольный граф – граф, множество вершин которого можно разбить на две части (доли) так, что концы каждого ребра лежат в разных частях.

Дерево – связный граф, не имеющий циклов.

Лес – граф, не имеющий циклов.

Лист в дереве – вершина степени 1.

Плоский граф – граф, вершинами которого являются точки плоскости, а рёбрам соответствуют непрерывные линии, соединяющие смежные вершины, причем эти линии пересекаются только в вершинах.

Планарный граф – граф, изоморфный плоскому.

Пример 1. Дана матрица смежности. Постройте соответствующий ей граф. Найдите матрицу инцидентности.

Решение:

.

Пример 2. Задайте 10 пронумерованных вершин и

а) изобразите какое-нибудь дерево с этими вершинами;

Б) составьте для него последовательность по алгоритму Прюфера.

Код Прюфера: (5,2,5,2,9,8,8,9)

Пример 3. Определить, изоморфны ли графы (ответ обосновать).

Решение:

Установим изоморфизм:

Пример 4. Дан регулярный граф с 6 вершинами и 9 ребрами.

А) нарисуйте этот граф,

Б) напишите маршрут, цепь, цикл,