zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Lý thuyết đồ thị: Chương 2 - Nguyễn Trần Phi Phượng

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:14

Báo xấu

206
lượt xem 16
download

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

Dưới đây là bài giảng Lý thuyết đồ thị: Chương 2 - Biểu diễn đồ thị trên máy tính do Nguyễn Trần Phi Phương biên soạn. Mời các bạn tham khảo để nắm bắt được những nội dung về ma trận kề - ma trận trọng số; ma trận liên thuộc đỉnh cạnh; danh sách cạnh; danh sách kề.

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 Lý thuyết đồ thị: Chương 2 - Nguyễn Trần Phi Phượng

Chương 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH
2.1 Ma trận kề - Ma trận trọng số Ma trận kề Xét đơn đồ thị G = (V,E) bao gồm V={v1, v2, …, vn}. Ma trận kề biểu diễn G là một ma trận vuông A =[aij]n, được xác định như sau: ⎧1, (vi , v j ) ∈ E aij = ⎨ ⎩0, (vi , v j ) ∉ E 1 2 3 4 Ví dụ 1 ⎡0 0 1 0⎤ 2 ⎢⎢ 0 0 0 1 ⎥⎥ A= 3 ⎢0 0 0 1⎥ ⎢ ⎥ 4 ⎣1 1 0 0⎦ 08/03/2011 Lý thuyết đồ thị 2
2.1 Ma trận kề - Ma trận trọng số Ví dụ 1 2 3 4 5 6 1 ⎡0 1 0 0⎤ 1 1 1 2 3 2 ⎢⎢1 0 1 0⎥⎥ 1 1 3 ⎢0 1 0 0⎥ 0 0 A= ⎢ ⎥ 4 ⎢1 1 0 0 0⎥ 1 4 5 6 5 ⎢1 1 0 1 0 0⎥ ⎢ ⎥ 6 ⎢⎣0 0 0 0 0 0⎥⎦ 08/03/2011 Lý thuyết đồ thị 3
2.1 Ma trận kề - Ma trận trọng số Các tính chất của ma trận kề 1. Ma trận kề của đồ thị vô hướng là ma trận đối xứng. 2. Tổng các phần tử trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j). Chú ý Ma trận kề của đa đồ thị có thể xây dựng hoàn toàn tương tự. ⎧k , (vi , v j ) ∈ E aij = ⎨ k: số cạnh nối hai đỉnh vi và vj ⎩ 0, (vi , v j ) ∉ E 08/03/2011 Lý thuyết đồ thị 4
2.1 Ma trận kề - Ma trận trọng số Đồ thị có trọng số Đồ thị G = (V,E) gọi là đồ thị có trọng số (hay chiều dài, trọng lượng) nếu mỗi cạnh (cung) e được gán với một số thực w(e).Ta gọi w(e) là trọng lượng của e Ma trận trọng số Cho G = (V, E), V = {v1,v2,…,vn} là đơn đồ thị có trọng số. Ma trận khoảng cách của G là ma trận D= (dij) xác định như sau: ⎧0, i = j ⎪ dij = ⎨ w(vi , v j ), (vi , v j ) ∈ E ⎪ ∞, ( v , v ) ∉ E ⎩ i j 08/03/2011 Lý thuyết đồ thị 5
2.1 Ma trận kề - Ma trận trọng số Ví dụ ⎡0 5 31 40 ∞ ∞ ∞⎤ ⎢∞ 0 27 ∞ 73 ∞ ∞⎥⎥ ⎢ ⎢∞ 26 0 8 49 25 38⎥ ⎢ ⎥ D = ⎢∞ ∞ ∞ 0 ∞ 16 ∞⎥ ⎢∞ 70 ∞ ∞ 0 ∞ 9 ⎥ ⎢ ⎥ ⎢∞ ∞ ∞ ∞ 23 0 12⎥ ⎢∞ ∞ ∞ ∞ 10 ∞ 0 ⎥⎦ ⎣ 08/03/2011 Lý thuyết đồ thị 6
2.2 Ma trận liên thuộc đỉnh cạnh Xét đồ thị có hướng G = (V,E) với V={v1, v2,…, vn}, E={e1, e2,…, em}. Ma trận liên thuộc đỉnh – cạnh A=[aij]n×m được xây dựng theo quy tắc: ⎧1, nếu vi là đỉnh đầu của cung ej ⎪ aij = ⎨−1, nếu vi là đỉnh cuối của cung ej ⎪0, nếu vi không là đỉnh đầu, đỉnh cuối của ⎩ cung ej 08/03/2011 Lý thuyết đồ thị 7
2.2 Ma trận liên thuộc đỉnh cạnh Ví dụ e1 e2 e3 e4 e5 1 ⎡ 1 −1 0 0 0 ⎤ e1 e4 ⎢ ⎥ e2 e5 2 ⎢ 0 0 0 1 −1⎥ A= e3 3 ⎢ −1 0 1 0 0 ⎥ ⎢ ⎥ 4 ⎣ 0 1 −1 −1 1 ⎦ 08/03/2011 Lý thuyết đồ thị 8
2.3 Danh sách cạnh Cho đồ thị G = (V,E) có m cạnh. Danh sách cạnh của G sẽ bao gồm hai mảng 1 chiều có kích thước m: – Mảng Dau sẽ lưu các đỉnh đầu của các cạnh – Mảng Cuoi sẽ lưu đỉnh cuối của các cạnh Ví dụ Dau Cuoi 1 3 e1 e4 4 1 e2 e5 3 4 e3 4 2 2 4 08/03/2011 Lý thuyết đồ thị 9
2.3 Danh sách cạnh Ví dụ Dau Cuoi 1 2 1 e1 2 e2 3 2 3 e4 e3 e7 1 4 e5 1 5 4 e6 5 6 4 2 4 5 2 5 08/03/2011 Lý thuyết đồ thị 10
2.3 Danh sách cạnh Xác định bậc của đỉnh dựa vào danh sách cạnh: – Đối với đồ thị vô hướng: duyệt qua 2 mảng Dau va Cuoi, số lần xuất hiện của một đỉnh chính là bậc của đỉnh đó. – Đối với đồ thị có hướng: • Duyệt qua mảng Dau, số lần xuất hiện của một đỉnh chính là bán bậc ra của đỉnh đó. • Duyệt qua mảng Cuoi, số lần xuất hiện của một đỉnh chính là bán bậc vào của đỉnh đó. 08/03/2011 Lý thuyết đồ thị 11
2.4 Danh sách kề Cho đồ thị G = (V,E) có n đỉnh. Đồ thị G có thể được biểu diễn bằng n danh sách liên kết. Mỗi danh sách liên kết thứ i sẽ biểu diễn các đỉnh kề với đỉnh vi Ví dụ 1 3 NULL 2 4 NULL 3 4 NULL 4 1 2 NULL 08/03/2011 Lý thuyết đồ thị 12
2.4 Danh sách kề 1 2 3 Ví dụ 4 5 6 1 2 4 5 NULL 2 1 3 4 5 NULL 3 2 NULL 4 1 2 5 NULL 5 1 2 4 NULL 6 NULL 08/03/2011 Lý thuyết đồ thị 13
2.4 Danh sách kề Xác định bậc của đỉnh dựa vào danh sách kề: – Đối với đồ thị vô hướng: Số phần tử của mỗi danh sách sẽ là bậc của đỉnh tương ứng – Đối với đồ thị có hướng: • Số phần tử của mỗi danh sách sẽ là bán bậc ra của đỉnh tương ứng • Việc xác định bán bậc vào khó khăn hơn nhiều: phải duyệt qua tất cả các danh sách, số lần xuất hiện của 1 đỉnh trong các danh sách chính là bán bậc vào của đỉnh đó. 08/03/2011 Lý thuyết đồ thị 14

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 © 2022-2032 TaiLieu.VN. All rights reserved.