Taula de continguts:
Definició: què significa el gràfic bipartit?
Un gràfic bipartit és un gràfic en què es pot dividir un conjunt de vèrtexs gràfics en dos conjunts independents i no hi ha dos vèrtexs gràfics dins del mateix conjunt. És a dir, es poden considerar gràfics bipartits iguals a dos gràfics coloribles. Els gràfics del bipartit s'utilitzen principalment en les relacions de modelatge, especialment entre dues classes separades d'objectes.
Un gràfic bipartit també es coneix com a bigraph.
Techopedia explica el Bipartit Graph
Un gràfic bipartit té dos conjunts de vèrtexs, per exemple A i B, amb la possibilitat que quan es dibuixi un cantell, la connexió hauria de poder connectar-se entre qualsevol vèrtex de A a qualsevol vèrtex de B. Si el gràfic no conté cap cicle senar (el nombre de vèrtexs del gràfic és imparell), llavors el seu espectre és simètric. El nombre cromàtic, que és el nombre mínim de colors requerits per acolorir els vèrtexs sense vèrtexs adjacents que comparteixen els mateixos colors, ha de ser menor o igual a dos en el cas d'un gràfic bipartit. Tots els tipus de gràfics acíclics (gràfics que no tenen cicles gràfics) són exemples de gràfics bipartits. Un gràfic cíclic es considera bipartit si tots els cicles implicats són de longitud igual. Segons el teorema de coloració de línies de Koning, tots els gràfics bipartits són gràfics de classe 1.
Els gràfics bipartits s'utilitzen àmpliament en la teoria de codificació moderna, a part d'utilitzar-se en les relacions de modelatge.
