Revisão das 23h51min de 4 de novembro de 2010 editar Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 489 edições ← Ver a alteração anterior		Revisão das 17h30min de 6 de novembro de 2010 editar desfazer Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 489 edições Ver a alteração posterior →
Linha 1: ~~{{em tradução}}~~ [[Image:Simple-bipartite-graph.svg\|200px\|thumb\|Exemplo de um grafo bipartido]] Linha 40 ⟶ 39: * Um grafo é bipartido [[se e somente se]] ele não contém um [[ciclo ímpar]]. Portanto, um grafo bipartido não pode conter uma [[clique]] de tamanho maior ou igual a 3. * Um grafo é bipartido se e somente se ele é 2-colorível, (i.e. seu [[número cromático]] é menor ou igual a 2). * O tamanho da [[Cobertura de vértices (teoria dos grafos)\|cobertura de vértices mínima]] é igual ao tamanho do [[Acoplamento (teoria dos grafos)\|acoplamento máximo]] ([[teorema de König (teoria dos grafos)\|teorema de König]]). * O tamanho do [[Conjunto independente\|conjunto independente máximo]] mais o tamanho do acoplamento máximo é igual ao número de vértices. * Para um grafo bipartido [[grafo conectado\|conectado]] o tamanho da [[Cobertura de arestas (teoria dos grafos)\|cobertura de arestas mínima]] é igual ao tamanho do conjunto independente máximo. * Para um grafo bipartido conectado o tamanho da cobertura de arestas mínima mais o tamanho da cobertura de vértices mínima é igual ao número de vértices. * Todo grafo bipartido é um [[grafo perfeito]]. * O [[teoria dos grafos espectrais\|espectro]] de um grafo é simétrico se e somente se ele é um grafo bipartido. =={{Ver Também}}== ~~<!--~~ * [[Grafo bipartido completo]] * The size of [[minimum vertex cover]] is equal to the size of the [[maximum matching]] ([[König's theorem (graph theory)\|König's theorem]]). * The size of the [[maximum independent set]] plus the size of the maximum matching is equal to the number of vertices. * For a [[connected graph\|connected]] bipartite graph the size of the [[minimum edge cover]] is equal to the size of the maximum independent set. * For a connected bipartite graph the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices. * Every bipartite graph is a [[perfect graph]]. * The [[Spectral graph theory\|spectrum]] of a graph is symmetric if and only if it's a bipartite graph. ~~==See also==~~ * [[Complete bipartite graph]] * [[Dulmage–Mendelsohn decomposition]] * [[Adjacency matrix of a bipartite graph]] * [[Record linkage]] * {{mathworld \| title = Bipartite Graph \| urlname = BipartiteGraph}} ~~-->~~ =={{Ligações externas}}== * [http://wwwteo.informatik.uni-rostock.de/isgci/index.html stema de Informações sobre inclusões de classes de grafos]: [http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_69.html grafo bipartido] {{Referências}}

Grafo bipartido: diferenças entre revisões