TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị: Chương 2 - Biểu diễn đồ thị trên máy tính

Bài giảng Lý thuyết đồ thị: Chương 2 - Biểu diễn đồ thị trên máy tính giới thiệu tới các bạn những nội dung về các phương pháp biểu diễn đồ thị trên máy tính; sự đẳng cấu của đồ thị; minh họa về biểu diễn đồ thị trên máy tính. Bài giảng phục vụ cho các bạn chuyên ngành Toán học và những ngành có liên quan. | Chương 2 Biểu diễn đồ thị trên máy tính Phần Các phương pháp biểu diễn đồ thị trên máy tính Biểu diễn đồ thị trên máy tính??? Tại sao phải biểu diễn đồ thị trên máy tính??? Lý thuyết đồ thị ngày càng được ứng dụng rộng rãi. Để xây dựng được các ứng dụng của đồ thị trên máy tính thì cần phải tìm cách biểu diễn đồ thị trên máy tính thích hợp. Máy tính không thể hiểu được các đồ thị dưới dạng hình vẽ thông thường. Tiêu chuẩn để lựa chọn cách thức biểu diễn đồ thị trên máy tính? Cấu trúc dữ liệu phải đơn giản, phù hợp với từng bài toán ứng dụng. Dễ biểu diễn, dễ cài đặt các ứng dụng trên đó. 5/14/2020 4:49:36 AM Lý thuyết đồ thị Ma trận kề Cho đồ thị G = , với V = {v1, v2, , vn}. Ma trận kề biểu diễn G là một ma trận vuông A, kích thước nxn, được xác định như sau: VD: 5/14/2020 4:49:36 AM Lý thuyết đồ thị Ma trận kề (tt) VD: 5/14/2020 4:49:36 AM Lý thuyết đồ thị 1 2 3 4 5 6 Ma trận kề (tt) Đặc điểm của ma trận kề: Ma trận vuông, các phần tử chỉ mang giá trị 0 hoặc 1. Ma trận kề của đồ thị vô hướng là ma trận đối xứng Xác định bậc dựa vào ma trận kề: Đối với đồ thị vô hướng: số lượng các phần tử khác 0 trên một dòng (cột) chính là bậc của đỉnh tương ứng với dòng (cột) đó. Đối với đồ thị có hướng: Số lượng các phần tử khác 0 trên dòng chính là bán bậc ra của đỉnh tương ứng với dòng đó. Số lượng các phần tử khác 0 trên cột chính là bán bậc vào của đỉnh tương ứng với cột đó. 5/14/2020 4:49:36 AM Lý thuyết đồ thị Ma trận liên thuộc đỉnh – cạnh Cho đồ thị vô hướng G = , với V = {v1, v2, , vn}, E = {e1, e2, , em}. Ma trận liên thuộc đỉnh – cạnh biểu diễn G là một ma trận A, kích thước nxm, được xác định như sau: Ví dụ: 5/14/2020 4:49:36 AM Lý thuyết đồ thị vi là đỉnh đầu của cạnh ej vi không là đỉnh đầu của cạnh ej Ma trận liên thuộc (tt) VD: 5/14/2020 4:49:36 AM Lý thuyết đồ thị 1 2 3 4 5 6 e1 e2 e3 e4 e5 e6 e7 Ma trận liên thuộc (tt) Cho đồ thị có hướng G = , với V = {v1, v2, , vn}, E = {e1, e2, , em}. Ma trận liên thuộc .

Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.