Основные понятия

Пусть $A, B, C, D, E, F$ — некоторые игроки в шахматы. Причем известно, что $A$ сыграл с $C, D, F$ (с последним два раза); $B$ сыграл с $C, E, F$; $C$ сыграл с $A, B$; D сыграл с $A, E, F$; $E$ сыграл с $B, D, F, E$; $F$ сыграл с $A$ (два раза) и с $B, D, E$. Информацию об этих играх можно проиллюстрировать следующей геометрической конфигурацией ($G$):

Построенная конфигурация полностью устанавливает информацию о встречах: игроки $X$ и $Y$ встречались, тогда и только тогда, когда в конфигурации $G$ соединены точки $X$ и $Y$ отрезком или дугой, причем количество таких дуг равно числу встреч игроков $X$ и $Y$. Если игрок $X$ сыграл сам с собой, то это будет тогда и только тогда, когда в конфигурации $G$ есть дуга, соединяющая точку $X$ с точкой $X$.

Конфигурация $G$ называется неориентированным графом (н-графом) или просто графом, при этом точки, изображающие $A, B, C, D, E, F$, называются вершинами графа $G$, а упомянутые дуги или отрезки, соединяющие вершины, называются ребрами графа $G$.

Заметим, что:

• в графе $G$ есть 2 ребра, соединяющие вершины $A$ и $F$. Такие ребра называются кратными или параллельными;
• ребра, соединяющие вершину с ней же, называются петлями;
• не исключено наличие вершин, не являющихся концом некоторого ребра (существование игрока, не сыгравшего ни одной партии).

Пусть $V = \{V_1, V_2,..., V_n\}$ — некоторое непустое множество произвольной природы элементов. $E$ — некоторое подмножество декартового произведения $V \times V \times N$, элементы которого называются ребрами. Тогда $G = (V, E)$ называется н-графом или графом, при этом элементы множества $V$ называются вершинами, а элементы множества $E$ ребрами данного графа.

Если $e = (V_i, V_j, k)$ — некоторое ребро графа $G$, то тройки $(V_i, V_j, k)$ и $(V_j, V_i, k)$ будем считать обозначением одного и того же ребра $e$.

Если вершины $V_i, V_j$ — концы ребра $e$, будем говорить, что вершины $V_i$, $V_j$ инцидентны ребру $e$ или ребро $e$ инцидентно вершинам $V_i$ и $V_j$. Два ребра, инцидентные одной вершине, называются смежными. Две вершины, инцидентные одному ребру, также называются смежными.

Вершина графа, не инцидентная ни одному ребру графа, называется изолированной.

Ребро вида $(V_i, V_i, k)$ называется петлей.

Если для ребра $e = (V_i, V_j, k_1)$ тройка $(V_i, V_j, k_2)$, $k_1 \ne k_2$ также является ребром графа, то ребро $e$ будем называть кратным.

Граф называется полным, если каждые две различные его вершины соединены одним и только одним ребром.