4. Типы графов, дополнительные графы, двудольные графы, критерий двудольности.

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

Определение. Полный n-вершинный граф (клика) – это граф, в котором любые две вершины соединены ребром (обозначается );

Определение. Нулевой n-вершинный граф – это граф без ребер (обозначается );

Определение. Граф называется связным, если в нем любые две вершины соединены цепью.

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

Утверждение. Критерий двудольности графа - необходимо и достаточно, чтобы в этом графе все циклы имели четную длину.

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

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