Разумевање бипартиција у теорији графова

У теорији графова, бипартиција графа је подела његовог скупа врхова на два дисјунктна скупа (названа партитни скупови) тако да све ивице повезују темене из различитих партитних скупова. Другим речима, не постоје ивице између врхова у истом партитном скупу.ӕӕНа пример, размотрите граф са 4 темена {а,б,ц,д} и делимо скуп врхова на два дела: {а,б} и {ц,д}. Граф је бипартитан јер све ивице повезују темене из различитих делова.ӕӕДводелна се може користити за смањење сложености алгоритама за проблеме графа као што су обилажење графом, проналажење најкраће путање и подударање графа.