Bài Giảng Toán Rời Rạc Và Lý Thuyết đồ Thị: Bài 4 - Võ Tấn Dũng

Trang chủ Tìm kiếm Trang chủ Tìm kiếm Bài giảng Toán rời rạc và lý thuyết đồ thị: Bài 4 - Võ Tấn Dũng pdf 50 4 MB 0 4 4.9 ( 21 lượt) Xem tài liệu Nhấn vào bên dưới để tải tài liệu Tải về Đang chuẩn bị: 60 Bắt đầu tải xuống Đang xem trước 10 trên tổng 50 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên Chủ đề liên quan bài giảng toán rời rạc Toán rời rạc Lý thuyết đồ thị Đơn đồ thị vô hướng Đa đồ thị vô hướng đồ thị có hướng

Nội dung

TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM MÔN TOÁN RỜI RẠC GV: Võ Tấn Dũng ĐƠN ĐỒ THỊ VÔ HƯỚNG  Đơn đồ thị vô hướng G = (V,E) là một bộ gồm hai tập hợp V và E.  V là tập các đỉnh (vertices).  E là tập các cạnh (edges), mỗi cạnh là một cặp không có thứ tự gồm 2 đỉnh khác nhau của tập V.  Ví dụ: Đơn đồ thị G1 = (V1, E1), trong đó V1={a, b, c, d, e, f, g, h}, E1={(a,b), (b,c), (c,d), (a,d), (d,e), (a,e), (d,b), (f,g)}. a f b h e c d Đồ thị G1 3 g ĐA ĐỒ THỊ VÔ HƯỚNG  Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.  Hai cạnh e1 và e2 được gọi là cạnh song song nếu chúng cùng tương ứng với một cặp đỉnh.  Ví dụ: Đa đồ thị G2 = (V2, E2), trong đó V2={a, b, c, d, e, f, g, h}, E2={(a,b), (b,c), (b,c), (c,d), (a,d), (d,e), (a,e), (a,e), (a, e), (d,b), (f,g)}. a Cạnh song song b f h e c g d Đồ thị G2 Cạnh song song, cạnh vòng  Cạnh song song (cạnh bội) Hai hay nhiều cạnh phân biệt cùng tương ứng với một cặp đỉnh  Cạnh vòng (cạnh loop):   Một cạnh tương ứng với hai đỉnh trùng nhau.  Đơ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ị  B A x C D y z ĐỒ THỊ CÓ HƯỚNG  Đơn đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh và E là tập các cặp có thứ tự gồm hai đỉnh khác nhau của V gọi là các cạnh (cung).  G = (V, E)  Tập đỉnh V  Tập cạnh (cung) E = { (a, b) | a,b  V }  e = (a, b)  E  Ký hiệu: e = ab  e có hướng từ a đến b  a: đỉnh đầu; b: đỉnh cuối  e là cạnh vòng  ab CÁC THUẬT NGỮ CƠ BẢN  Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G.  Nếu e = (u, v) là cạnh của đồ thị ta nói cạnh này là cạnh liên thuộc với hai đỉnh u và v (hoặc cũng nói là nối đỉnh u và đỉnh v)  Đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u, v). BẬC CỦA ĐỈNH  Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v). deg(a) = 1, deg(b) = 4, deg(c) = 4, deg( f) = 3, deg(d) = 1, deg(e) = 3, deg(g) = 0  Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Trong ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo.  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. 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 Đỉnh treo  deg(v)=1 Cạnh treo có đầu mút là một đỉnh treo Đồ thị rỗng: deg(v)=0 v a g f e b c d This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Tìm kiếm

Chủ đề

Giải phẫu sinh lý Tài chính hành vi Atlat Địa lí Việt Nam Đơn xin việc Hóa học 11 Đề thi mẫu TOEIC Bài tiểu luận mẫu Trắc nghiệm Sinh 12 Mẫu sơ yếu lý lịch Thực hành Excel Lý thuyết Dow Đồ án tốt nghiệp adblock ​ Bạn đang sử dụng trình chặn quảng cáo?

Nếu không có thu nhập từ quảng cáo, chúng tôi không thể tiếp tục tài trợ cho việc tạo nội dung cho bạn.

Tôi hiểu và đã tắt chặn quảng cáo cho trang web này