Разбиране на двойните дялове в теорията на графите

В теорията на графите двуразделната част на граф е разделяне на неговия набор от върхове на две несвързани множества (наречени частични множества), така че всички ребра свързват върхове от различни разделителни множества. С други думи, няма ръбове между върховете в едно и също множество от части.

Например, разгледайте графика с 4 върха {a,b,c,d} и разделяме набора от върхове на две части: {a,b} и {c,d}. Графът е двустранен, тъй като всички ръбове свързват върхове от различни части.

Двустранният дял може да се използва за намаляване на сложността на алгоритмите за проблеми с графики, като обхождане на графика, намиране на най-краткия път и съвпадение на графика.