BÀi tập và thực hành môn học lý thuyết đồ thị

4Tính liên thông

Bài 4.1.

a) (a, e, b, c, b)

b) (a, e, a, d, b, c, a)

c) (e, b, a, d, b, e)

d) (c, b, d, a, e, c)

Bài 4.2. Các danh sách đỉnh sau đây có tạo nên đường đi trong đồ thị bên dưới hay không? Đường đi nào là đơn? Đường đi nào là chu trình? Độ dài của các đường đi này là bao nhiêu?

a) (a, b, e, c, b)

b) (a, d, a, d, a)

c) (a, d, b, e, a)

d) (a, b, e, c, b, d, a)

Bài 4.3. Xác định xem các đồ thị đã cho có liên thông không.



Bài 4.4. Có bao nhiêu thành phần liên thông trong các đồ thị ở các Bài tập 4.3? Tìm các thành phần liên thông đó.

Bài 4.5. Tìm tất cả các đỉnh cắt và cạnh cắt của đồ thị.



Bài thực hành số 1: Biểu diễn đồ thị

Bài tập 1:

Nhập vào ma trận kề của một đơn đồ thị (từ bàn phím và đọc từ tập tin).

1. 
   Kiểm tra tính hợp lệ của đồ thị (giá trị trên đường chéo chính đều bằng 0).
   
2. 
   Kiểm tra xem đồ thị là vô hướng hay hữu hướng?
   
3. 
   Nếu ma trận kề được nhập từ bàn phím thì xuất ra thành tập tin matranke.txt
   
4. 
   Nếu ma trận được đọc từ tập tin thì xuất kết quả ma trận ra màn hình hiển thị.
   
5. 
   Xuất ra bậc của tất cả các đỉnh của đồ thị (số cạnh nối tới đỉnh).
   
6. 
   Kiểm tra tính liên thông của đồ thị? Xuất ra tất cả các thành phần liên thông nếu có.
   

Nhập vào ma trận trọng số của một đơn đồ thị (từ bàn phím và đọc từ tập tin).

1. 
   Kiểm tra tính hợp lệ của đồ thị (giá trị trên đường chéo chính đều bằng 0).
   
2. 
   Kiểm tra xem đồ thị là vô hướng hay hữu hướng?
   
3. 
   Nếu ma trận kề được nhập từ bàn phím thì xuất ra thành tập tin trongso.txt
   
4. 
   Nếu ma trận được đọc từ tập tin thì xuất kết quả ma trận ra màn hình hiển thị.
   
5. 
   Xuất ra cạnh có trọng số nhỏ nhất và lớn nhất.
   

#include

#include

void main()

