Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| Próxima revisão | Revisão anterior | ||
| grafos:conjecturadareconstrucao [2022/09/27 16:49] – criada modeus | grafos:conjecturadareconstrucao [2022/09/30 23:32] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 45: | Linha 45: | ||
| * Grafos separáveis sem vértices de grau $1$ | * Grafos separáveis sem vértices de grau $1$ | ||
| * Árvores | * Árvores | ||
| + | * Cactos | ||
| + | * Grafos planares maximais | ||
| + | * Grafos exoplanares maximais | ||
| + | * Grafos exoplanares | ||
| + | * Grafos completos multipartidos | ||
| __As seguintes classes são reconhecíveis__ | __As seguintes classes são reconhecíveis__ | ||
| Linha 50: | Linha 55: | ||
| * Subdivisões de grafos $3$-conexos | * Subdivisões de grafos $3$-conexos | ||
| * Grafos planares | * Grafos planares | ||
| + | * Grafos perfeitos | ||
| ==== Parâmetros Reconstrutíveis ==== | ==== Parâmetros Reconstrutíveis ==== | ||
| Linha 63: | Linha 69: | ||
| * Diâmetro | * Diâmetro | ||
| * Conectividade | * Conectividade | ||
| + | * Aresta-conectividade | ||
| * Número cromático | * Número cromático | ||
| * Polinômio cromático | * Polinômio cromático | ||
| Linha 79: | Linha 86: | ||
| Sejam $F, G$ grafos com $|V(F)|< | Sejam $F, G$ grafos com $|V(F)|< | ||
| + | </ | ||
| + | |||
| + | <WRAP round box 80%> | ||
| + | === Lema === | ||
| + | Sejam $F, G$ grafos com $F$ desconexo. Então o número $s(F, G)$ de subgrafos de $G$ isomorfos a $F$ é reconstrutível. | ||
| </ | </ | ||
| Linha 92: | Linha 104: | ||
| <WRAP round box 80%> | <WRAP round box 80%> | ||
| === Teorema === | === Teorema === | ||
| - | Se o grafo $G$ é reconstrutível sempre que $diam(G) = 2$ ou $diam(G) = diam(\overline{G}) = 3$, então | + | Se o grafo $G$ é reconstrutível sempre que $diam(G) = 2$ ou $diam(G) = diam(\overline{G}) = 3$, então |
| </ | </ | ||