Danh mục

Bài giảng Toán rời rạc: Đồ thị phẳng - Trần Vĩnh Đức

Số trang: 36      Loại file: pdf      Dung lượng: 1.43 MB      Lượt xem: 11      Lượt tải: 0    
10.10.2023

Xem trước 4 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

Bài giảng Toán rời rạc: Đồ thị phẳng cung cấp cho người học những nội dung kiến thức như: Định nghĩa đồ thị phẳng, định lý (Công thức Euler), chứng minh công thức Euler, định lý (Bất đẳng thức cạnh đỉnh), chứng minh bất đẳng thức cạnh đỉnh,… Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Đồ thị phẳng - Trần Vĩnh Đức Đồ thị phẳng Trần Vĩnh Đức HUST Ngày 1 tháng 3 năm 2016CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 36 Tài liệu tham khảo ▶ Eric Lehman, F Thomson Leighton & Albert R Meyer, Mathematics for Computer Science, 2013 (Miễn phí) ▶ K. Rosen, Toán học rời rạc ứng dụng trong tin học (Bản dịch Tiếng Việt) ▶ Ngô Đắc Tân, Lý thuyết Tổ hợp và Đồ thị, NXB ĐHQG Hà Nội, 2004.CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 36 way to represent this graph in a plane without any edges crossing? Giới thiệu FIGURE 1 Three Houses and Three Utilities.CuuDuongThanCong.com https://fb.com/tailieudientucntt 3 / 36 Định nghĩa Một đồ thị được gọi là phẳng nếu ta có thể vẽ nó trên mặt phẳng mà không có cạnh nào cắt nhau. Hình vẽ như thế gọi là một biểu diễn phẳng của đồ thị. FIGURE 2 The FIGURE 3 K4 Drawn FIGURE 2 The FIGURE 3 K4 Drawn Graph K . with No Crossings. Graph K4 . 4 with No Crossings.CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 36 Ví dụ 10.7 Planar Graphs 719 10.7 Planar Graphs 719wn FIGURE 4 The FIGURE 5 A Planar FIGURE 4 The FIGURE 5 A Planar Graph Q3 . Representation of Q3 . Graph Q3 . Representation of Q3 . CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 36anar. We will give an example to showsubregions, R21beand how this can R22in, an done as shown ad in Figure 7 develop some general results that can be used to do this. Ví dụ v, planar? Đồ thị K3,3 : v1 v2 v3draw K3,3 in the plane with no edges crossing is doomed. We nowpresentation of K3,3 , the vertices v1 and v2 must be connected to both s form a closed curve that splits the plane into two regions, R1 anda). The vertex v3 is in either R1 or R2 . When v3 is in R2 , the inside v ges between v3 and v4 and between v3 and v5 separate R2 into two v4 v5 v6 s shown in Figure 7(b). không phẳng vì FIGURE 6 The Graph K . F 3,3 v1 v5 v1 v5 R21 R2 R1 v3 R1 R22 v4 v2 v4 v2 (a) (b)CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 36 Proof: First, we specify a planar representati a sequence of subgraphs G1 , G2 , . . . , Ge = is done using the following inductive defini Obtain Euler chứng minh rằng Gn from mọi biểu diễn phẳngby Gn−1 củaarbitrarily adding a một đồ thị đều chia mặt phẳng thành cùng số miền như nhau. R4 R2 R6 R3 R1 R5 FIGURE 8 The Regions of the Planar RCuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 36 Định lý (Công thức Euler) Cho G là một đồ thị phẳng liên thông với e cạnh và v đỉnh. Gọi r là số miền trong biểu diễn phẳng của G. Khi đó r = e − v + 2.CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 36 Ví dụ Xét một đồ thị phẳng liên thông có 20 đỉnh, mỗi đỉnh đều có bậc 3. Biểu diễn phẳng của đồ thị này chia mặt phẳng thành bao nhiêu miền? ▶ Tổng bậc bằng 3v = 3 × 20 = 60 ▶ Số cạnh e = 30 ▶ Theo công thức Euler r = e − v + 2 = 30 − 20 + 2 = 12CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 / 36 Chứng minh công thức Euler ▶ Ta chứng minh bằng quy nạp theo số miền r. ▶ Nếu r = 1 thì đồ thị không có chu trình. Tại sao? ▶ Vậy e = v − 1. 3 ▶ Giả sử định lý đúng với r > 1.CuuDuongThanCong.com https://fb.com/tailieudient ...

Tài liệu được xem nhiều: