Материал из WikiGrapp
Перейти к:навигация, поиск

Layout --- укладка, нумерация.

A layout (or linear layout, linear arrangement) of a graph G = (V,E) is an assignment of distinct integers from \{1, \ldots, n\} to the elements of V. Equivalently, a layout {\mathcal L} may be thought of as an ordering {\mathcal L}(1), \ldots, {\mathcal L}(n) of V, where |V| = n. A tree layout is a linear arrangement of a tree. If p is a non-integer point on x-axis, then the cut of the layout {\mathcal L} at p, denoted cut_{{\mathcal L}}(p) is the number of edges that cross over p, i.e. the number of edges (u,v) \in G with {\mathcal L}(u) < p < {\mathcal L}(v). The cutwidth of a layout {\mathcal L}, denoted cut({\mathcal L}), is the maximum cut of {\mathcal L} over all possible values; namely,

cut({\mathcal L}) = \max_{1 < p < |V|} cut_{{\mathcal L}}(p).

The cutwidth of a graph G, denoted cut(G), is the minimum cutwidth of any linear arrangement of G.

The width of a layout {\mathcal L}, b(G,{\mathcal L}), is the maximum of |{\mathcal L}(u) - {\mathcal L}(v)| over all edges (u,v) of G. That is, it is the length of the longest edge in the layout. The bandwidth of G, bw(G), is the minimum width over all layouts. A bandwidth layout for a graph G is a layout satisfying b(G,{\mathcal L}) = bw(G).

See also

  • Bandwidth, Separation-width.