grafos:grafos [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.
====== Grafos ======

<WRAP round tip box 100%>
Veja o glossário [[.:defBasicas|aqui]].
</WRAP>

===== Teoria Básica =====

  * [[.historiaGrafos| As Sete Pontes de Königsberg]]
  * [[.definicaoGrafos| Definição de grafo]]
  * [[.degreegraph | Adjacência e Grau de um Grafo]]
  * [[.subgrafos| Subgrafos]]
  * [[.caminhos| Passeios, Caminhos e Ciclos]]
  * [[.tiposGrafos| Tipos Básicos de Grafos]]


  * [[.multigrafo1 | Multigrafos e propriedades]]
  * [[.arvGraph | Árvores e Florestas]]
===== O grau de um vértice =====

  * [[.numTotaldeArestas|Lema do Aperto de Mão]]
  * [[.totGrauImparPar|A quantidade de vértices de grau ímpar é par]]
  * [[.subgrafoGrauMinimo| Existe H subgrafo de G, tal que: $\delta (H) > \varepsilon (H) \geq \varepsilon (G)$]]
  * [[.difdmed| $d_{med}(G) \neq \varepsilon(G)$]]

===== Caminhos e ciclos =====

  * [[.tamanhocaminhoeciclograumin|Inferência do tamanho de caminhos e/ou de ciclos em grafos a partir de seu grau, quando $\delta(G) \geq 2$]]
  * [[.cinturagrafocomciclo|Todo grafo com ciclo respeita a relação: $g(G) \leq 2 diam(G) + 1$]]
  * [[.raioEdiametro|Uma relação entre raios e diâmetros]]
  * [[.raioEvertices|Relação entre o raio de um grafo e o seu número de vértices]]

===== Circuito euleriano =====

    * [[.defeuler | Circuito Euleriano: Definição]]
    * [[.teoeuler | Teorema de Euler]]
===== Conexidade =====

  * [[.conexidad| Conexidade: Fundamentos]]
  * [[.enuconexo|A ordem dos vértices em um grafo conexo]]
  * [[.connectivity| Conectividade]]
  * [[.cicloDeltaKConexidade|Uma relação de $k$-conexidade,$\ell$-aresta-conexidade e grau mínimo]]
  * [[.2conexo|Grafos e subgrafos $2$-conexos]]


  * [[.TeoremaMader|O Teorema de Mader]]
  * [[.TeoremaMenger|Teorema de Menger]]
  * [[.linkindpairs | Ligando pares de vértices]]



  * [[.maxfluxmincut| Fluxo máximo é o corte mínimo]]
===== Árvores e Florestas =====

  * [[.defarvores | Árvores e Florestas: Primeiras definições e algumas equivalências]]
  * [[.arvenraizadas | Árvores Enraizadas: algumas definições e notações]] 
  * [[.arvoresnormais | Árvores normais]]
  * [[.arvoresnormaispropriedades | Algumas propriedades de árvores normais]]



  * [[.treepacking | Empacotamento de árvores]].

===== Grafos bipartidos =====

  * [[.defbipartite | Grafos Bipartidos: Definições iniciais]]
  * [[.matching&alternatingpaths | Emparelhamentos em grafos bipartidos]]
  * [[.konigtheorem | Teorema de Emparelhamento de König]]
  * [[.teoremahall | Condição de casamento: o Teorema de Hall]]
  * [[.conseqHall | Consequências do Teorema de Hall]]
  * [[.casamentoestavel | Emparelhamentos estáveis]]
  * [[.teoempperfeito | Teorema do Emparelhamento Perfeito]]
  * [[.3regempper | Grafo cúbicos e emparelhamentos perfeitos]]
  * [[.complement | Complementar: Teorema do Emparelhamento perfeito]]
  * [[.theoremEdrosPosa | Teorema de Erdős-Pósa]]
  * [[.arboricitypacking | O Teorema do Empocatamento-Cobertura e Arbocidade]]
  * [[.coverpaths | Cobertura de Caminhos]]


  * [[.jogoemp | Jogo com empararelhamento perfeito]]

===== Minors =====
 		 	
  * [[.subdivisao&minortopologico |Minors: Subdivisão, Inflação e Minor Topológico]]
  * [[.inflacao&minor |Contrações e uma condição para existência de um Minor]]
  * [[.minorvsminortopologico | Relações entre minors e minors topológicos]]


  * [[.seymourminorconjecture|Conjectura do menor de Seymour]]

===== Álgebra Linear básica (para grafos) =====

  * [[.algebralinbas | Algebra Linear básica para grafos]]

===== Estrutura de um grafo $3$-conexo =====

  * [[.estruct3connect | A estrutura de um grafo $3$-conexo a partir de um $K^4$: com multigrafos]]
  * [[.estruct3connected |A estrutura de um grafo $3$-conexo: sem multigrafos]]
  * [[.theoremtuttegeneral | Teorema de Tutte]]


===== Grafos Planares =====

  * [[.pretopology | Pré-requisitos topológicos para a seção]]
  * [[.topintrod | Grafos Planares: Introdução]]
  * [[.topicosplan | Alguns resultados: limites e faces]]
  * [[.limgrafoscub | $3$-conexo e Triangulação Plana]]
  * [[.eulersform | Fórmula de Euler e algumas consequências]]
  * [[.incorp |Incorporações planares: Teorema de Whitney]]
  * [[.graphplanar | Grafo Planar e resultados auxiliares]]
  * [[.lema1planar | Grafos $3$-conexos, minors topológicos,$TK^{5}$ e $TK_{3,3}$]]
  * [[.corolario1planar | Teorema de Kuratowski: Algumas equivalências]]
  * [[.criterionplanarity | Critérios de planaridade algébrica]]
  * [[. planeduality | Dualidade Plana]]

===== Coloração =====


  * [[.colouringintro | Coloração: Mapas de coloração e grafos planares]]
  * [[.teo5cores | Teorema das cinco cores]]
  * [[.numerdecores | Número de cores de um grafo]]
  * [[.alggul | Algorítmo guloso e $Col(G)$]]
  * [[.lemakcolor | $k$-coloração de um subgrafo]]
  * [[.teobrooks | Teorema de Brooks]]
  * [[.teoerdos | Teorema de Erdós e o Teorema de Hajós]]
  * [[.colarestas | Colorações de arestas]]
  * [[.listcolouring | Lista de Coloração]]
  * [[.perfectgraphs | Grafos Perfeitos]]


===== Extremal =====
  * [[.extremal| Teorema de Turán]]

===== Grafos Infinitos =====
  * [[.conceitosinfinito| Conceitos básicos]]
  * [[.subdivisãoalephzero| Subdivisão de $K^{\aleph_{0}}$]]
  * [[.muitasarvoresgeradoras| Enumeráveis árvores geradoras disjuntas]]
  * [[.cinturagrande| Cinturas grandes]]
  * [[.conexidadearvoregeradora| Todo grafo conexo contém uma árvore geradora]]
  * [[.koniginfinity | Lema da Infinitude de König]]
  * [[.teobruijnerdos | Teorema de de Bruijn-Erdős]]
  * [[.defunfriendlypartition | Unfriendly Partition]]
  * [[.estrelapente | Grafos infinitos conexos e o Lema da Estrela-pente]]
  * [[.raylessIdeiasEProps | Grafos sem raios ]]
  * [[.decomposiçãoemArv | Decomposição em Árvores ]]

===== Problemas em aberto =====

  * [[.quasesuaves | Almost smooth graphs]]
  * [[.brickfactory | O Problema da Fábrica de Tijolos]]
  * [[.quasegeradores | Subgrafos regulares quase geradores]]
  * [[.ncromplano | Número cromático do plano]]
  * [[.grafosgemeos | Dicotomia dos Grafos Gêmeos]]
  * [[.conjecturadareconstrucao | Conjectura da Reconstrução]]

===== Glossário =====

<WRAP round tip box 100%>
Veja o glossário [[.:defBasicas|aqui]].
</WRAP>

===== Exercícios (em construção) =====

  * [[.exercicios|Exercícios]]