ГРАФ ДВУДОЛЬНЫЙ

ГРАФ ДВУДОЛЬНЫЙ, дихроматический граф, - граф, множество вершин к-рого V можно разбить на два непересекающихся подмножества V' и V'' (т. е. V = V' ∪ V'', V' ∩ V'' = ∅) так, что каждое ребро соединяет нек-рую вершину из V' с нек-рой вершиной из V''. Граф является Г. д. тогда и только тогда, когда все его простые циклы имеют четную длину. Под Г. д. часто понимают также граф, в к-ром заранее заданы подмножества вершин V' и V'' (доли). Г. д. удобны для представления бинарных отношений между элементами двух разных типов, напр.: взяв элементы данного множества и его подмножества, имеем отношение «вхождение элемента в подмножество»; для исполнителей и видов работ имеем отношение «данный исполнитель может выполнять данную работу» и т. д.

Среди задач о Г. д. важное место занимает изучение паросочетаний, т. е. семейств попарно несмежных ребер. Такие задачи возникают, напр., в теории расписаний (разбиение ребер Г. д. на минимальное число непересекающихся паросочетаний), в задаче о назначениях (нахождение максимального паросочетания) и т. д. Мощность максимального паросочетания в Г. д. равна

где V''(A') - число вершин из V'', смежных хотя бы с одной вершиной из A'. Полный Г. д.- это Г. д., в к-ром любые две вершины из различных подмножеств соединены ребром (напр., граф K_3,3, см. Граф плоский, рис. 1). Обобщением понятия «Г. д.» является понятие "k-дольного графа", т. е. графа, в к-ром вершины разбиты на к подмножеств так, что каждое ребро соединяет вершины из разных подмножеств.

Лит.: [1] Оре О., Теория графов, пер. с англ., М., 1968.

В. Б. Алексеев.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.