Bipartit graf

Från Wikipedia
Hoppa till: navigering, sök
En bipartit graf partionerad i mängderna U och V.

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.

Egenskaper[redigera | redigera wikitext]

  • 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.

Exempel[redigera | redigera wikitext]

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ämpningar[redigera | redigera wikitext]

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

Generalisering[redigera | redigera wikitext]

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.