Graf przedziałowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

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

i

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]