TAILIEUCHUNG - GRAPH THEORY - PART 1

Lý thuyết đồ thị có thể được nói đến đã bắt đầu vào 1736 khi Euler đã xem xét các trường hợp (nói chung của các) vấn đề Königsberg cầu: Có một đi bộ lộ trình đi qua mỗi trong bảy cây cầu Königsberg đúng một lần? (Solutio Problematis quảng cáo geometriam situs pertinentis, Commentarii Academiae Scientiarum imperialis Petropolitanae 8 (1736), trang 128-140.) Phải mất 200 năm trước khi cuốn sách đầu tiên về lý thuyết đồ thị được viết. Này được thực hiện bằng cách König vào năm 1936. ("Theorie der endlichen và unendlichen Graphen", Teubner, Leipzig, 1936. Bản dịch bằng tiếng Anh, năm 1990) Kể từ khi lý. | Lecture Notes on GRAPH THEORY Tero Harju Department of Mathematics University of Turku FIN-20014 Turku Finland e-mail harju@ 2007 Contents 1 Introduction. 2 Graphs and their plane figures. 4 Subgraphs . 7 Paths and cycles . 11 2 Connectivity of Graphs. 16 Bipartite graphs and trees. 16 Connectivity . 24 3 Tours and Matchings. 30 Eulerian graphs. 30 Hamiltonian graphs . 32 Matchings . 36 4 Colourings . 43 Edge colourings . 43 Ramsey Theory . 47 Vertex colourings . 52 5 Graphs on Surfaces. 60 Planar graphs. 60 Colouring planar graphs. 67 Genus of a graph. 74 6 Directed Graphs. 83 Digraphs. 83 Network Flows. 89 Index. 96 1 Introduction Graph theory can be said to have its beginning in 1736 when Euler considered the general case of the Konigsberg bridge problem Is there a walking route that crosses each of the seven bridges of Konigsberg exactly once Solutio Problema-tis ad geometriam situs pertinentis Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 1736 pp. 128-140. It took 200 years before the first book on graph theory was written. This was done by Konig in 1936. Theorie der endlichen und unendlichen Graphen Teubner Leipzig 1936. Translation in English 1990. Since then graph theory has developed into an extensive and popular branch of mathematics which has been applied to many problems in mathematics computer science and other scientific and not-so-scientific areas. For the history of early graph theory see . Biggs . Lloyd and . Wilson Graph Theory 1736 - 1936 Clarendon Press 1986. There seem to be no standard notations or even definitions for graph theoretical objects. This is natural because the names one uses for these objects reflect the applications. So for instance if we consider a communications network say for email as a graph then the computers which take part in this network are called nodes rather than vertices or points. on the other hand other names are used for

• Toán học
• toán rời rạc
• biểu diễn đồ thị
• lý thuyết đồ thị
• cơ sở dữ liệu
• thuật toán masyt ính
• biểu diễn cây
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc