Graf przedziałowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

W teorii grafów graf przedziałowy to 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 \phi.

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[edytuj | edytuj kod]