{

int n,m,i,j;

// Doc n, m tu ban phim

printf(" Nhap n, m ");

scanf("%d %d",&n,&m);

for (i=0;i

for (j=0;j

{

printf(" Nhap a[%d][%d]: " ,i,j);

}

// Xuat mang a ra man hinh

for (i=0;i

{

for (j=0;j

{

fprintf(f,"%3d",a[i][j]);

}

fprintf(f,"\n");

getch();

#include

#include

void main()

{

int n,m,i,j;

FILE* f;

f = fopen("D:\\matranke.txt","rt");

fscanf(f,"%d%d",&n,&m);

for (i=0;i

{

for (j=0;j

{

fscanf(f,"%d",&b[i][j]);

}

}

fclose(f);

printf(" Mang B co n:%d m:%d\n",n,m);

for (i=0;i

{

for (j=0;j

{

printf("%3d",b[i][j]);

}

printf("\n");

getch();

CHƯƠNG 2: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON

Cài đặt thuật toán duyệt theo chiều sâu và chiều rộng với đồ thị được cho bởi ma trận kề đọc từ tập tin matranke.txt, chương trình cho phép nhập vào đỉnh xuất phát và hiển thị kết quả duyệt.

Cài đặt chương trình cho phép nhập vào 2 đỉnh x và y của đồ thị, kiểm tra xem có đường đi từ x tới y (và ngược lại) hay không?

4.1.1Duyệt đồ thị theo chiều sâu (thuật toán DFS)

Ý tưởng chính của thuật toán có thể trình bày như sau:

• 
  Ta sẽ bắt đầu tìm kiếm từ một đỉnh v₀ nào đó của đồ thị.
  
• 
  Sau đó chọn u là một đỉnh tuỳ ý kề với v₀ và chưa được duyệt.
  
• 
  Lặp lại quá trình đối với u. Đây là thủ tục đệ quy.
  
• 
  Quá trình đệ quy kết thúc khi không chọn được đỉnh u nữa.
  

Thủ tục đệ quy được viết như sau:

Thủ tục DFS(v); (*tim kiem theo chieu sau bat dau tu dinh v; cac bien Chuaxet, Ke la bien toan cuc*) Bắt đầu Tham_dinh(v); Chuaxet[v]:=false; For u là Ke(v) do If Chuaxet[u] then DFS(u); Kết thúc (*dinh v da duyet xong*)

Duyệt toàn bộ đồ thị theo chiều sâu: Bắt đầu for v thuộc V do Chuaxet[v]:=true; for v thuộc V do if Chuaxet[v] then DFS(v); Kết thúc Độ phức tạp là : O(n+m)

4.1.2Duyệt đồ thị theo chiều rộng (thuật toán BFS)

Ý tưởng chính của thuật toán như sau:

• 
  Sử dụng 1 hàng đợi để lưu trữ các đỉnh sẽ được duyệt.
  
• 
  Ban đầu đưa đỉnh bắt đầu duyệt u vào hàng đợi.
  
• 
  Thực hiện quá trình lặp cho đến khi hàng đợi rỗng. Mỗi bước lặp làm như sau:
  
  • 
    Lấy 1 đỉnh v ra khỏi hàng đợi. Thực hiện các công việc cần thiết với đỉnh đó.
    
  • 
    Xác định các đỉnh w kề với đỉnh v mà chưa duyệt.
    
  • 
    Đưa các đỉnh w này vào hàng đợi.
    

Thủ tục được viết như sau:

Thủ tục BFS(u); (*Tim kiem theo chieu rong bat dau tu dinh u, cac bien Chuaxet, Ke la bien cuc bo*) Bắt đầu QUEUE:= Ø; QUEUE  u; (* nap u vao QUEUE*) Chuaxet[v]:=false; While QUEUE ≠ Ø do Begin v  QUEUE:; (*lay p tu QUEUE:*) Tham_dinh(v); For w là Ke(v) do If Chuaxet[w] them Begin QUEUE  w; Chuaxet[w]:=false; End; End; Kết thúc

Duyệt toàn bộ đồ thị theo thuật toán BFS: Bắt đầu (*khởi tạo ban đầu *) for mọi k thuộc V do Chuaxet[k]:=true; for u thuộ V do if Chuaxet[u] then BFS(v); Kết thúc Thuật toán BFS có độ phức tạp: O(n+m)

4.1.3Ứng dụng của thuật toán duyệt

Ta thấy, tư tưởng của thuật toán duyệt là xuất phát từ 1 đỉnh u, và đi thăm các đỉnh v còn lại trong đồ thị nếu như tồn tại 1 đường đi từ đỉnh u đến v.

Như vậy ta sẽ giải quyểt được 2 bài toán như sau:

• 
  Tìm 1 đường đi giữa 2 đỉnh bất kỳ.
  
• 
  Kiểm tra tính liên thông của đồ thị và tìm các thành phần liên thông trong đồ thị.
  

Để xác định được 1 đường đi từ đỉnh u đến đỉnh v, ta cần phải làm như sau:

• 
  Dùng thủ tục duyệt theo chiều sâu với đỉnh u.
  
• 
  Trong quá trình duyệt có sử dụng mảng các biến trạng thái Chuaxet[k] (hay Free[k]) để kiểm tra đỉnh k đã được duyệt chưa.
  
• 
  Để xác định đường đi ta dùng mảng biến lưu trữ vết Truoc[k] = t, có nghĩa là từ đỉnh t sẽ chuyển đến đỉnh k.
  

Bổ sung vào các thủ tục DFS và BFS như sau:

Đối với DFS bổ sung code như sau: If Chuaxet[u] then Begin Truoc[u]:= v; Chuaxet[u] = false; DFS(u); End;

Đối với BFS bổ sung code như sau: If Chuaxet [u] then Begin QUEUE  u; Chuaxet[u]:= false; Truoc[u]:= p; End;

Xác định đường đi từ u đến v như sau:

While (v ≠ u) do Begin In giá trị v ra ngoài màn hình; v = Truoc[v] ; // gán v bằng đỉnh mà từ nó nhảy đến v hiện tại End; In giá trị u ra màn hình;

Để xác định số thành phần liên thông trong đồ thị thì ta dùng thêm 1 biến count đế đếm. Khi đó các bước phải làm như sau:

• 
  Khởi tạo các mảng biến cần thiết, và count = 0.
  

• 
  Xét với mọi đỉnh u trong đồ thị, nếu như đỉnh u chưa được duyệt thì:
  
  • 
    Tăng giá trị của biến count lên 1 đơn vị
    
  • 
    Thực hiện các thuật toán duyệt đối với đỉnh u.
    
• 
  Nếu kết quả biến count = 1 thì đồ thị liên thông. Trong trường hợp còn lại thì giá trị của count chính là số thành phần liên thông của đồ thị.
  

Viết thêm code để xác định số thành phần liên thông:

Count :=0; If Chuaxet[u] then Begin Count := Coutn + 1; DFS(u); End;

Count :=0; If Chuaxet[u] then Begin Count := Coutn + 1; BFS(u); End;

CHƯƠNG 3
ĐỒ THỊ CÓ TRỌNG SỐ VÀ ĐƯỜNG ĐI NGẮN NHẤT

Bài 1. Tìm chiều dài của đường đi ngắn nhất giữa a và z trong đồ thị có trọng số sau đây

Bài 2. Tìm độ dài của đường đi ngắn nhất giữa các cặp đỉnh sau đây trong các đồ thị có trọng số ở Bài 6.1.

a) a và d b) a và f c) c và f d) b và z

Bài 3. Tìm độ dài đường đi ngắn nhất từ đỉnh A đến tất các đỉnh còn lại trong các đồ thị sau:



Bài 4. Tìm độ dài đường đi ngắn nhất từ đỉnh A đến tất các đỉnh còn lại trong các đồ thị sau:

Каталог: wp-content -> uploads -> 2017
2017 -> Th ng b¸o thuèc míi
2017 -> Nguyen hoang cuong
2017 -> Curriculum vitae
2017 -> CỤc quản lý DƯỢc cộng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh Phúc
2017 -> Cung cấp giải pháp phần mềm
2017 -> MỘt số kiến thức cơ BẢn dành cho newbie
2017 -> NguyễN ĐĂng thảo vài Nét Chấm Phá Trong Đời Sống Âm Nhạc
2017 -> ĐỀ CƯƠng chi tiết môN: quản trị nguồn nhân lựC
2017 -> Điều Danh mục thuốc đông y, thuốc từ dược liệu và vị thuốc y học cổ truyền

tải về 257.57 Kb.

Chia sẻ với bạn bè của bạn: