Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| grafos:connectivity [2023/08/10 15:20] – edição externa 127.0.0.1 | grafos:connectivity [2023/08/10 15:37] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 28: | Linha 28: | ||
| <WRAP round box 100%> | <WRAP round box 100%> | ||
| === Definição: | === Definição: | ||
| - | //O par não ordenado $\{A,B\}$ é uma separação de $G$ se $A \cup B = V$ e $G$ não tem arestas entre $A \setminus B$ e $B \setminus A$. Claramente, o último é equivalente a dizer que $A \cap B$ separa $A$ de $B$. Se ambos $A \setminus B$ e $B \setminus A$ são não vazios, dizemos que a separação é **adequada**. O número $|A \cap B|$ é a **ordem** da separação $\{A,B\}$, e os conjuntos A, B são seus lados.// | + | //O par não ordenado $\{A,B\}$ é uma separação de $G$ se $A \cup B = V$ e $G$ não tem arestas entre $A \setminus B$ e $B \setminus A$. Claramente, o último é equivalente a dizer que $A \cap B$ separa $A$ de $B$.// |
| + | |||
| + | //Se ambos $A \setminus B$ e $B \setminus A$ são não vazios, dizemos que a separação é **adequada**. O número $|A \cap B|$ é a **ordem** da separação $\{A,B\}$, e os conjuntos A, B são seus lados.// | ||
| </ | </ | ||
| ==== $k$-conexidade ==== | ==== $k$-conexidade ==== | ||
| <WRAP round box 100%> | <WRAP round box 100%> | ||
| === Definição === | === Definição === | ||
| - | //$G$ é dito [[.defKConexo|$k$-conexo]] (para $k \in \mathbb{N}$) se $|V| > k$ e $G-X$ é conexo para qualquer conjunto $X \subseteq V$ com $|X| < k $. Em outras palavras, não há dois vértices de $G$ separados por menos de $k$ outros vértices.// | + | //Um grafo $G=(V,A)$ é dito [[.defKConexo|$k$-conexo]] (para $k \in \mathbb{N}$) se $|V| > k$ e $G-X$ é conexo para qualquer conjunto $X \subseteq V$ com $|X| < k $. Em outras palavras, não há dois vértices de $G$ separados por menos de $k$ outros vértices.// |
| </ | </ | ||
| - | Todo grafo não vazio é $0$-conexo, e os grafos $1$-conexos são precisamente os grafos conexos não triviais. O maior inteiro $k$ tal que $G$ é $k$-conexo é a **conectividade** $k(G)$ de $G$. Portanto, $k(G) = 0$ se, e somente se, $G$ é desconexo ou se [[.defCompleto|$K^1$]], e $k(K^n) = n-1$ para todo $n \geq 1$. | + | Todo grafo não vazio é $0$-conexo, e os grafos $1$-conexos são precisamente os grafos conexos não triviais. O maior inteiro $k$ tal que $G$ é $k$-conexo é a **conectividade** $\kappa |
| ==== $\ell$-aresta-conexidade ==== | ==== $\ell$-aresta-conexidade ==== | ||
| Linha 42: | Linha 45: | ||
| <WRAP round box 100%> | <WRAP round box 100%> | ||
| === Definição === | === Definição === | ||
| - | //Um grafo $G = (V, A)$ é dito [[.defLarestaconex |$\ell$-aresta-conexo]] ($\ell \in \mathbb{N}$) se $|V|>1$ e $G - F$ é conexo para todo conjunto $F\subset | + | //Um grafo $G = (V, A)$ é dito $\ell$-aresta-conexo ($\ell \in \mathbb{N}$) se $|V|>1$ e $G - F$ é conexo para todo conjunto $F\subset |
| + | |||
| + | //O maior inteiro $\ell$ para o qual $G$ é $\ell$-aresta-conexo é a ** aresta-conectividade** de $G$, denotada por $\lambda(G)$. Em particular, temos que $\lambda(G) = 0 $ se $G$ é desconexo.// | ||
| </ | </ | ||
| Linha 54: | Linha 59: | ||
| ---- | ---- | ||
| - | <WRAP round tip box 30%> | + | <WRAP round tip box 50%> |
| === Leia também === | === Leia também === | ||
| * [[.cicloDeltaKConexidade|Uma relação de $k$-conexidade, | * [[.cicloDeltaKConexidade|Uma relação de $k$-conexidade, | ||