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

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:11

Báo xấu

132
lượt xem 17
download

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

CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THị 2.1 Biểu diễn bằng hình học Cho đồ thị G = (V, E), khi đó ta có thể biểu diễn G bằng phương pháp hình học như sau: Mỗi v ∈ V ta đặt tương ứng với một điểm trong mặt phẳng, điểm đó gọi là đỉnh của đồ thị. a) Trường hợp G là đồ thị vô hướng, nếu e = (u,v) ∈ V thì trong mặt phẳng, các đỉnh u, v được nối với nhau bởi một cạnh không có hướng. Đồ thị vô hướng G = ({v1, v2, v3, v4},...

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

Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chương 2 CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THN (6 tiết) 2.1 Biểu diễn bằng hình học Cho đồ thị G = (V, E), khi đó ta có thể biểu diễn G bằng phương pháp hình học như sau: Mỗi v ∈ V ta đặt tương ứng với một điểm trong mặt phẳng, điểm đó gọi là đỉnh của đồ thị. a) Trường hợp G là đồ thị vô hướng, nếu e = (u,v) ∈ V thì trong mặt phẳng, các đỉnh u, v được nối với nhau bởi một cạnh không có hướng. Nếu e = (u,u) ∈ V thì tại đỉnh u sẽ có một khuyên. b) Trường hợp G là đồ thị có hướng, Nếu e = (u,v) ∈ V thì trong mặt phẳng sẽ có một cung có hướng đi từ u đến v. Nếu u = v thì tại đỉnh u sẽ có một khuyên có hướng vào chính nó. Ví dụ 1: Đồ thị vô hướng G = ({v1, v2, v3, v4}, {(v1,v2), (v2,v3), (v2,v4), (v3,v4), (v4,v4)}) được biểu diễn hình học như sau: v1 v3 v4 v2 Đồ thị có hướng G = ({v1, v2, v3}, {(v1,v1), (v1,v2), (v2,v3), (v3,v1), (v3, v2)}) được biểu diễn hình học như sau: v2 v1 v3 Biểu diễn đồ thị bằng hình học là một cách biểu diễn đơn giản, trực quan nhưng không có nhiều ý nghĩa trong việc xử lý bằng máy tính. 2.2 Biểu diễn bằng ma trận kề (liền kề), ma trận trọng số Xét đơn đồ thị vô hướng G = (V,E), với tập đỉnh V = {v1, v2, ..,vn}, tập cạnh E = {e1, e2, .., em}. Ta gọi ma trận kề của đồ thị G là ma trận: A = {aij: i,j = 1,2,...,n} với các phần tử aij được xác định theo quy tắc sau: aij = 1 nếu (vi,vj) ∈ E aij = 0 nếu (vi,vj) ∉ E , i,j = 1, 2, .., n Ví dụ 2: Cho đồ thị vô hướng G = ({v1, v2, v3},{(v1,v1), (v1,v2), (v1,v3), (v2,v3)}) Ma trận kề của G là 13 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ V1 v2 v3 v1 1 1 1 v2 1 0 1 v3 1 1 0 Ví dụ 3: Cho đồ thị vô hướng G như sau: 1 2 3 4 5 Ma trận kề của G là 1 2 3 4 5 1 0 1 0 1 0 2 1 0 1 0 1 3 0 1 0 1 0 4 1 0 1 0 1 5 0 1 0 1 0 Chú ý: Ma trận kề của một đồ thị tuỳ thuộc vào thứ tự liệt kê các đỉnh. Do vậy có tới n! ma trận kề khác nhau của một đồ thị n đỉnh vì có n! cách sắp xếp n đỉnh. Các tính chất của ma trận kề của đồ thị đơn vô hướng: a) Ma trận kề của đơn đồ thị vô hướng n đỉnh là một ma trân vuông đối xứng cấp nxn. b) Tổng các phần tử trên hàng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j). c) Nếu kí hiệu a ijp , i, j = 1,2,.., n là các phần tử của ma trận tích A p = 123 A. A... A p Khi đó a , i, j = 1,2,.., n cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung p ij gian. Ma trận kề của đồ thị đơn có hướng cũng được định nghĩa tương tự, nhưng lưu ý ma trận này là không đối xứng. Ví dụ 4: Cho đơn đồ thị có hướng G 2 3 1 14 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 4 Ma trận kề của G là 1 2 3 4 1 0 1 1 0 2 0 0 0 1 3 0 1 0 0 4 1 0 0 0 Trên đây ta chỉ mới xét các đơn đồ thị, đối với đa đồ thị thì ma trận kề cũng được xây dựng hoàn toàn tương tự, chỉ khác là thay vì ghi 1 vào vị trí aij nếu (vi,vj) là cạnh (cung) của đồ thị, ta sẽ ghi k là số cạnh (cung) nối hai đỉnh vi và vj. Ví dụ 5: Cho đa đồ thị vô hướng G như sau: 3 2 1 4 5 Ma trận kề của G là 1 2 3 4 5 1 0 1 1 3 1 2 1 0 1 1 1 3 1 1 1 0 2 4 3 1 0 0 0 5 1 1 2 0 0 Ví dụ 6: Cho đa đồ thi có hướng G như sau: v4 v3 v2 v1 15 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ma trận kề của G là V1 v2 v3 v4 v1 0 0 0 0 v2 1 0 2 1 v3 1 1 0 0 v4 1 1 0 0 Trong rất nhiều ứng dụng của lý thuyết đồ thị, mỗi cạnh e = (u,v) của đồ thị được gắn một con số c nào đó (c(e), c(u,v)) gọi là trọng số của cạnh e. Đồ thị có các cạnh được gán trọng số gọi là đồ thị có trọng số. Trong trường hợp đồ thị có trọng số, để biểu diễn đồ thị thay vì dùng ma trận kề ta dùng ma trận trọng số như sau: C = cij, i,j=1, 2, .., n V ới cij = c(eij)) nếu eij ∈ E cij = θ nếu eij ∉ E , i = 1,2,..,n; j = 1,2,..,n Trong đó số θ tuỳ từng trường hợp cụ thể, có thể được đặt bằng một trong các giá trị sau: 0, - ∞ , +∞. Ví dụ 7: Cho đồ thị vô hướng có trọng số G như sau v1 8 10 v2 v5 5 v4 6 3 7 v3 Ma trận trọng số của G là v1 v2 v3 v4 v5 v1 0 0 0 10 8 v2 0 0 7 0 5 v3 0 7 0 3 0 v4 10 0 3 0 6 v5 8 5 0 6 0 16 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ví dụ 8: Cho đồ thị có hướng có trọng số G như sau: b c 7 4 3 a d 4 9 5 7 e Ma trận trọng số của G là a B c d e a 0 0 0 0 5 b 4 0 7 0 4 c 0 0 0 3 0 d 0 0 0 0 7 e 0 0 9 0 0 Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề (hoặc ma trận trọng số) là để trả lời câu hỏi: Hai đỉnh u, v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh. Nhược điểm lớn nhất của phương pháp này là: Không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. 2.3 Biểu diễn bằng ma trận liên thuộc đỉnh - cạnh Giả sử G = (V,E) là một đồ thị vô hướng với tập đỉnh V = {v1,v2,.., vn}, và tập các cạnh E = {e1,e2,..,em}. Khi đó ma trận liên thuộc đỉnh - cạnh A = aij, i = 1,2,..n, j = 1,2,...m của nó được xác định như sau: Aij = 1 nếu cạnh ej nối với đỉnh vi Aij = 0 nếu cạnh ej không nối với đinh vi, i = 1,2,..,n, j = 1,2,..,m Ví dụ 9: Cho đồ thị G như sau v3 v2 v1 e6 e2 e4 e5 e1 e3 v5 v4 Khi đó ma trận liên thuộc đỉnh - cạnh của G như sau 17 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ e1 e2 e3 e4 e5 e6 v1 1 1 0 0 0 0 v2 0 0 1 1 0 1 v3 0 0 0 0 1 1 v4 1 0 1 0 0 0 v5 0 1 0 1 1 0 Ma trận liên thuộc cũng có thể được dùng để biểu diễn đồ thị có cạnh bội và khuyên Ví dụ 10: Cho đồ thị G như sau v1 v2 v3 e4 e2 e1 e3 e7 e6 e5 v4 v5 e8 Khi đó ma trận liên thuộc đỉnh cạnh của G là e1 e2 e3 e4 e5 e6 e7 e8 v1 1 1 1 0 0 0 0 0 v2 0 1 1 1 0 1 1 0 v3 0 0 0 1 1 0 0 0 v4 0 0 0 0 0 0 1 1 Ma trận liên thuôc đỉnh - cạnh còn rất hay được sử dụng trong v5 0 0 0 0 1 1 0 0 các bài toán liên quan đến đồ thị có hướng mà trong đó phải xử lý các cung của đồ thị. Cho G = (V,E) , V = {v1,v2,..,vn}, E = {e1,e2,..,em}, là đồ thị có hướng. Khi đó ma trận liên thuộc đỉnh - cạnh A = aij , i = 1,2,..,n; j = 1,2,..., m của G được xác định như sau: aij = 1 nếu đỉnh vi là đỉnh đầu của cung ej aij =-1 nếu đỉnh vi là đỉnh cuối của cung ej aij = 0 nếu đỉnh vi không là đầu mút của cung ej 18 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ví dụ 11: Cho ma trận G như sau 2 4 6 1 3 5 Ma trận liên thuộc cạnh - đỉnh của G như sau (1,2) (1,3) (2,3) (2,4) (3,5) (4,5) (5,2) (5,6) (6,4) 1 1 1 0 0 0 0 0 0 0 2 -1 0 1 1 0 0 -1 0 0 3 0 -1 -1 0 1 0 0 0 0 4 0 0 0 -1 0 1 0 0 -1 5 0 0 0 0 -1 -1 1 1 0 6 0 0 0 0 0 0 0 -1 1 2.4 Biểu diễn bằng danh sách cạnh (cung) Xét đồ thị G = (V,E), với |V| = n, |E| = m. Để biểu diễn đồ thị theo phương pháp danh sách cạnh (cung) chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Mỗi cạnh (cung) e = (u,v) của đồ thị sẽ tương ứng với hai biến Dau[e] và Cuoi[e]. Như vậy để lưu trữ đồ thị ta cần sử dụng 2m đơn vị ô nhớ. Trong trường hợp đồ thị có trọng số ta phải cần thêm m đơn vị ô nhớ nữa để lưu trữ trọng số của các cạnh. Ví dụ 12: Cho đồ thị vô hướng G như sau 3 4 6 1 2 5 Danh sách cạnh của G như sau Dau Cuoi 1 2 1 3 2 3 2 5 3 4 4 5 4 6 5 6 19 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ví dụ 13: Cho đồ thị có hướng G như sau v2 v1 Khi đó danh sách cạnh của G là Dau Cuoi v3 v1 v2 v1 v3 v2 v3 v3 v2 2.5 Biểu diễn bằng danh sách kề Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn đồ thị dưới dạng danh sách kề là cách biểu diễn thích hợp được sử dụng. Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị chúng ta lưu trữ danh sách các đỉnh kề với nó. Để làm được điều này chúng ta có thể sử dụng cấu trúc mảng các mảng (mảng hai chiều) hoặc mảng các danh sách liên kết. Ví dụ 1: Cho đồ thị vô hướng G như sau v1 v2 v5 v4 v3 Khi đó, danh sách kề lưu trữ dưới dạng mảng như sau v2 v4 v5 v1 v1 v3 v4 v2 v2 v4 v5 v3 v1 v2 v3 v5 v4 v1 v3 v4 v5 Danh sách kề lưu trữ dưới dạng danh sách liên kết như sau: v2 v4 v5 nill v1 v1 v3 v4 nill v2 v2 v4 v5 nill v3 v1 v2 v3 v5 nill v4 v1 v3 v4 nill v5 Chúng ta có rất nhiều phương pháp khác nhau để biểu diễn đồ thị, mỗi phương pháp đều có những ưu và nhược điểm riêng của nó. Vì vậy việc lựa chọn phương pháp biểu diễn đồ thị sao cho việc xử lý nó có hiệu quả nhất phải tuỳ thuộc vào từng bài toán và giải thuật cụ thể. Cài đặt thuật toán: (nhập và hiển thị DS kề của một đồ thị biểu diễn bằng danh sách lien kết: //---------------------------------------------------------------------------- // Chuong trinh nhap va in ra danh sach ke. 20 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ //---------------------------------------------------------------------------- #include #include #include #define VMAX 100 //So dinh toi da cho mot do thi typedef struct pp //Cau truc tu tro { int v; struct pp *next; }Link; Link *Ke[VMAX]; //Danh sach ke cua do thi int n; char ch; //So dinh cua do thi //-------------------------------------------------------------------------- // Ham nhap danh sach ke cua do thi co n dinh //-------------------------------------------------------------------------- void nhap_dsk(Link *Ke[], int n) { int i,v; Link *pd,*p; //Khoi tao mang cac danh sach cac dinh ke cua cac dinh for(i=1;iv=i; Ke[i]->next = NULL; } //Nhap danh sach cac dinh ke cua cac dinh for(i=1;inext = (Link*)malloc(sizeof(Link)); p=p->next; 21 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ } p->v=v; p->next = NULL; } Ke[i]->next = pd; } } //-------------------------------------------------------------------------- // Ham hien thi danh sach ke cua do thi co n dinh //-------------------------------------------------------------------------- void in_dsk(Link *Ke[], int n) { int i; Link *pd; printf("\nDanh sach ke cua cac dinh cua do thi:\n"); printf("\n ------------------\n"); for(i=1;iv); pd = Ke[i]->next; while(pd!=NULL) { printf("%5d",pd->v); pd=pd->next; } } } // Ham in tieu de cua chuong trinh //-------------------------------------------------------------------------- void tieu_de() { printf("\n CHUONG TRINH CAI DAT CAC THUAT TOAN TIM KIEM TREN DO THI"); printf("\n --------------***--------------\n\n"); } //-------------------------------------------------------------------------- // Ham hien thi Menu chon chuc nang cua chuong trinh //-------------------------------------------------------------------------- char menu() { printf("\n Menu chon chu nang"); printf("\n ---***---\n"); printf("\n\n 1. Nhap do thi cho boi danh sach ke"); printf("\n\n 2. Hien thi danh sach ke cua do thi"); printf("\n\n 5. Ket thuc chuong trinh"); printf("\n\n ----------------------------------------"); printf("\n\n Ban chon:"); ch=getche(); return ch; } //-------------------------------------------------------------------------- 22 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ // Chuong trinh chinh //-------------------------------------------------------------------------- void main() { int kt=0,i; char ch; do { clrscr(); tieu_de(); ch = menu(); switch(ch) { case '1': //Nhap danh sach ke cua do thi clrscr(); tieu_de(); kt=1; printf("\n\n1.Nhap danh sach ke cua do thi"); printf("\n------------------------------\n\n"); printf("\n\nSo dinh cua do thi n ="); scanf("%d",&n); nhap_dsk(Ke,n); printf("\n\n\n\n--------------------------------"); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '2': //Hien thi danh sach ke cua do thi clrscr(); tieu_de(); printf("\n\n2.In danh sach ke cua do thi"); printf("\n----------------------------\n\n"); if(kt) in_dsk(Ke,n); else printf("\nDo thi chua duoc nhap vao!"); printf("\n\n\n\n--------------------------------"); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '5': //Ket thuc chuong trinh printf("\n\nXin cam on ban da su dung chuong trinh!"); getch(); break; } }while(ch!='5'); } 23 NguyÔn Minh §øc - §HQG Hµ Néi

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.