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ý ...

Trang chủ Tìm kiếm Trang chủ Tìm kiếm 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) pdf 45 942 KB 3 47 4.4 ( 7 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 45 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 Biểu diễn đồ thị Sự đẳng cấu của các đồ thị đồ thị có hướng Sự liên thông Đường đi và chu trình

Nội dung

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 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 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 A Đơ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ị B x C D y z 3 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 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 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 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 Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ví dụ 2 A A 0 B 1 C 1 D 0 E 0 B C D E 1 1 0 0 0 1 1 1 1 0 1 2 1 1 1 2 1 2 2 0 Chương 1. Đại cương về đồ thị B D A C E 8 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 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 v2 0 v3 0 v4 0 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 v5 0 0 0 0 1 1 0 0 Chương 1. Đại cương về đồ thị 10 This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Tìm kiếm

Chủ đề

Đồ án tốt nghiệp Đề thi mẫu TOEIC Đơn xin việc Mẫu sơ yếu lý lịch Tài chính hành vi Thực hành Excel Bài tiểu luận mẫu Lý thuyết Dow Atlat Địa lí Việt Nam Hóa học 11 Giải phẫu sinh lý Trắc nghiệm Sinh 12 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