mobile theme mode icon
theme mode light icon theme mode dark icon
Random Question Tilfeldig
speech play
speech pause
speech stop

Forstå bipartisjoner i grafteori

I grafteori er en bipartisjon av en graf en deling av toppunktsettet i to usammenhengende sett (kalt delsett) slik at alle kanter forbinder toppunkter fra forskjellige delsett. Det er med andre ord ingen kanter mellom toppunktene i samme partittsett.

Tenk for eksempel en graf med 4 toppunkter {a,b,c,d} og vi deler toppunktsettet i to deler : {a,b} og {c,d}. Grafen er todelt fordi alle kanter forbinder hjørner fra forskjellige deler.

Bipartisjon kan brukes til å redusere kompleksiteten til algoritmer for grafproblemer som grafovergang, korteste veifunn og graftilpasning.

Knowway.org bruker informasjonskapsler for å gi deg en bedre service. Ved å bruke Knowway.org godtar du vår bruk av informasjonskapsler. For detaljert informasjon kan du lese teksten vår i retningslinjer for informasjonskapsler. close-policy