Grafo bipartido: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 26:
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<sub>x</sub>'' é adequada para um determinado trabalho ''j<sub>y</sub>'' existe uma aresta entre ''p<sub>x</sub>'' e ''j<sub>y</sub>'' no grafo. O [[teorema do casamento]] fornece uma caracterização de grafos bipartidos que permitem [[Acoplamento (teoria dos grafos)|acoplamentos perfeitos]].
Grafos bipartidos são usados extensivamente na moderna [[teoria dos códigos]], especialmente para decodificar [[palavra de código|palavras de código]] recebidas do canal. [[grafo Fator|grafos Fator]] e [[grafo Tanner|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.
▲<!--
In computer science, a [[Petri net]] is a mathematical modelling tool used in analysis and simulations of concurrent systems. A system is modelled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.
| |||