Revisão das 19h24min de 28 de outubro de 2010 editar Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 734 edições ← Ver a alteração anterior		Revisão das 13h51min de 29 de outubro de 2010 editar desfazer Ricardo Ferreira de Oliveira (discussão \| contribs) Administradores 26 734 edições Ver a alteração posterior →
Linha 14: Toda [[árvore (grafo)\|árvore]] é bipartida. [[grafo ciclo\|grafos ciclo]] com um número par de vértices são bipartidos. Qualquer [[grafo planar]] onde todas as faces em sua representação planar consistem de um número par de arestas é bipartido. Casos especiais destes são [[grafo grelha\|grafos grelha]] e [[grafo quadrado\|grafos quadrado]], em que cada face interna é composta por 4 arestas. ==Testando biparticidade== [[~~Image~~Ficheiro:RecursiveEvenBipartite.svg\|thumb\|~~Finding~~Encontrando auma ~~bipartition~~bipartição ~~using~~usando ~~parity~~paridade]]▼ Se um grafo bipartido é [[Conectividade (teoria dos grafos)\|conexo]], a sua bipartição pode ser definida pela [[Paridade (matemática)\|paridade]] das distâncias de qualquer vértice escolhido arbitrariamente ''v'': um subconjunto consiste dos vértices a uma distância par de ''v'' e o outro subconjunto consiste dos vértices a uma distância ímpar de ''v''. <!-- [[Cycle graph]]s with an even number of vertices are bipartite. ** Any [[planar graph]] where all the [[Glossary of graph theory#Genus\|faces]] in its planar representation consist of an even number of edges is bipartite. Special cases of this are [[grid graph]]s and [[squaregraph]]s, in which every inner face consists of 4 edges. ~~==Testing bipartiteness==~~ ▲[[Image:RecursiveEvenBipartite.svg\|thumb\|Finding a bipartition using parity]] If a bipartite graph is [[Connectivity (graph theory)\|connected]], its bipartition can be defined by the [[Parity (mathematics)\|parity]] of the distances from any arbitrarily chosen vertex ''v'': one subset consists of the vertices at even distance to ''v'' and the other subset consists of the vertices at odd distance to ''v''. Thus, one may efficiently test whether a graph is bipartite by using this parity technique to assign vertices to the two subsets ''U'' and ''V'', separately within each [[Connected component (graph theory)\|connected component]] of the graph, and then examine each edge to verify that it has endpoints assigned to different subsets.

Grafo bipartido: diferenças entre revisões