intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Toán rời rạc - Chương 5: Các khái niệm cơ bản của lý thuyết đồ thị (Phần 1) (ĐH Công nghệ Thông tin)

Chia sẻ: Gió Biển | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST
Báo xấu
90
lượt xem 6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Toán rời rạc - Chương 5: Các khái niệm cơ bản của lý thuyết đồ thị (Phần 1)" cung cấp cho người đọc các kiến thức: Các khái niệm cơ bản, biểu diễn đồ thị, một số đồ thị đặc biệt, sự đẳng cấu của các đồ thị, đồ thị có hướng, đường đi và chu trình, sự liên thông. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc - Chương 5: Các khái niệm cơ bản của lý thuyết đồ thị (Phần 1) (ĐH Công nghệ Thông tin)

  1. CHƯƠNG 5: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ PHẦN 1: - Các khái niệm cơ bản - Biểu diễn đồ thị - Một số đồ thị đặc biệt - Sự đẳng cấu của các đồ thị - Đồ thị có hướng - Đường đi và chu trình - Sự liên thông 1
  2. Các khái niệm cơ bản  Đồ thị (Graph)  G = (V, E) với V≠  V: tập các đỉnh  E: tập các cạnh  Cạnh eE  ứng với 2 đỉnh v, wV  v, w là 2 đỉnh kề (hay liên kết) với nhau, e liên thuộc với v và w  Ký hiệu: e = vw (…)  v w : e được gọi là vòng (khuyên) tại v Chương 1. Đại cương về đồ thị 2
  3. Các khái niệm cơ bản  Đồ thị (Graph)  Cạnh bội (song song)  Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh B x  Đơn đồ thị A C  Đồ thị không có vòng và y z cạnh song song D  Đa đồ thị  Các đồ thị không phải là đơn đồ thị Chương 1. Đại cương về đồ thị 3
  4. Các khái niệm cơ bản  Đồ thị (Graph)  Đồ thị đầy đủ  Đồ thị mà mọi cặp đỉnh đều kề nhau  Kn: đơn đồ thị đầy đủ  Đồ thị con  Đồ thị G’ = (V’, E’)  V’  V, E’  E  Đồ thị hữu hạn  E và V hữu hạn  Đồ thị vô hạn Chương 1. Đại cương về đồ thị 4
  5. Biểu diễn đồ thị  Biểu diễn hình học  Mỗi đỉnh  một điểm  Mỗi cạnh  một đường (cong hoặc thẳng) nối 2 đỉnh liên thuộc với nó  Biểu diễn bằng ma trận  Thường được dùng để biểu diễn trên máy tính  2 cách biểu diễn thường dùng  Ma trận kề  Ma trận liên thuộc Chương 1. Đại cương về đồ thị 5
  6. Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ma trận vuông cấp n (số đỉnh của đồ thị)  Các phần tử a ij được xác định bởi  a ij  1 : Nếu v i v j là một cạnh của G  a ij  0: Nếu v i v j không là một cạnh của G  Tính chất  Phụ thuộc vào thứ tự liệt kê của các đỉnh  Ma trận là đối xứng  Một vòng được tính là một cạnh (akk = 1) Chương 1. Đại cương về đồ thị 6
  7. Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ví dụ 1 Chương 1. Đại cương về đồ thị 7
  8. Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ví dụ 2 B D A B C D E A 0 1 1 0 0 B 1 0 1 1 1 A C 1 1 0 1 2 D 0 1 1 1 2 C E E 0 1 2 2 0 Chương 1. Đại cương về đồ thị 8
  9. Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận liên thuộc  Ma trận M = ( a ij )nxm  Các phần tử a ij được xác định bởi  a ij  1 : Nếu cạnh e j liên thuộc với vi của G  a: ij  0 : Nếu cạnh e j không liên thuộc với vi của G  Tính chất  Các cột tương ứng với các cạnh bội là giống nhau trong ma trân liên thuộc  Các vòng ứng với một cột có đúng một phần tử bằng 1 ứng với đỉnh nối với vòng đó. Chương 1. Đại cương về đồ thị 9
  10. Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma liên thuộc  Ví dụ e1 e2 e3 e4 e5 e6 e7 e8 v1 1 1 1 0 0 0 0 0 v2 0 1 1 1 0 1 1 0 v3 0 0 0 1 1 0 0 0 v4 0 0 0 0 0 0 1 1 v5 0 0 0 0 1 1 0 0 Chương 1. Đại cương về đồ thị 10
  11. Biểu diễn đồ thị  Biểu diễn bằng bảng (danh sách liền kề)  Lưu trữ các đỉnh liền kề với một đỉnh Đỉnh Đỉnh liền kề  Ví dụ a b, c, e b a c b a c a, c, d, e d c, e e d e a, c, d Chương 1. Đại cương về đồ thị 11
  12. Các khái niệm cơ bản  Bậc của đỉnh  Đỉnh của đồ thị G có bậc là n nếu nó kề với n đỉnh khác. g f e  Ký hiệu: deg(v) hay d(v)  Mỗi vòng được kể là 2 cạnh tới một đỉnh  Đỉnh cô lập  deg(v)=0 a b c d  Đỉnh treo  deg(v)=1  Cạnh treo có đầu mút là một đỉnh treo  Đồ thị rỗng: deg(v)=0 v Chương 1. Đại cương về đồ thị 12
  13. Các khái niệm cơ bản  Bậc của đỉnh  Định lý 1.1  Trong mọi đồ thị G = (V, E), tổng số bậc của các đỉnh của G bằng 2 lần số cạnh của nó  Hệ quả  Trong mọi đồ thị G = (V, E) ta có  Số đỉnh bậc lẻ là một số chẵn  Tổng bậc của đỉnh bậc lẻ là một số chẵn Chương 1. Đại cương về đồ thị 13
  14. Các khái niệm cơ bản  Bậc của đỉnh  Định lý 1.2  Trong mọi đơn đồ thị G = (V, E), nếu số đỉnh nhiều hơn 1 thì tồn tại ít nhất hai đỉnh cùng bậc.  Định lý 1.3  Trong mọi đơn đồ thị G = (V, E), nếu số đỉnh nhiều hơn 2 và có đúng hai đỉnh cùng bậc thì hai đỉnh này không đồng thời có bậc bằng 0 hoặc n-1. Chương 1. Đại cương về đồ thị 14
  15. Các khái niệm cơ bản  Chứng minh và giải toán bằng phương pháp đồ thị 1. Xây dựng đồ thị mô tả đầy đủ thông tin của bài toán  Mỗi đỉnh vV  một đối tượng trong bài toán  Mỗi cạnh eE  mối quan hệ giữa hai đối tượng  Vẽ đồ thị mô tả bài toán 2. Sử dụng các định nghĩa, tính chất, định lý, … suy ra điều cần phải chứng minh Chương 1. Đại cương về đồ thị 15
  16. Các khái niệm cơ bản  Một số bài toán ví dụ Chứng minh rằng trong một cuộc họp tùy ý có ít nhất 2 đại biểu tham gia trở lên, luôn có ít nhất hai đại biểu mà họ có số người quen bằng nhau trong các đại biểu đến dự họp. Chương 1. Đại cương về đồ thị 16
  17. Các khái niệm cơ bản  Một số bài toán ví dụ Chứng minh rằng số người mà mỗi người đã có một số lẻ lần bắt tay nhau trên trái đất là một con số chẵn. Chương 1. Đại cương về đồ thị 17
  18. Một số đồ thị đặc biệt  Đồ thị đầy đủ Kn  Đơn đồ thị  Số đỉnh: |V| = n  Bậc: deg(v) = n – 1, v V  Số cạnh: |E| = n(n - 1) / 2 K1 K2 K3 K4 K5 K6 Chương 1. Đại cương về đồ thị 18
  19. Một số đồ thị đặc biệt  Đồ thị vòng Cn  Đơn đồ thị  Số đỉnh: |V| = n  3  Bậc: deg(v) = 2, v V  Số cạnh: |E| = n Chương 1. Đại cương về đồ thị 19
  20. Một số đồ thị đặc biệt  Đồ thị hình bánh xe Wn  Nối các đỉnh của Cn với một đỉnh mới u ta được Wn  Số đỉnh: |V| = n + 1, n 3  Bậc: deg(v) = 3, v V \ {u}; deg(u) = n  Số cạnh: |E| = 2n Chương 1. Đại cương về đồ thị 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2