Bipartit graf

En bipartit graf, även kallad tvådelad graf, är en graf vars hörnmängd ${\displaystyle V(G)}$ kan partitioneras som ${\displaystyle V(G)=X\cup Y}$ där ${\displaystyle X\cap Y=\emptyset }$ och där varje kant ${\displaystyle e\in E(G)}$ kan skrivas på formen ${\displaystyle e=\{x,y\}}$, där ${\displaystyle x\in X}$ och ${\displaystyle y\in Y}$. I så fall säges ${\displaystyle G}$ 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

• 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 ${\displaystyle \chi =2}$, där ${\displaystyle \chi }$ är det kromatiska talet.
• Varje bipartit graf är en perfekt graf.

Exempel

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

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

Generalisering

En k-partit graf är en graf vars hörnmängd kan partitioneras som ${\displaystyle V(G)=\bigcup _{k=0}^{n-1}V_{k}}$, och där varje kant ${\displaystyle e\in E(G)}$ kan skrivas på formen ${\displaystyle e=\{x,y\}}$, där ${\displaystyle x\in V_{i}}$, ${\displaystyle y\in V_{j}}$ och ${\displaystyle i\neq j}$. En graf har kromatiskt tal k, om och endast om den är k-partit men inte (k-1)-partit.