Đang chuẩn bị liên kết để tải về tài liệu:
GRAPH THEORY - PART 5

Graphs on Surfaces Cơ quan đại diện mặt phẳng của đồ thị không có nghĩa là duy nhất. Thật vậy, một đồ thị có thể được rút ra trong tự ý nhiều cách khác nhau. Ngoài ra, các tính chất của một đồ thị không nhất thiết phải ngay lập tức từ một đại diện, nhưng có thể được rõ ràng khác. Tuy nhiên, gia đình quan trọng của đồ thị, biểu đồ bề mặt, dựa trên các thuộc tính (topo hình học) của các bản vẽ của đồ thị. Chúng tôi hạn chế mình trong chương này để tự. | 5 Graphs on Surfaces 5.1 Planar graphs The plane representations of graphs are by no means unique. Indeed a graph G can be drawn in arbitrarily many different ways. Also the properties of a graph are not necessarily immediate from one representation but may be apparent from another. There are however important families of graphs the surface graphs that rely on the topological or geometrical properties of the drawings of graphs. We restrict ourselves in this chapter to the most natural of these the planar graphs. The geometry of the plane will be treated intuitively. A planar graph will be a graph that can be drawn in the plane so that no two edges intersect with each other. Such graphs are used e.g. in the design of electrical or similar circuits where one tries to or has to avoid crossing the wires or laser beams. Planar graphs come into use also in some parts of mathematics especially in group theory and topology. There are fast algorithms linear time algorithms for testing whether a graph is planar or not. However the algorithms are all rather difficult to implement. Most of them are based on an algorithm designed by Auslander and Parter 1961 see Section 6.5 of S. Skiena Implementing Discrete Mathematics Combinatorics and Graph Theory with Mathematica Addison-Wesley 1990. Definition Definition. a graph G is a planar graph if it has a plane figure F G called the plane embedding of G where the lines or continuous curves corresponding to the edges do not intersect each other except at their ends. The complete bipartite graph G. i is a planar graph. Definition. An edge e uv E Eg is subdivided when it is replaced by a path . . V of length two by introducing a new vertex .A A subdivision of a graph G is obtained from G by a sequence of subdivisions. 5.1 Planar graphs 61 The following result is clear. Lemma 5.1. A graph is planar if and only if its subdivisions are planar Geometric properties It is clear that the graph theoretical properties ofG are inherited by all of