Indholdsfortegnelse:
Definition - Hvad betyder bipartitgraf?
En topartsgrafik er en graf, hvor et sæt grafhøjder kan opdeles i to uafhængige sæt, og ingen to grafhøjder i det samme sæt er tilstødende. Med andre ord kan bipartitgrafer betragtes som lig med to farvelagte grafer. Bipartit-grafer bruges for det meste i modelleringsrelationer, især mellem to hele separate klasser af objekt.
En bipartit graf er også kendt som en bigraph.
Techopedia forklarer bipartitgrafik
En bipartit-graf har to sæt vertikater, for eksempel A og B, med muligheden for, at når en kant tegnes, skal forbindelsen være i stand til at forbinde et hvilket som helst toppunkt i A til ethvert toppunkt i B. Hvis grafen ikke indeholder nogen ulige cyklus (antallet af vertikater i grafen er ulige), så er dens spektrum symmetrisk. Det kromatiske antal, som er det mindste antal farver, der kræves for at farve verticerne uden nogen tilstødende hjørner, der deler de samme farver, skal være mindre end eller lig med to i tilfælde af en bipartit-graf. Alle typer acykliske grafer (grafer, der ikke har nogen grafcyklus), er eksempler på bipartitgrafer. En cyklisk graf betragtes som bipartit, hvis alle de involverede cyklusser har jævn længde. I henhold til Konings linjefarve sætning er alle bipartit grafer klasse 1 grafer.
Bipartitgrafer er vidt brugt i moderne kodningsteori bortset fra at blive brugt i modelleringsrelationer.
