Ряд отображений связан с понятием графа пересечений. Графом пересечений некоторого набора множеств называется граф, каждая ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Горбатов В.А. Логическое управление информационными процессами


Ряд отображений связан с понятием графа пересечений. Графом пересечений некоторого набора множеств называется граф, каждая вершина которого взаимно однозначно соответствует множеству из заданного набора и две вершины смежны, если соответствующие множества пересекаются. Так, интервальным графом, или графом интервалов, называется граф, для которого существует множество интервалов вещественной прямой такое, что граф пересечений этого множества изоморфен данному графу. Если вместо интервалов прямой рассматриваются дуги окружности, то граф называют графом дуг круга. Множество интервалов и множество дуг окружности для этих графов изображены на рис. 1.9 и 1.10 соответственно.

(cкачать страницу)

Смотреть книгу на libgen

Ряд отображений связан с понятием графа пересечений. Графом пересечений некоторого набора множеств называется граф, каждая вершина которого взаимно однозначно соответствует множеству из заданного набора и две вершины смежны, если соответствующие множества пересекаются. Так, интервальным графом, или графом интервалов, называется граф, для которого существует множество интервалов вещественной прямой такое, что граф пересечений этого множества изоморфен данному графу. Если вместо интервалов прямой рассматриваются дуги окружности, то граф называют графом дуг круга. Множество интервалов и множество дуг окружности для этих графов изображены на рис. 1.9 и 1.10 соответственно.