Я просто создаю алгоритм для обнаружения двудольных графов, но я думал о некотором графике, который я не уверен, считается двудольным, хотя мой алгоритм говорит, что это так.Обнаружение двудольного графа
График идет как
(A)--(B)
(C)
Таким образом, это имеет 3 узлов, но есть 1 ребро между только A и B. Действительно ли это двухсторонний?
Да, ваш примерный граф действительно двудольный.
См, например, Wikipedia article в котором говорится во вступительном предложении ...
В математической области теории графов, двудольный граф (или bigraph) представляет собой граф, вершины которого можно разделить на две непересекающиеся множества U и V такие, что каждое ребро соединяет вершину в U с одной в V; , т. Е. U и V являются отдельными независимыми множествами. Эквивалентно, двудольный граф представляет собой график, который не содержит циклов нечетной длины.
Есть два способа вы могли бы разделить этот график ("{A, C}, {B}" или "{B, C}, {A}"), который будет отвечать условиям, необходимым для двудольного графа ,
Для двудольного графа нет необходимости связывать граф.
Да, это так. Вы можете разделить узлы на два набора, чтобы все ребра проходили между двумя наборами. F'rinstance, {A} и {B, C}. – Beta
Таким образом, узел из одного набора фактически не должен подключаться к другому набору? – omega
Исправить. (И комментарий не может быть только восьми символов.) – Beta