мини|Пример бипартитног графа без циклуса мини|Комплетан бипартитни граф са m = 5 и n = 3

Бипартитни граф, познат и као биграф или диграф је граф, у математичкој области теорије графова, чији се чворови могу поделити на два дисјунктивна скупа U и V (тако да се U и V могу представити као скупови које се обележавају као независан скуп) тако да свака грана (ивица) спаја чвор из U и један чвор из V. Скупови чворова U и V се често и називају партитивни скупови. Еквивалентно томе, бипартитан граф је граф који не садржи ниједан циклус непарне дужине.

Два скупа U и V могу да се представе помоћу бојења графа са две боје: тако да једна боја означава све чворове из U и плава је, а сви чворови из V су представљени зеленом бојом. Тако свака грана има завршетке са различитом бојом, као што је и представљено у проблему бојења графа. Ова метода није могућа и нема смисла да се употреби за небипартитне графове, као на пример троугао: пошто је један чвор обојен у плаво, а други у зелено, немогуће је одредити боју за трећи чвор јер у њега улазе две гране које почињу са две различите боје.

Често се користи и ознака G = (U, V, E) да се означи бипартитни граф који има два дисјунктна скупа чворова U и V, и Е који означава гране графа. Ако бипартитан граф није повезан, онда може да има више од једног пара дисјунктних скупова. У том слулају, ова нотација (G = (U, V, E)) је врло од помоћи при навођењу конкретног пара скупова који може да буде од користи. Ако |U| = |V| (број чворова у U је једнак броју чворова у V, U и V имају исту кардиналност), онда се G назива и балансиран бипартитан граф. Ако су сви чворови са исте стране имају исти степен, онда се G назива бирегуларан граф.

Примери Када се моделују релације између две различите класе објеката, бипартитни графови су често корисни и њихова примена је природна. На пример, граф фудбалера и клубова, са граном између фудбалера и клуба која означава да је фудбалер играо за тај клуб, је природан пример афилационе мреже, која је тип бипартитног графа који се користи у анализи друштвених веза.

Још један пример овог типа графа који се такође природно намеће је у пробелему оптимизације пруге (спада у област НП-комплетни проблеми), у којем је улаз распоред возова и њихових станица, а циљ је да се пронађе скуп возова да буде што мањи је могуће тако да сваки воз посети макар једну од изабраих станица. Овај проблем може да се моделује као доминантни скуп у бипартитном графу који има чвор за сваки воз и сваку станицу и грану за сваку станицу на којој се воз зауставља.

Трећи пример је у академској области нумизматици. Антички новчићи се праве помоћу два позитивна отиска (предња и задња страна). Графови који нумизматичари користе да би представили производњу новчића су бипартитни графови.

Апстрактинији примери могу да буду:  Свако стабло је бипартитан граф   Графови са циклусом са парним бројем чворова су бипартитни графови  Сви планарни графови чија лица имају исте дужине су бипартитни графови. Специјални случајеви овога су графови са мрежом у којима се свако унутрашње лице садржи од 4 гране, а сваки унутрашњи чвор има 4 или више суседа.   Комплетан бипартитан граф са m и n чворова, представљен као Kn,m је бипартитан граф G=(U, V, E), где су U, V дисјунктни скупови величина m, n, и Е који спаја сваки чвор из U са свим чворевима из V. Следи да је Кn,m има n*m грана. Блиско повезани са комплетним бипартитним графовима су круна графови, који се формирају од комплетних бипартитних графова тако што се уклањају гране савршеног поклапања.   Суперкоцка графови, парцијалне коцке и медијански графови су бипартитни. У овим графовима, чворови, чворови могу да се обележе као битвектори, у смислу да су два чвора прођена ако и само ако су одговарајући битвектори различити за једну позицију. Скуп два дисјкунтна скупа може да се формира одвајањем чворова чији битвектори имају паран број чворова од оних кој имају непаран. Стабла и коцкаграфови креирају медијанске графове, а сваки медијански граф је парцијална коцка. 

