LÝ THUYẾT ĐỒ THỊ (TOÁN RỜI RẠC, CẤU TRÚC RỜI RẠC) - 123doc

Tải bản đầy đủ (.ppt) (45 trang)

1. Trang chủ
>>
2. Giáo án - Bài giảng
>>
3. Cao đẳng - Đại học

LÝ THUYẾT ĐỒ THỊ (TOÁN RỜI RẠC, CẤU TRÚC RỜI RẠC)

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (503.09 KB, 45 trang )

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-1Cá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, eliê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 vChương 1. Đại cương về đồ thị2Cá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ớimột cặp đỉnhĐơn đồ thị Đồ thị không có vòng và cạnh song songĐa đồ thị Các đồ thị không phải là đơn đồ thịChương 1. Đại cương về đồ thịBAxCDyz3Cá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ạnChương 1. Đại cương về đồ thị4Biểu diễn đồ thị BiểuMỗi đỉnh ≡ một điểmMỗi cạnh ≡ một đường (cong hoặc thẳng) nối 2 đỉnh liênthuộc với nó Biểudiễn hình họcdiễn bằng ma trậnThường được dùng để biểu diễn trên máy tính2 cách biểu diễn thường dùng Ma trận kề Ma trận liên thuộcChương 1. Đại cương về đồ thị5Biểu diễn đồ thị Biểudiễn bằng ma trậnMa trận kề Ma trận vuông cấp n (số đỉnh của đồ thị) Các phần tử được xác định bởi: Nếuaij = 1: Nếuaijlà một cạnh của Gvi vkhôngjlà một cạnh của Gvi v jaijchất= 0 Tính Phụ thuộc vào thứ tự liệt kê của các đỉnhMa trận là đối xứngMột vòng được tính là một cạnh (akk = 1)Chương 1. Đại cương về đồ thị6Biểu diễn đồ thịBiểu diễn bằng ma trậnMa trận kề Ví dụ 1Chương 1. Đại cương về đồ thị7Biểu diễn đồ thịBiểu diễn bằng ma trậnMa trận kề Ví dụ 2ABCDEA B C D E0 1 1 01 0 1 11 1 0 10 1 1 10 1 2 2Chương 1. Đại cương về đồ thịB01220DACE8Biểu diễn đồ thị Biểudiễn bằng ma trậnMa trận liên thuộc Ma trận M = ( )nxmaij Các phần tử được xác định bởiaij: Nếu cạnhliên thuộc với vi của Ga= 1: Nếu cạnh ekhôngj: ijliên thuộc với vi của Gaijchất= 0ej TínhCác cột tương ứng với các cạnh bội là giống nhau trong ma trânliên thuộcCá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ị9Biểu diễn đồ thịBiểu diễn bằng ma trậnMa liên thuộc Ví dụv1v2v3v4v5e1 e21 10 10 00 00 0e311000e401100Chương 1. Đại cương về đồ thịe500101e601001e701010e80001010Biể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 đỉnhVí dụbaeChương 1. Đại cương về đồ thịcdĐỉnhabcdeĐỉnh liền kềb, c, eaa, c, d, ec, ea, c, d11Các khái niệm cơ bảnBậc của đỉnhĐỉnh của đồ thị G có bậclà n nếu nó kề với n đỉnhkhác.Ký hiệu: deg(v) hay d(v)Mỗi vòng được kể là 2cạnh tới một đỉnhĐỉnh cô lập ⇔ deg(v)=0Đỉnh treo ⇔ deg(v)=1Cạnh treo có đầu mút làmột đỉnh treoĐồ thị rỗng: deg(v)=0 ∀vChương 1. Đại cương về đồ thịagfebcd12Cá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ủanó Hệ quả Trong mọi đồ thị G = (V, E) ta cóSố đỉnh bậc lẻ là một số chẵnTổng bậc của đỉnh bậc lẻ là một số chẵnChương 1. Đại cương về đồ thị13Cá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 đỉnhcù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ùngbậ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ị14Các khái niệm cơ bảnChứng minh và giải toán bằng phươngphá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án2.Sử dụng các định nghĩa, tính chất, định lý, … suy ra điềucần phải chứng minhChương 1. Đại cương về đồ thị15Cá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ó ítnhấ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 trongcác đại biểu đến dự họp.Chương 1. Đại cương về đồ thị16Cá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ộtsố 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ị17Một số đồ thị đặc biệtĐồ thị đầy đủ KnK1Đơn đồ thịSố đỉnh: |V| = nBậc: deg(v) = n – 1, ∀v ∈VSố cạnh: |E| = n(n - 1) / 2K2Chương 1. Đại cương về đồ thịK3K4K5K618Một số đồ thị đặc biệtĐồ thị vòng CnĐơn đồ thịSố đỉnh: |V| = n ≥ 3Bậc: deg(v) = 2, ∀v ∈VSố cạnh: |E| = nChương 1. Đại cương về đồ thị19Mộ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 ≥ 3Bậc: deg(v) = 3, ∀v ∈V \ {u};deg(u) = nSố cạnh: |E| = 2nChương 1. Đại cương về đồ thị20Một số đồ thị đặc biệtĐồ thị đều bậc k (Đồ thị k-đều)Mọi đỉnh đều có cùng bậc kSố đỉnh: |V| = nBậc: deg(v) = k, ∀v ∈VSố cạnh: |E| = n.k/2Ví dụ:Cn là đồ thị đều bậc 2Kn là đồ thị đều bậc (n-1)Chương 1. Đại cương về đồ thị21Một số đồ thị đặc biệtCác khối n-lập phương Qnn Có 2 đỉnh, mỗi đỉnh được biểu diễn bằng một dãy số nhịphân với độ dài n.Hai đỉnh là liền kề nếu và chỉ nếu các dãy nhị phân biểudiễn chúng chỉ khác nhau đúng 1 bit.n2Số đỉnh: |V| =Bậc: deg(v) = n, ∀v ∈Vn −12Số cạnh: |E| = n.Chương 1. Đại cương về đồ thị22Một số đồ thị đặc biệtĐồ thị bùHai đơn đồ thị G và G’ được gọi là bù nhau chúng có chung các đỉnh Cạnh nào thuộc G thì không thuộc G’ và ngược lạiKý hiệu: G’ =Chương 1. Đại cương về đồ thịG23Một số đồ thị đặc biệtĐồ thị lưỡng phânMột đồ thị G được gọi là đồ thị lưỡng phân nếu tập cácđỉnh của G có thể phân thành 2 tập hợp không rỗng, rờinhau sao cho mỗi cạnh của G nối một đỉnh thuộc tập nàyđến một đỉnh thuộc tập kia.Ký hiệu: Km,nK 3, 3Chương 1. Đại cương về đồ thị24Sự đẳng cấu giữa các đồ thị ĐịnhnghĩaG(V, E) đẳng cầu với G’(V’, E’), (G ≈ G’) nếu Tồn tại song ánh f: V  V’ Bảo toàn quan hệ liền kề:∀u,v ∈V, uv ∈E ⇔ f(u)f(v) ∈E’G đẳng cấu với G’ thì |V| = |V’| |E| = |E’| deg(v) = deg(f(v)), ∀ v ∈VChương 1. Đại cương về đồ thị25

