Visa källa för Bipartit graf

[[Fil:Simple-bipartite-graph.svg|höger|miniatyr|200px|En bipartit graf partionerad i mängderna ''U'' och ''V''.]]
En '''bipartit graf''', även kallad tvådelad graf, är en [[Graf (grafteori)|graf]] vars hörnmängd <math>V(G)</math> kan [[partition av en mängd|partitioneras]] som <math>V(G) = X \cup Y</math> där <math>X \cap Y = \emptyset</math> och där varje kant <math>e \in E(G)</math> kan skrivas på formen <math>e = \{x, y\}</math>, där <math>x \in X</math> och <math>y \in Y</math>. I så fall säges <math>G</math> 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 [[cykel (grafteori)|cykler]] av udda längd.
*För bipartita grafer med icke-tomma kantmängder gäller att <math>\chi = 2</math>, där <math>\chi</math> är det [[kromatiskt_tal|kromatiska talet]].
*Varje bipartit graf är en [[perfekt graf]].

==Exempel==
[[Fil:Graph K3-3.svg|höger|miniatyr|Den [[komplett bipartit graf|kompletta bipartita]] grafen <math>K_{3,3}</math>.]]
Varje graf som inte har någon cykel av udda längd är bipartit. Exempel på grafer som uppfyller detta är [[träd_(graf)|träd]] och [[cyklisk graf|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 (grafteori)|graf]] vars hörnmängd kan partitioneras som <math>V(G) = \bigcup _{k=0} ^{n-1} V_k</math>, och där varje kant <math>e \in E(G)</math> kan skrivas på formen <math>e = \{x, y\}</math>, där <math>x \in V_i</math>, <math>y \in V_j</math> och <math>i \neq j</math>. En graf har kromatiskt tal ''k'', om och endast om den är ''k''-partit men inte (''k''-1)-partit.

[[Kategori:Grafteori]]
[[Kategori:Paritet]]