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 V(G) kan partitioneras som V(G) = X \cup Y där X \cap Y = \emptyset och där varje kant e \in E(G) kan skrivas på formen e = \{x, y\}, där x \in X och y \in Y. I så fall säges 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[redigera | redigera wikitext]

Exempel[redigera | redigera wikitext]

Den kompletta bipartita grafen K_{3,3}.

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 V(G) = \bigcup _{k=0} ^{n-1} V_k, och där varje kant e \in E(G) kan skrivas på formen e = \{x, y\}, där x \in V_i, y \in V_j och i \neq j. En graf har kromatiskt tal k, om och endast om den är k-partit men inte (k-1)-partit.