Example
As an example, let G be a nine-vertex grid graph. Define a haven of order 4 in G, mapping each set X of three or fewer vertices to an X-flap β(X), as follows:
- If there is a unique X-flap that is larger than any of the other X-flaps, let β(X) be that unique large X-flap.
- Otherwise, choose β(X) arbitrarily to be any X-flap.
It is straightforward to verify by a case analysis that this function β satisfies the required monotonicity property of a haven. If X ⊆ Y and X has fewer than two vertices, or X has two vertices that are not the two neighbors of a corner vertex of the grid, then there is only one X-flap and it contains every Y-flap. In the remaining case, X consists of the two neighbors of a corner vertex and has two X-flaps: one consisting of that corner vertex, and another (chosen as β(X)) consisting of the six remaining vertices. No matter which vertex is added to X to form Y, there will be a Y-flap with at least four vertices, which must be the unique largest flap since it contains more than half of the vertices not in Y. This large Y-flap will be chosen as β(Y) and will be a subset of β(X). Thus in each case monotonicity holds.
Read more about this topic: Haven (graph Theory)
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)