Особине

Карактеризација Бипартитни графови могу да буду окарактеризовани на неколико различитих начина:  Граф је бипартитан ако и само ако не садржи циклусе непарне дужине   Граф је бипартитан ако и само ако је бојив са само две боје  Спектар графа је симетричан ако и само ако је граф бипартитан.

Конигова теорема и савршени графови У бипартитним графовима, величина коју има покривач чворова је једнака величини максималних поклапања; то је Конигова теорема. Алтернативна и еквивалентна теорема је да је величина максимума независног скупа плус величина максималних поклапања једнака броју чворова. У било ком графу без изоловања чворова величине минималног распона гране плус величине максимума поклапања је једнак броју чворова. Ако комбинујемо ову јендакост са Кониговом теоремом следи чињеница да у бипартитним графовима, величина минималног распона гране једнака величини максимума независног скупа, и да је величина минималног распона гране плус величина минималног распона чвора једнака броју чворова.

Још једна класа повезаних разултата се тиче савршених графова: сваки бипартитни граф, комплемент сваког бипартитног графа, линијски граф бипартитног графа су савршени. Савршенство бипартитних графова је врло једноставно да се увиди (може да се обоји са две боје, тј. њихов хроматски број је 2) али савршенство комплемента бипартитног графа је мање тривијално и још једна је примена Конигове теореме. Ово је један од разултата који су мотивисали увођење појма савршеног графа. Исто важи и за комплементе линијског графа савршеног графа и савршенство комплемената линијских графова који се такође могу објаснити преко ове теореме тј. да сваки бипартитни граф има боју гране коју је добила помоћу боја једнаким његовом максималном степену.

Према још једној теореми која описује савршене графове, савршени графови имају забрањену карактеризацију графа која подсећа на бипартитан граф: граф је бипартитан ако и само ако нема непаран циклус као подграф, и граф је савршен ако и само ако нема непаран циклус или његов комплемент као индукован подграф. Бипартитни графови, линијски графови бипартитних графова и њигови комплементи граде четири од пет основних класа савршених графова који се користе да би се доказала горенаведена теорема.

Степен За један чвор, степен је број грана који улазе и излазе из њега и означава се са deg(V). Сума степена за бипартитне графове је:

Низ степени бипартитног графа је пар листи где свака садржи степене два дисјунктна скупа. На пример бипартитни граф К3,5 има низ степени (5, 5, 5), (3, 3, 3, 3, 3). Изоморфни бипартитни граф има исти низ степени. Али низ степени не мора у општем случају да јединствено описује бипартитни граф; у неким случајевима, неизоморфни бипартитни графови такође могу да имају тај низ степени.

Пробелем реализације бипартиције је проблем налажења једноставног бипартитног графа са низом степена представљен као две листе природних бројева. (Пратеће нуле могу да се игноришу јер су тривијално реализоване додавањем одговарајућег броја изолованих чворова диграфу.)

Веза са хиперграфовима и усмереним графовима Матрица повезаности бипартитног графа (U, V, E) је (0,1)-матрица величине |U| X |V| који има један за сваки пар повезаних чворова и нулу за несуседне чворове. Матрица повезаности може да се користи и да би се описала еквиваленција између бипартитних графова, хиперграфова и усмерених графова.

Хиперграф је комбинаторијална структура таква да, као и неусмерени граф, има чворове и гране, али у којима гране могу да буту произвољни скупови чворова и грана које имају идентичне крајеве. Бипартитни граф (U, V, E) може да се користи да би се моделовао хиперграф у којем је U скуп чворова хиперграфа, V је скуп хиперграна, и Е садржи гране од чвора хиперграфа до гране хиперграфа. Ако ово узмемо у обзир, матрица повезаности бипартитног графа је баш инцидентна матрица одговарајућих хиперграфова. Као специјалан случај овог одговарајања између бипартитних графова и хиперграфова, било који мултиграф (граф у којем постоји две или више гране између два иста чвора) може да буде интерпретиран као хиперграф у којем неке хипергране имају исте крајеве, и представљене су помоћу бипартитног графа који нема вишеструке повезаности и у којем су чворови на једној страни степена два.

