intTypePromotion=1
 » 
 » 

Bài giảng học Lý thuyết đồ thị

Chia sẻ: Nguyen Doan Minh Tri | Ngày: | Loại File: PPT | Số trang:59

0
Thêm vào BST
Báo xấu
180
lượt xem 55
download

Bài giảng học Lý thuyết đồ thị

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

lý thuyết đồ thị nghiên cứu các tính chất của đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởi các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng. Đồ thị thường được vẽ dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạn thẳng (các cạ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 học Lý thuyết đồ thị

  1. Lý thuyết đồ thị Chương 1: Giới thiệu 1
  2. Chương 1: Giới thiệu Định nghĩa:  Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp các đỉnh (vertices) V (V≠ Ø) và các cạnh (edges) E. Mỗi cạnh tương ứng với 2 đỉnh. Nếu cạnh e tương ứng với 2 đỉnh v, w thì ta nói v và w là 2 đỉnh liên kết hay kề (adjacent) với nhau và e được gọi là tới các đỉnh v, w. Ký e = vw hay v e w. hiệu 2
  3. Chương 1: Giới thiệu A Các đỉnh: A, B, C, D  Các cạnh: AB, AC, AD,  BD, BC B D C Cạnh không phân biệt thứ tự của đỉnh được gọi là cạnh vô hướng. Đồ thị bao gồm các cạnh vô hướng được gọi là đồ thị vô hướng. 3
  4. Chương 1: Giới thiệu Định nghĩa:  Cạnh uv tương ứng với 2 đỉnh trùng nhau gọi - là vòng (loop) hay khuyên. B A C 4
  5. Chương 1: Giới thiệu Hai cạnh phân biệt cùng tương ứng với một - cặp đỉnh gọi là 2 cạnh song song (parallel edge). B A C 5
  6. Chương 1: Giới thiệu Đồ thị không có cạnh song song và khuyên - được gọi là đơn đồ thị (simple graph), ngược lại là đa đồ thị (multi graph). B A B A C C D 6
  7. Chương 1: Giới thiệu Đồ thị G’ = (V’, E’) gọi là 1 đồ thị con (sub - graph) của đồ thị G = (V, E) nếu V’ ⊂ V và E’ ⊂ E. A A’ E’ B’ E B C’ D C 7
  8. Chương 1: Giới thiệu Đồ thị có số đỉnh và số cạnh hữu hạn gọi là - đồ thị hữu hạn (finite graph), ngược lại là đồ thị vô hạn (infinite graph). 8
  9. Chương 1: Giới thiệu Biểu đồ  A’ A B B’ A” C’ E’ D C B” C” D’ 9
  10. Chương 1: Giới thiệu Bậc của một đỉnh  Bậc (degree) của một đỉnh v, ký hiệu là d(v), - chính là số cạnh tới đỉnh đó. Mỗi vòng tại một đỉnh sẽ được xem như 2 cạnh tới đỉnh đó. Nếu d(v) = 0, v được gọi là đỉnh cô lập (isolated - vertex). Nếu d(v) = 1, v được gọi là đỉnh treo (perdant - vertex), cạnh tới đỉnh treo được gọi là cạnh treo (perdant edge). Đồ thị mà mọi đỉnh đều là đỉnh cô lập được gọi - là đồ thị rỗng (null graph). 10
  11. Chương 1: Giới thiệu Bậc của các đỉnh:  A B C A: 2 G B: 5 F D C: 0 (đỉnh cô lập) E D: 2 Y X E: 1 (đỉnh treo) F: 4 G’ Z T 11
  12. Chương 1: Giới thiệu Đồ thị mà mọi cặp đỉnh đều kề nhau được - gọi là đồ thị đầy đủ (complete graph). Đồ thị đầy đủ có n đỉnh được ký hiệu là Kn. A E B D C 12
  13. Chương 1: Giới thiệu Đồ thị bù của một đồ thị G, ký hiệu là G, là - một đồ thị có cùng đỉnh với G và có các cạnh là những cạnh mà ta phải bổ sung vàođể G trở thành đầy đủ. G G 13
  14. Chương 1: Giới thiệu Định lý 1.1:  Với mọi đồ thị G = (V, E), ta có: ∑d (v) = 2 E v∈V Hệ quả 1.1:  Tổng số bậc của các đỉnh bậc lẻ trong 1 đồ thị là 1 số chẵn Hệ quả 1.2:  Mọi đồ thị đều có một số chẵn các đỉnh bậc l ẻ. 14
  15. Chương 1: Giới thiệu Hệ quả 1.3:  1 Đồ thị Kn có n(n-1) cạnh. 2 15
  16. Chương 1: Giới thiệu Biểu diễn đồ thị - Danh sách kề  ABBDE C BAACDE CCCBD B D DABCE EABD A E 16
  17. Chương 1: Giới thiệu Biểu diễn đồ thị - Ma trận kề:  C A B C D E A 0 2 0 1 1 B 2 0 1 1 1 B D C 0 1 2 1 0 D 1 1 1 0 1 E 1 1 0 1 0 A E 17
  18. Chương 1: Giới thiệu Định lý 1.2:  Tổng các phần tử trên hàng (hoặc cột) thứ i của ma trận kề của đồ thị G có n đỉnh bằng bậc của đỉnh vi của đồ thị ấy, nghĩa là: n n d (vi ) = ∑ mik = ∑ mki k =1 k =1 18
  19. Chương 1: Giới thiệu Đường đi và chu trình  Cho một đồ thị G. Một đường đi P trong G là một dãy các cạnh nối tiếp có chung đầu mút v0v1, v1v2,..., vk-1vk. Ký hiệu: P = v0 e1 v1 e2 ... ek vk hay P = v0v1...vk k (số cạnh tạo thành P) được gọi là chiều dài của P. Ký hiệu l(P) = k. 19
  20. Chương 1: Giới thiệu Đường đi P: EACB  A l(P) = 3  B E D C 20
ADSENSE
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 © 2009-2019 TaiLieu.VN. All rights reserved.

 

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