Параметризованные алгоритмы графического представления графов: различия между версиями

Граф G описывается множеством его вершин V и ребер E, т.е. G = (V, E), где E С V x V. Обозначим за N(v) (открытую) окрестность вершины v, включающую все вершины, смежные с v; за N[v] = N(v) [ fvg – закрытую окрестность v; за deg(v) = jN(v)j – степень вершины v. Для множества вершин S, N(S) = Sv2S N(v) и N[S] = N(S) [ S. G[S] обозначает граф, порожденный множеством вершин, т.е. G[S] = (S;E \ (S x S)). Граф G = (V, E) с множеством вершин V и множеством дуг E С V x V является двудольным, если существует разбиение V на два множества V1 и V2, такие, что V = V1 [ V2, VI \ V2 = ; и E С V1 x V2. Для наглядности запишем это в следующем виде: G = (V1, V2, E).