Forståelse af bipartitioner i grafteori
I grafteori er en bipartition af en graf en opdeling af dens toppunktss
t i to usammenh
ngende s
t (kaldet partites
t), således at alle kanter forbinder toppunkter fra forskellige partites
t. Med andre ord er der ingen kanter mellem toppunkter i samme partits
t.
Betragt f.eks. en graf med 4 toppunkter {a,b,c,d} og vi deler toppunktet i to dele : {a,b} og {c,d}. Grafen er todelt, fordi alle kanter forbinder hjørner fra forskellige dele.
Bipartition kan bruges til at reducere kompleksiteten af algoritmer til grafproblemer såsom grafgennemgang, korteste vejsøgning og grafmatchning.
Jeg kan godt lide denne
Jeg kan ikke lide dette
Rapporter en indholdsfejl
Dele
