Grafo bipartido: diferenças entre revisões

[[Image:Simple-bipartite-graph.svg|200px|thumb|Exemplo de um grafo bipartido]]

 

 

Os dois conjuntos ''U'' e ''V'' podem ser pensados como uma [[coloração de grafos|coloração]] do grafo com duas cores: se nós colorimos todos os nodos em ''U'' de azul, e todos os nodos em ''V'' de verde, cada aresta tem terminações de cores diferentes, como é exigido no problema de coloração de grafos. Em contrapartida, tal coloração é impossível no caso de um grafo que não é bipartido, como um [[Galeria de grafos nomeados|triângulo]]: depois de um nó ser colorido de cor azul e outro de verde, o terceiro vértice do triângulo é ligado a vértices de ambas as cores, impedindo que seja atribuída qualquer cor.

Frequentemente se escreve ''G'' = (''U'', ''V'', ''E'') para denotar um grafo bipartido cuja partição tem as partes ''U'' e ''V''. Se |''U''| =|''V''|, ou seja, se os dois subconjuntos tem igual [[cardinalidade]], então ''G'' é chamado um grafo bipartido ''balanceado''.

 

* Qualquer grafo sem ciclos ímpares é bipartido. Como consequência disso:

** Toda [[árvore (grafo)|árvore]] é bipartida.

** 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.

 

[[Ficheiro:RecursiveEvenBipartite.svg|thumb|Encontrando uma bipartição usando 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''.

Assim, pode-se testar eficientemente se um grafo é bipartido, usando esta técnica de paridade de se atribuir vértices para os dois subconjuntos ''U'' e ''V'', separadamente a cada componente conectado do grafo e, em seguida, examinar cada aresta para verificar se ela tem terminações designadas para os diferentes subgrupos.

 

Grafos bipartidos são úteis para a modelagem de problemas de [[Acoplamento (teoria dos grafos)|acoplamento]]. Um exemplo de grafo bipartido é um problema de correspondência de empregos. Suponha que temos um conjunto ''P'' de pessoas e um conjunto ''J'' de postos de trabalho, com nem todas as pessoas adequadas para todos os trabalhos. Podemos modelar isto como um grafo bipartido (''P'', ''J'', ''E''). Se uma pessoa ''p_x'' é adequada para um determinado trabalho ''j_y'' existe uma aresta entre ''p_x'' e ''j_y'' no grafo. O [[teorema do casamento]] fornece uma caracterização de grafos bipartidos que permitem [[Acoplamento (teoria dos grafos)|acoplamentos perfeitos]].

 

Em ciência da computação, uma [[rede de Petri]] é uma ferramenta de modelagem matemática utilizada na análise e simulação de sistemas concorrentes. Um sistema é modelado como um grafo bipartido dirigido com dois conjuntos de nós: Um conjunto de nodos "lugar" que contêm recursos, e um conjunto de nodos "evento" que geram e/ou consomem recursos. Existem restrições adicionais sobre os nós e arestas que condicionam o comportamento do sistema. Redes de Petri utilizam as propriedades de grafos bipartidos dirigidos e outras propriedades para permitir provas matemáticas do comportamento dos sistemas enquanto ao mesmo tempo, permitindo a fácil implementação de simulações do sistema.

 

 

Grafos bipartidos podem modelar inteiramente o mais geral [[multigrafo]]. Dada um multigrafo M, tome U como o conjunto de vértices de M e tome V como o conjunto de arestas de M. Então junte-se um elemento de V para precisamente os dois elementos de U que são as extremidades da aresta em M. Assim, cada multigrafo é descrito completamente por um grafo bipartido, que é unilateral regular de grau 2, e vice-versa.

 

Da mesma forma, cada [[hipergrafo]] direcionado pode ser representado por um grafo bipartido. Tome U como o conjunto de vértices no hipergrafo, e V como conjunto de arestas. para cada <math>u\in U</math> e <math>v \in V</math>, conecte u a v se a aresta do hipergrafo contém u como entrada, e conecte v a u se v contém u como saída.

 

* 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 [[teoria dos grafos espectrais|espectro]] de um grafo é simétrico se e somente se ele é um grafo bipartido.

 

* [[Grafo bipartido completo]]

 

{{Referências}}

 

[[Categoria:Famílias de grafos]]