Innehållsförteckning:
Definition - Vad betyder Bipartite Graph?
En tvåpartsgraf är en graf i vilken en uppsättning grafhörn kan delas upp i två oberoende uppsättningar, och inga två grafhörn i samma uppsättning är intill varandra. Med andra ord kan bipartitgrafer betraktas som lika med två färgglada grafer. Bipartitgrafer används mest i modelleringsrelationer, särskilt mellan två hela separata klasser av objekt.
En tvåpartsgrafik kallas också en bigraph.
Techopedia förklarar bipartitgrafik
En tvåpartsgrafik har två uppsättningar av vertikaler, till exempel A och B, med möjligheten att när en kant dras, ska anslutningen kunna ansluta mellan valfri topp i A till någon topp i B. Om diagrammet inte innehåller någon udda cykel (antalet vertikaler i diagrammet är udda), då är dess spektrum symmetriskt. Det kromatiska antalet, som är det minsta antalet färger som krävs för att färga topparna utan angränsande vertikaler som delar samma färger, måste vara mindre än eller lika med två i fallet med en tvåpartsgraf. Alla typer av acykliska grafer (diagram som inte har några diagramcykler) är exempel på bipartitgrafer. Ett cykliskt diagram betraktas som bipartit om alla involverade cykler har jämn längd. Enligt Konings radfärgssats är alla bipartitgrafer klass 1-grafer.
Bipartitgrafer används ofta i modern kodningsteori förutom att de används i modelleringsrelationer.