Слична интерпратација матрица повезаности може да се користи да би се показала 1-1 одговарање између усмерених графова и балансираних бипартитних графова, који имају исти број чворова са обе стране пара дискунктних скупова. За матрицу повезаности усмереног греафа са n чворова може да буде (0,1)-матрица величине nXn, која се онда може интерпретирати као матрица повезаности бипартитног графа са n чворова са обе стране. У овом случају, бипартитни граф је бипартитна дупла представа усмереног графа.

Алгоритми

Тестирање бипартиција Могуће је тестирати и проверити да ли је граф бипартитан, и вратити две боје (ако је граф бипартитан) или циклус непарне дужине (ако није) у времену које се означава као субекспоненцијално време, помоћу алгоритма претрага у дубину. Главна идеја да се сваком чвору дода боја која се разликује од боје родитеља у дрвету које настаје при примени претраге у дубину. Последица тога је разапињуће стабло са две боје чворова које се састоји од грана које спајају чворове до својих родитеља, али можда неће исправно обојити гране које нису грана стабла. У стаблу које је генерисано претрагом у дубину, један од два краја сваке гране која није грана стабла је предак овог другог краја и када дфс претрага открије грану која овог типа треба да провери да ли ово два чвора имају различите боје. Ако немају, онда је путања у стаблу од претка до детета, заједно са граном која је погрешно обојена циклус непарне дужине, који је враћен из алгоритма заједно са резултетом да граф није бипартитан. Ипак, ако алгоритам заврши рад без детектовања циклуса непарне дужине овог типа, онда је свака грана правилно обојена и алгоритам враћа боје заједно са резултатом да је граф заиста бипартитан.

Алтернативно овоме, слична процедура може да се примени са методом претрага у ширину уместо претраге у дубину. Опет, сваки чвор добија супротну боју од свог родитеља у стаблу претраге. Ако, када је неки чвор обојен, онда постоји и грана која га спаја са претходно обојеним чвором том бојом. Онда је та грана заједно са путањом у стаблу која настаје при примени алгоритма претраге у дубину која спаја та два краја са њиховим најнижим заједничким претком чини циклус непарне дужине. Ако се алгоритам заврши без проналаска циклуса непарне дужине на овај начин, онда је сигурно нашао исправно бојење, и сигурно може да се закључи да је овај граф бипартитан.Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, Addison Wesley. стр. 94–97.

За графове са убацивањем n-те дужи или неког другог облика у Еуклидовој равни, могуће је да се тестира да ли је граф бипартитан и вратити или две боје или циклус непарне дужине у, времену, иако граф сам по себи има до грана.

Пролаз кроз циклусе непарне дужине мини|Граф са пролазом кроз циклусе непарне дужине величине 2: уклањањем два плава чвора настаје бипартитни граф Пролаз кроз циклусе непарне дужине спада у скуп проблема који се зову НП-комплетни проблеми који тражи, да уз дати граф G= (V, E) и број К, у зависности да ли постоји скуп К чворова чије би одстрањивање од G проузроковало резултујући граф да буде бипартитан. Проблем је такав да постоји алгоритам чија се брзина трајања може ограничити у полиномијалном времену, неком функцијом величине графа помножене неком већом функцијом од К. Конкретније, време које је потребно да се извши је O(3k mn), иако ово није наведено у том чланку. Резултат по Риду је откривен помоћу потупно нове методе, која је касније названа итеративна компресија и испоставило се да је она врло корисна у раду са алгоритмима. Ово оруђе се данас смара једним од основних и најпотребнијих оруђа у раду са параметризованим алгоритмима.