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
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
- Eric W.E.W. Weisstein Eric W.E.W., Interval Graph, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów |
|
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |