Definition and Construction
Given a connected graph G=(V,E) with V the set of vertices and E the set of edges, and with a root vertex r, the level structure is a partition of the vertices into subsets Li called levels, consisting of the vertices at distance i from r. Equivalently, this set may be defined by setting L0 = {r}, and then, for i > 0, defining Li to be the set of vertices that are neighbors to vertices in Li − 1 but are not themselves in any earlier level.
If a breadth first search of G is performed, starting from r, then the vertices in each level will be found as a consecutive subsequence of the breadth first ordering of the graph. These subsets may be computed by performing a breadth first search, calculating the level of each vertex v as it is processed by the search by adding one to the minimum level of an already-processed neighbor of v, and storing this level with v so that its later neighbors may perform the same calculation.
Read more about this topic: Level Structure
Famous quotes containing the words definition and/or construction:
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)
“There is, I think, no point in the philosophy of progressive education which is sounder than its emphasis upon the importance of the participation of the learner in the formation of the purposes which direct his activities in the learning process, just as there is no defect in traditional education greater than its failure to secure the active cooperation of the pupil in construction of the purposes involved in his studying.”
—John Dewey (1859–1952)