Grafo bipartido

No campo da matemática da teoria dos grafos, um grafo bipartido ou bigrafo é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um vértice em V; ou seja, U e V são conjuntos independentes. Equivalentemente, um grafo bipartido é um grafo que não contém qualquer ciclo de comprimento ímpar.

Exemplo de um grafo bipartido

Os dois conjuntos U e V podem ser pensados como uma coloração do grafo com duas cores: se nós colorirmos 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 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.

Exemplos

• Qualquer grafo sem ciclos ímpares é bipartido. Como consequência disso:
  • Toda árvore é bipartida.
  • 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 grafos grelha e grafos quadrado, em que cada face interna é composta por 4 arestas.

Testando biparticidade

Encontrando uma bipartição usando paridade

Se um grafo bipartido é conexo, a sua bipartição pode ser definida pela 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.

Aplicações

Grafos bipartidos são úteis para a modelagem de problemas de 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 acoplamentos perfeitos.

Grafos bipartidos são usados extensivamente na moderna teoria dos códigos, especialmente para decodificar palavras de código recebidas do canal. Grafos Fator e grafos Tanner são exemplos disso.

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.

Em geometria projetiva, grafos de Levi são uma forma de grafo bipartido usada para modelar as incidências entre os pontos e linhas em uma configuração.

Modelagem de multigrafos e hipergrafos

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 $u\in U$ e $v\in V$, 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.

Propriedades

• Um grafo é bipartido se e somente se ele não contém um ciclo ímpar. Portanto, um grafo bipartido não pode conter um clique de tamanho ímpar.
• 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 mínima é igual ao tamanho do acoplamento máximo (teorema de König).
• O tamanho do conjunto independente máximo mais o tamanho do acoplamento máximo é igual ao número de vértices.
• Para um grafo bipartido conectado o tamanho da 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 espectro de um grafo é simétrico se e somente se ele é um grafo bipartido.

Ver também

• Grafo bipartido completo

Ligações externas

• «Sistema de informações sobre inclusões de classes de grafos». : grafo bipartido