2.1. Основные определения, способы задания, основные классы, изоморфизм графов

Графом (G) называется совокупность двух множеств: множества вершин (V) и множества ребер или дуг (E), между элементами которых определено отношение инцидентности.

Вершина и инцидентны друг другу, если вершина является для этого ребра концевой точкой.

Вершины и называются смежными, если существует ребро, соединяющее их, т.е. они инцидентны одному и тому же ребру.

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

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

Граф, содержащий направленные ребра (дуги) называется, называется неориентированным графом (н-графом).

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

Ребро, концевые вершины которого совпадают, называется петлей.

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

Нулевым, пустым (или полностью несвязным) графом называется граф с пустым множеством ребер (т.е. нулевой граф – это просто множество точек (вершин)).

Простым графом называется граф без петель или кратных ребер.

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

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

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

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

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