Tài liệu liên quan

• ly thuyet do thi
  • 24
  • 281
  • 0
• ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: HC3CT-Lần 1-Đề 2 ppt
  • 1
  • 965
  • 8
• ĐỀ THI MÔN TÓAN RỜI RẠC & LÝ THUYẾT DỒ THỊ LỚP: Học lại K4 docx
  • 1
  • 741
  • 4
• Lý thuyết đồ thị ôn thi học sinh giỏi
  • 23
  • 716
  • 2
• lý thuyết đồ thị qua các định lý và bài toán
  • 22
  • 1
  • 13
• Tóm tắt bài giảng môn lý thuyết đồ thị
  • 34
  • 901
  • 2
• GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ pot
  • 121
  • 832
  • 18
• LÝ THUYẾT ĐỒ THỊ - CÂY pdf
  • 33
  • 561
  • 3
• Lý thuyết đồ thị (Nguyễn Thanh Sơn) - chương 4 ĐỒ THỊ PHẲNG pdf
  • 24
  • 669
  • 2
• Lý thuyết đồ thị - Phần 4 docx
  • 7
  • 370
  • 0

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(896 KB - 45 trang) - LÝ THUYẾT ĐỒ THỊ (TOÁN RỜI RẠC, CẤU TRÚC RỜI RẠC) Tải bản đầy đủ ngay ×