Atsiliepimai

Įvertinimų nėra.

Įvertink ir tu! Visi atsiliepimai

Aprašymas

Let be the given interval family. Each interval i in I is represented by [ai, bi] for i = 1, 2, ... n. here ai is called the left endpoint and bi is the right end point of the interval Ii. Without loss of generality we may assume that all end points of the intervals in I which are distinct between 1 and 2n. The intervals are labelled in the increasing order of their right end points. Two intervals i and j are said to intersect each other, if they have non-empty intersection. Interval graphs play important role in numerous applications, many of which are scheduling problems. They are a subset of perfect graphs. A graph G = (V, E) is called an interval graph if there is a one-to-one correspondence between V and I such that two vertices of G are joined by an edge in E if and only if their corresponding intervals in I intersect.