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

Bài giảng Lý thuyết đồ thị: Chương 1 - ThS. Nguyễn Khắc Quốc

Chia sẻ: Fgnfffh Fgnfffh | Ngày: | Loại File: PDF | Số trang:56

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

Bài giảng Lý thuyết đồ thị: Chương 1 Đồ thị nhằm trình bày về khái niệm, định nghĩa đồ thị, các ví dụ về đồ thị, ứng du5g bài toán đồ thi vào khoa học tự nhiên, nêu định nghĩa, khái niệm và hệ quả của bậc của đỉnh...bài giảng hữu ích dành cho sinh viên ngành khoa học máy tính.

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 Lý thuyết đồ thị: Chương 1 - ThS. Nguyễn Khắc Quốc

  1. BÀI GIẢNG MÔN LÝ THUYẾT ĐỒ THỊ Ths. Nguyễn Khắc Quốc IT.Deparment – Tra Vinh University 1
  2. Chương 1 ĐỒ THỊ - Lý thuyết đồ thị là một ngành khoa học được phát triển từ lâu - có nhiều ứng dụng hiện đại. - Những ý tưởng cơ bản được đưa ra từ thế kỷ 18 bởi nhà toán học Thụy Sĩ tên là Leonhard Euler. - Giải quyết bài toán 7 chiếc cầu Konigsberg nổi tiếng. Dùng để giải các bài toán trong nhiều lĩnh vực: + Xác định xem có thực hiện một mạch điện trên một bảng điện phẳng được không. + phân biệt hai hợp chất hóa học có cùng công thức phân tử nhưng có cấu trúc khác nhau Đồ thị với các trọng số dùng để giải các bài toán: + Tìm đường đi ngắn nhất. + Lập lịch thi đấu + Chia kênh cho các đài truyền hình. ThS. Nguyễn Khắc Quốc 2
  3. 1.1. ĐỊNH NGHĨA VÀ THÍ DỤ. - Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó. Đồ thị vô hướng Phân loại: + Theo đặc tính + Số các cạnh nối các cặp đỉnh của đồ thị. Đồ thị có hướng ThS. Nguyễn Khắc Quốc 3
  4. 1.1. ĐỊNH NGHĨA VÀ THÍ DỤ (tt). Ứng dụng: - Biểu diễn sự cạnh tranh các loài trong một môi trường sinh thái, - Biểu diễn ai có ảnh hưởng lên ai trong một tổ chức nào đó, - Biểu diễn các kết cục của cuộc thi đấu thể thao. - Tính số các tổ hợp khác nhau của các chuyến bay giữa hai thành phố trong một mạng hàng không, - Đi tham quan tất cả các đường phố của một thành phố sao cho mỗi đường phố đi qua đúng một lần, - Tìm số các màu cần thiết để tô các vùng khác nhau của một bản đồ. ThS. Nguyễn Khắc Quốc 4
  5. 1.1. ĐỊNH NGHĨA VÀ THÍ DỤ (tt). 1.1.1. Định nghĩa: Một đơn đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt. ThS. Nguyễn Khắc Quốc 5
  6. 1.1. ĐỊNH NGHĨA VÀ THÍ DỤ (tt). 1.1.2. Định nghĩa: Một đa đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt. Hai cạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng với một cặp đỉnh. Rõ ràng mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị. ThS. Nguyễn Khắc Quốc 6
  7. 1.1. ĐỊNH NGHĨA VÀ THÍ DỤ (tt). 1.1.3. Định nghĩa: Một giả đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh (không nhất thiết là phân biệt). Với vV, nếu (v,v)E thì ta nói có một khuyên tại đỉnh v. ThS. Nguyễn Khắc Quốc 7
  8. 1.1. ĐỊNH NGHĨA VÀ THÍ DỤ (tt). Tóm lại: - Giả đồ thị là loại đồ thị vô hướng tổng quát nhất vì nó có thể chứa các khuyên và các cạnh bội. - Đa đồ thị là loại đồ thị vô Giả đồ thị hướng có thể chứa cạnh bội nhưng không có các khuyên, - Đơn đồ thị là loại đồ thị vô hướng không chứa cạnh bội Đơn đồ thị hoặc các khuyên. ThS. Nguyễn Khắc Quốc 8
  9. 1.1. ĐỊNH NGHĨA VÀ THÍ DỤ (tt). 1.1.4. Định nghĩa: Một đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V. ThS. Nguyễn Khắc Quốc 9
  10. 1.1. ĐỊNH NGHĨA VÀ THÍ DỤ (tt). 1.1.5. Định nghĩa: - Một đa đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự Đồ thị có hướng của các phần tử thuộc - Đồ thị vô hướng nhận được từ đồ thị có hướng G bằng cách xoá bỏ các chiều mũi tên trên các cung được gọi là đồ thị vô hướng nền của Đa đồ thị có hướng G. ThS. Nguyễn Khắc Quốc 10
  11. 1.2. BẬC CỦA ĐỈNH. 1.2.1. Định nghĩa: Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được gọi là liền kề nếu (u,v)E. Nếu e = (u,v) thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u, v gọi là các điểm đầu mút của cạnh e. ThS. Nguyễn Khắc Quốc 11
  12. 1.2. BẬC CỦA ĐỈNH (tt). 1.2.2. Định nghĩa: Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập nếu deg(v)=0. Ta có: deg(v1)=7, deg(v2)=5, deg(v3)=3, deg(v4)=0, (đỉnh cô lập) deg(v5)=4, deg(v6)=1, (đỉnh treo) deg(v7)=2. ThS. Nguyễn Khắc Quốc 12
  13. 1.2. BẬC CỦA ĐỈNH (tt). 1.2.3. Mệnh đề: Cho đồ thị G = (V, E). Khi đó: Chứng minh: - Rõ ràng mỗi cạnh e = (u,v) được tính một lần trong deg(u) và một lần trong deg(v). - Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh. ThS. Nguyễn Khắc Quốc 13
  14. 1.2. BẬC CỦA ĐỈNH (tt). 1.2.4. Hệ quả: Số đỉnh bậc lẻ của một đồ thị là một số chẵn. Chứng minh: + Gọi V1 và V2 tương ứng là tập các đỉnh bậc chẵn và tập các đỉnh bậc lẻ của đồ thị G = (V, E). Khi đó: + Vế trái là một số chẵn và tổng thứ nhất cũng là một số chẵn nên tổng thứ hai là một số chẵn. Vì deg(v) là lẻ với mọi v  V2 nên |V2| là một số chẵn. ThS. Nguyễn Khắc Quốc 14
  15. 1.2. BẬC CỦA ĐỈNH (tt). 1.2.5. Mệnh đề: Trong một đơn đồ thị, luôn tồn tại hai đỉnh có cùng bậc. Chứng minh: Xét đơn đồ thị G=(V,E) có |V|=n. Khi đó phát biểu trên được đưa về bài toán: +Trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau ThS. Nguyễn Khắc Quốc 15
  16. 1.2. BẬC CỦA ĐỈNH (tt). 1.2.6. Định nghĩa: Đỉnh u được gọi là nối tới v hay v được gọi là được nối từ u trong đồ thị có hướng G nếu (u,v) là một cung của G. Đỉnh u gọi là đỉnh đầu và đỉnh v gọi là đỉnh cuối của cung này. ThS. Nguyễn Khắc Quốc 16
  17. 1.2. BẬC CỦA ĐỈNH (tt). 1.2.7. Định nghĩa: Bậc vào (hoặc bậc ra) của đỉnh v trong đồ thị có hướng G, ký hiệu degt(v) (hoặc dego(v)), là số các cung có đỉnh cuối là v. Thí dụ: degt(v1) = 2, dego(v1) = 3, degt(v2) = 5, dego(v2) = 1, degt(v3) = 2, dego(v3) = 4, degt(v4) = 1, deg0(v4) = 3, degt(v5) = 1, dego(v5) = 0, degt(v6) = 0, dego(v6) = 0. - Đỉnh có bậc vào và bậc ra cùng bằng 0 gọi là đỉnh cô lập. - Đỉnh có bậc vào bằng 1 và bậc ra bằng 0 gọi là đỉnh treo, cung có đỉnh cuối là đỉnh treo gọi là cung treo. ThS. Nguyễn Khắc Quốc 17
  18. 1.2. BẬC CỦA ĐỈNH (tt). 1.2.8. Mệnh đề: Cho G =(V, E) là một đồ thị có hướng. Khi đó Chứng minh: Kết quả có ngay là vì mỗi cung được tính một lần cho đỉnh đầu và một lần cho đỉnh cuối. ThS. Nguyễn Khắc Quốc 18
  19. 1.3. NHỮNG ĐƠN ĐỒ THỊ ĐẶC BIỆT. 1.3.1. Đồ thị đầy đủ: Đồ thị đầy đủ n đỉnh, ký hiệu là Kn, là đơn đồ thị mà hai đỉnh phân biệt bất kỳ của nó luôn liền kề. - Như vậy, Kn có cạnh và mỗi đỉnh của Kn có bậc là n1. Thí dụ: ThS. Nguyễn Khắc Quốc 19
  20. 1.3. NHỮNG ĐƠN ĐỒ THỊ ĐẶC BIỆT (tt). 1.3.2. Đồ thị vòng: Đơn đồ thị n đỉnh v1, v2, ...,vn (n3) và n cạnh (v1,v2), (v2,v3),...,(vn-1,vn), (vn,v1) được gọi là đồ thị vòng. - Ký hiệu là Cn. - Như vậy, mỗi đỉnh của Cn có bậc là 2. Thí dụ: ThS. Nguyễn Khắc Quốc 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
4=>1