Оглавление:
Определение - Что означает двудольный график?
Двудольный граф - это граф, в котором набор вершин графа может быть разделен на два независимых набора, и никакие две вершины графа в одном и том же наборе не являются смежными. Другими словами, двудольные графы можно рассматривать как равные двум раскрашиваемым графам. Двудольные графы в основном используются при моделировании отношений, особенно между двумя целыми отдельными классами объектов.
Двудольный граф также известен как биграф.
Техопедия объясняет двудольный граф
Двухсторонний граф имеет два набора вершин, например, A и B, с возможностью того, что при прорисовке ребра соединение должно иметь возможность соединить любую вершину в A с любой вершиной в B. Если граф не содержит каких-либо нечетный цикл (число вершин в графе нечетное), то его спектр симметричен. Хроматическое число, которое представляет собой минимальное количество цветов, необходимое для окраски вершин без смежных вершин, имеющих одинаковые цвета, должно быть меньше или равно двум в случае двудольного графа. Все типы ациклических графов (графы, у которых нет циклов графов), являются примерами двудольных графов. Циклический граф считается двудольным, если все задействованные циклы имеют четную длину. Согласно теореме о раскраске линий Конинга все двудольные графы являются графами класса 1.
Двудольные графы широко используются в современной теории кодирования, кроме того, что используются в моделировании отношений.
