Бипартитивни граф, познат и као биграф или диграф је граф, у математичкој области теорије графова, чији се чворови могу поделити на два дисјунктивна скупа 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 назива бирегуларан граф.

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

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

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

Апстрактинији примери могу да буду:

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

Бипартитивни графови могу да буду окарактеризовани на неколико различитих начина:

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

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

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

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

За један чвор, степен је број грана који улазе и излазе из њега и означава се са 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 чворова са обе стране. У овом случају, бипартитивни граф је бипартитивна дупла представа усмереног графа.

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

Алтернативно овоме, слична процедура може да се примени са методом претрага у ширину уместо претраге у дубину. Опет, сваки чвор добија супротну боју од свог родитеља у стаблу претраге. Ако, када је неки чвор обојен, онда постоји и грана која га спаја са претходно обојеним чвором том бојом. Онда је та грана заједно са путањом у стаблу која настаје при примени алгоритма претраге у дубину која спаја та два краја са њиховим најнижим заједничким претком чини циклус непарне дужине. Ако се алгоритам заврши без проналаска циклуса непарне дужине на овај начин, онда је сигурно нашао исправно бојење, и сигурно може да се закључи да је овај граф бипартитиван.^[5]

За графове са убацивањем n-те дужи или неког другог облика у Еуклидовој равни, могуће је да се тестира да ли је граф бипартитиван и вратити или две боје или циклус непарне дужине у${\displaystyle O(n\log n)}$, времену, иако граф сам по себи има до ${\displaystyle \Omega (n^{2})}$ грана.

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

Име пролаз кроз циклусе непарне дужине долази од чињенице да је граф бипартитиван ако и само ако нема циклусе непарне дужине. Дакле, да би се обрисали чворови из графа како би се добио бипартитивни граф, морамо уклонити све такве циклусе и да нађемо одређене скупове. У илустрацији, може се увидети да је сваки циклус непарне дужине у графу садржи плави (најнижи) чвор, тако да уклањање тих чворова уклања све поменуте циклусе и оставља бипартитивни граф.

Проблем бипартизације грана је алгоритамски проблем брисања што мање грана је могуће да би настао бипартитивни граф и врло је битан пробелм у алгоритмици модификације графова. Овај проблем има сложеност од O(2k m2), где је к број грана које треба да се обришу и m је број грана у улазном графу.

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

Као једноставан пример, претпоставимо да постоји скуп П људи где сви људи траже послове међу скупом Ј који предстваља послове, тако да нису сви људи одговарајући за све послове. Ова ситуација може да се моделује као бипартитиван граф (П, J, E) где гране спајају сваког кандидата са одговарајућим послом. Савршено поклапање описује начин да се симултано задовоље сви људи које траже посао као и да су сви послови попуњени; Халова теорема брака даје карактеризацију бипартитивног графа који дозвољава савршено поклапање. Национални програм за поклапање се односи на методе поклапања да се реше сви проблеми за САД-ове студенте медицине и послове за стажисте по болницама.^[6]

Далмеџ-Менделсон декомпозиција је структурална декомпозиција бипартитивних графова који су корисни у налажењу максималних поклапања. ^[7]

Бипартитивни графови се врло користе у модерној теорији кодовања, нарочито за декодовање шифри које се примају преко канала. Фактор графови и Танерови графови су примери овога. Танеров граф је бипартитиван граф у којем су чворови са једне стране бипартиције представљени цифрама из шифре, а чворови са друге стране су представљени комбинацијама цифри за које се претпоставља да је сума од нуле у самој шифри. Фактор граф је уско повезан са методама за пробалистичко декодовањем турнокода и ЛДПЦ. ^[8]

У информатици, Петри мрежа је оруђе за математичко моделовање које се користи за анализу и симулацију конкурентних система. Систем је моделован као бипартитиван граф са два скупа чворова: скуп са „место“ чворовима који садрже ресурсе, и скуп „догађаја“ чворова који генеришу и/или ресурс за конзумацију. Постоје и додатне границе за чворове и гране које ограничавају понашање система. Петри мреже користе особине бипартитивних усмерених графова да би дозволили математичке доказе понашања система док такође дозвољавају лаку имплементацију симулација система. ^[9]

У пројективној геометрији, Ливај графови су облик бипартитивних графова који се користи да се моделују инциденције између тачака и линија у конфигурацији. Ливај графови не морају да садрже циклусе дужине четири, тако да је дужина најкраћег циклуса већа од 6, а то одговара геометријском правилу тачака и права које каже да се две праве секу у највише једној тачки и да се једна права може повући из најмање две тачке. ^[10]

• Бипартитне димензије, минимални број комплетних бипартитивних графова чија је унија задати граф
• Мултипартитни граф је генерализација бипартитивног графа до више од два подскупа чворова

• Grünbaum, Branko (2009). Configurations of Points and Lines. American Mathematical Soc. стр. 28. ISBN 978-0-8218-8414-0. 
• Cassandras, Christos G.; Lafortune, Stéphane (2009). Introduction to Discrete Event Systems. Springer Science & Business Media. стр. 224. ISBN 978-0-387-33332-8. 
• Wasserman, Stanley; Faust, Katherine (25. 11. 1994). Social Network Analysis: Methods and Applications. Cambridge University Press. стр. 299. ISBN 978-0-521-38707-1. 

Бипартитивни граф на Викимедијиној остави.