Бипартитивни граф — разлика између измена

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

 

 

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