|
A thrackle is an embedding of a graph in the plane, such that each edge is a Jordan arc and every pair of edges meet once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, the crossing must be ''transverse''.〔. A preliminary version of these results was reviewed in .〕 ==Linear thrackles== A linear thrackle is a thrackle drawn in such a way that its edges are straight line segments. Every linear thrackle has at most as many edges as vertices, a fact that was observed by Paul Erdős. Erdős observed that, if a vertex ''v'' is connected to three or more edges ''vw'', ''vx'', and ''vy'' in a linear thrackle, then at least one of those edges lies on a line that separates two other edges; without loss of generality assume that ''vw'' is such an edge, with ''x'' and ''y'' lying in opposite closed halfspaces bounded by line ''vw''. Then, ''w'' must have degree one, because no other edge than ''vw'' can touch both ''vx'' and ''vy''. Removing ''w'' from the thrackle produces a smaller thrackle, without changing the difference between the numbers of edges and vertices. On the other hand, if every vertex has at most two neighbors, then by the handshaking lemma the number of edges is at most the number of vertices.〔.〕 Based on Erdős' proof, one can infer that every linear thrackle is a pseudoforest. Every cycle of odd length may be arranged to form a linear thrackle, but this is not possible for an even-length cycle, because if one edge of the cycle is chosen arbitrarily then the other cycle vertices must lie alternatingly on opposite sides of the line through this edge. Micha Perles provided another simple proof that linear thrackles have at most ''n'' edges, based on the fact that in a linear thrackle every edge has an endpoint at which the edges span an angle of at most 180°, and for which it is the most clockwise edge within this span. For, if not, there would be two edges, incident to opposite endpoints of the edge and lying on opposite sides of the line through the edge, which could not cross each other. But each vertex can only have this property with respect to a single edge, so the number of edges is at most equal to the number of vertices.〔 As Erdős also observed, the set of pairs of points realizing the diameter of a point set must form a linear thrackle: no two diameters can be disjoint from each other, because if they were then their four endpoints would have a pair at farther distance apart than the two disjoint edges. For this reason, every set of ''n'' points in the plane can have at most ''n'' diametral pairs, answering a question posed in 1934 by Heinz Hopf and Erika Pannwitz.〔.〕 Andrew Vázsonyi conjectured bounds on the number of diameter pairs in higher dimensions, generalizing this problem.〔 An enumeration of linear thrackles may be used to solve the biggest little polygon problem, of finding an ''n''-gon with maximum area relative to its diameter.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Thrackle」の詳細全文を読む スポンサード リンク
|