Tabela de conteúdos

Separação de Conjuntos e Vértices

Definição

Seja ainda $G=(V,A)$. Se $A,B \subseteq V$ e $X \subseteq V \cup A$ são tais que todo caminho $A-B$ em $G$ contém um vértice ou uma aresta de $X$, dizemos então que $X$ separa os conjuntos $A$ e $B$ em $G$. Observe que isso implica que $A \cap B \subseteq X$.

Dizemos que $X$ separa dois vértices $a,b$ se separar os conjuntos $\{a\},\{b\}$, sendo $a,b \notin X$, e que $X$ separa $G$ se $X$ separa dois vértices quaisquer em $G$.

Um conjunto que separa vértices é chamado de Conjunto separador.

Veja também: