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

Граф G описывается множеством его вершин V и ребер E, т.е. G = (V, E), где <math>E \subseteq V \times V \;</math>. Обозначим за <math>N(v) \;</math> (открытую) [[окрестность]] вершины v, включающую все вершины, смежные с v; за <math>N[v] = N(v) \cup \{ v \} \;</math> – закрытую окрестность v; за <math>deg(v) = |N(v)| \;</math> – [[степень вершины]] v. Для множества вершин S, <math>N(S) = \bigcup_{v \in S} N(v) \;</math> и <math>N[S] = N(S) \cup S \;</math>. <math>G[S] \;</math> обозначает граф, порожденный множеством вершин S, т.е. <math>G[S] = (S, E \cap (S \times S)) \;</math>. Граф G = (V, E) с множеством вершин V и множеством дуг <math>E \subseteq V \times V \;</math> является [[двудольный граф|двудольным]], если существует разбиение <math>V \;</math> на два множества <math>V_1 \;</math> и <math>V_2 \;</math>, такие, что <math>V = V_1 \cup V_2 \;</math>, <math>V_1 \cap V_2 = \empty \;</math> и <math>E \subseteq V_1 \times V_2 \;</math>. Для наглядности запишем это в следующем виде: <math>G = (V_1, V_2, E) \;</math>.