Граф двудольный

бихроматический граф, - граф, множество вершин к-рого [img: http://localhost:8080/file/010428-248.jpg] можно разбить на два непересекающихся подмножества [img: http://localhost:8080/file/010428-249.jpg] и, [img: http://localhost:8080/file/010428-250.jpg] (т.) так, что каждое ребро соединяет нек-рую вершину из [img: http://localhost:8080/file/010428-252.jpg] с нек-рой вершиной из [img: http://localhost:8080/file/010428-253.jpg]. Граф является Г. д. тогда и только тогда, когда все его простые циклы имеют четную длину. Под Г. д. часто понимают также граф, в к-ром заранее заданы подмножества вершин [img: http://localhost:8080/file/010428-254.jpg] и [img: http://localhost:8080/file/010428-255.jpg] (доли). Г. д. удобны для представления бинарных отношений между элементами двух разных типов, напр.: взяв элементы данного множества и его подмножества, имеем отношение "вхождение элемента в подмножество"; для исполнителей и видов работ имеем отношение "данный исполнитель может выполнять данную работу" и т. д. Среди задач о Г. д. важное место занимает изучение паросочетаний, т. е. семейств попарно несмежных ребер. Такие задачи возникают, напр., в теории расписаний (разбиение ребер Г. д. на минимальное число непересекающихся паросочетаний), в задаче оназначениях(нахождениемаксимального паросочетания) и т. д. Мощность максимального паросочетания в Г. д. равна [img: http://localhost:8080/file/010428-256.jpg] где [img: http://localhost:8080/file/010428-257.jpg] - число вершин из [img: http://localhost:8080/file/010428-258.jpg], смежных хотя бы с одной вершиной из [img: http://localhost:8080/file/010428-259.jpg]. Полный Г. д.- это Г. д., в к-ром любые две вершины из различных подмножеств соединены ребром (напр., граф [img: http://localhost:8080/file/010428-260.jpg] см. Граф плоский, рис. 1). Обобщением понятия "Г. д." является понятие "k-дольногографа", т. е. графа, в к-ром вершины разбиты на kподмножеств так, что каждое ребро соединяет вершины из разных подмножеств.