Graf przedziałowy

Graf przedziałowy – graf utworzony ze zbioru odcinków na prostej, poprzez przypisanie każdemu odcinkowi wierzchołka i połączenie krawędziami wierzchołków, których odcinki się nakładają.

Formalnie, niech

$I_{1},I_{2},\ldots I_{n}\subset R$

będzie zbiorem odcinków. Odpowiada mu graf przedziałowy G = (V, E), gdzie

$V=\{I_{1},I_{2},\ldots I_{n}\}$

i

$(I_{\alpha },I_{\beta })\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .$

Grafy przedziałowe są stosowane w modelowaniu alokacji zasobów w badaniach operacyjnych. Każdy przedział odpowiada wtedy zapotrzebowaniu na zasób przez jakiś czas. Znalezienie maksymalnego zbioru niezależnego odpowiada znalezieniu maksymalnego zbioru zapotrzebowań który może być zaspokojony bez stworzenie konfliktów.

Grafy przedziałowe są grafami doskonałymi.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Interval Graph, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).