- ГРАФ ДВУДОЛЬНЫЙ
бихроматический граф, - граф, множество вершин к-рого
можно разбить на два непересекающихся подмножества 
и ,
(т. <е.
) так, что каждое ребро соединяет нек-рую вершину из 
с нек-рой вершиной из 
. Граф является Г. д. тогда и только тогда, когда все его простые циклы имеют четную длину. Под Г. д. часто понимают также граф, в к-ром заранее заданы подмножества вершин 
и 
(доли). Г. д. удобны для представления бинарных отношений между элементами двух разных типов, напр.: взяв элементы данного множества и его подмножества, имеем отношение "вхождение элемента в подмножество"; для исполнителей и видов работ имеем отношение "данный исполнитель может выполнять данную работу" и т. д.
Среди задач о Г. д. важное место занимает изучение паросочетаний, т. е. семейств попарно несмежных ребер. Такие задачи возникают, напр., в теории расписаний (разбиение ребер Г. д. на минимальное число непересекающихся паросочетаний), в задаче оназначениях(нахождениемаксимального паросочетания) и т. д. Мощность максимального паросочетания в Г. д. равна
где
- число вершин из 
, смежных хотя бы с одной вершиной из 
. Полный Г. д.- это Г. д., в к-ром любые две вершины из различных подмножеств соединены ребром (напр., граф 
см. Граф плоский, рис. 1). Обобщением понятия "Г. д." является понятие "k-дольногографа", т. е. графа, в к-ром вершины разбиты на kподмножеств так, что каждое ребро соединяет вершины из разных подмножеств. Лит.:[1] Оре О., Теория графов, пер. с англ., М., 1968.
В. Б. Алексеев.
Математическая энциклопедия. — М.: Советская энциклопедия. И. М. Виноградов. 1977—1985.
Смотреть что такое "ГРАФ ДВУДОЛЬНЫЙ" в других словарях:
ГРАФ ПЛОСКИЙ — планарный граф, граф, допускающий правильную укладку на плоскости (см. Графа укладка). Иными словами, граф G наз. плоским, если он может быть изображен на плоскости так, что вершинам соответствуют различные точки плоскости, а линии,… … Математическая энциклопедия
двудольный граф — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN bipartite graph … Справочник технического переводчика
ГРАФ ЭКСТРЕМАЛЬНЫЙ — граф, на к ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек рой одной числовой характеристики при ограничениях на другие числовые характеристики и… … Математическая энциклопедия
Граф ожидания — (или граф ожидания транзакций) инструмент, используемый при разработке СУБД и многопоточных систем и используемый, в частности, для определения ситуации взаимной блокировки (deadlock). Фактически, граф ожидания транзакций представляет собой … Википедия
Двудольный граф — Биграф Двудольный граф или биграф это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что ка … Википедия
Двудольный граф (теория графов) — Биграф Биграф, двудольный граф или чётный граф это математический термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества U и V, то связи будут… … Википедия
Двудольный ориентированный граф — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Чётный граф (теория графов) — Биграф Биграф, двудольный граф или чётный граф это математический термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества U и V, то связи будут… … Википедия
Планарный граф — Планарный граф граф, который может быть изображен на плоскости без пересечения ребер. Более строго: Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим … Википедия
