En bipartit graf, även kallad tvådelad graf, är en graf vars hörnmängd kan partitioneras som där och där varje kant kan skrivas på formen , där och . I så fall säges ha bipartitionen (X,Y). Detta kan även uttryckas så att noderna i en bipartit graf kan indelas i två mängder, sådana att inga kanter går mellan två noder i samma mängd.

En bipartit graf partionerad i mängderna U och V.

EgenskaperRedigera

  • En graf är bipartit om och endast om den inte har några cykler av udda längd.
  • För bipartita grafer med icke-tomma kantmängder gäller att  , där   är det kromatiska talet.
  • Varje bipartit graf är en perfekt graf.

ExempelRedigera

 
Den kompletta bipartita grafen  .

Varje graf som inte har någon cykel av udda längd är bipartit. Exempel på grafer som uppfyller detta är träd och cykliska grafer med ett jämnt antal bågar.

TillämpningarRedigera

Bipartita grafer har tillämpningar till områden utanför matematiken, till exempel inom schemaläggning.

GeneraliseringRedigera

En k-partit graf är en graf vars hörnmängd kan partitioneras som  , och där varje kant   kan skrivas på formen  , där  ,   och  . En graf har kromatiskt tal k, om och endast om den är k-partit men inte (k-1)-partit.