Inhoudsopgave:
Definitie - Wat betekent Bipartite Graph?
Een bipartiete grafiek is een grafiek waarin een reeks grafiekhoekpunten kan worden verdeeld in twee onafhankelijke sets, en geen twee grafiekhoekpunten binnen dezelfde reeks grenzen aan elkaar. Met andere woorden, tweepartiete grafieken kunnen worden beschouwd als gelijk aan twee kleurbare grafieken. Bipartiete grafieken worden meestal gebruikt in modelrelaties, vooral tussen twee volledige afzonderlijke klassen van objecten.
Een tweedelige grafiek wordt ook wel een bigraph genoemd.
Techopedia legt Bipartite Graph uit
Een tweedelige grafiek heeft twee sets hoekpunten, bijvoorbeeld A en B, met de mogelijkheid dat wanneer een rand wordt getekend, de verbinding tussen elk hoekpunt in A en een hoekpunt in B moet kunnen verbinden. Als de grafiek geen oneven cyclus (het aantal hoekpunten in de grafiek is oneven), dan is het spectrum symmetrisch. Het chromatische aantal, dat het minimum aantal kleuren is dat vereist is om de hoekpunten te kleuren zonder aangrenzende hoekpunten die dezelfde kleuren delen, moet kleiner zijn dan of gelijk zijn aan twee in het geval van een tweedelige grafiek. Alle soorten acyclische grafieken (grafieken zonder grafiekcycli) zijn voorbeelden van tweedelige grafieken. Een cyclische grafiek wordt als tweedelig beschouwd als alle betrokken cycli even lang zijn. Volgens de lijnkleurstelling van Koning zijn alle tweedelige grafieken klasse 1-grafieken.
Bipartiete grafieken worden veel gebruikt in de moderne coderingstheorie, behalve dat ze worden gebruikt in modelleringsrelaties.
