Tài liệu

Xây dựng các chu trình cơ bản của đồ thị

Science and Technology

Xây dựng tập các chu trình cơ bản của đồ thị

Bài toán xây dựng cây khung của đồ thị liên quan chặt chẽ đến một số bài toán ứng dụng khác của lý thuyết đồ thị: bài toán xây dựng tập các chu trình cơ bản của đồ thị mà ta sẽ xét trong mục này.

Giả sử G=(V, E) là đơn đồ thị vô hướng liên thông, H=(V, T) là cây khung của nó. Các cạnh của đồ thị thuộc cây khung ta sẽ gọi là các cạnh trong, còn các cạnh còn lại sẽ gọi là cạnh ngoài.

Định nghĩa 1

Nếu thêm một cạnh ngoài e ∈ E\T vào cây khung H chúng ta sẽ thu được đúng một chu trình trong H, ký hiệu chu trình này là Ce. Tập các chu trình  = { Ce : e ∈ E\T } được gọi là tập các chu trình cơ bản của đồ thị G.

Giả sử A và B là hai tập hợp, ta đưa vào phép toán sau

A  B = ( A B) \ ( A  B).

Tập A  B được gọi là hiệu đối xứng của hai tập A và B.

Tên gọi chu trình cơ bản gắn liền với sự kiện là mỗi chu trình của đồ thị đều có thể thu được từ các chu trình cơ bản như chỉ ra trong định lý sau đây:

Định lý 2

Giả sử G=(V,E) là đồ thị vô hướng liên thông, H=(V,T) là cây khung của nó. Khi đó mọi chu trình của đồ thị G điều có thể biểu diễn như là hiệu đối xứng của một số các chu trình cơ bản.

Việc tìm tập hợp chu trình cơ bản giữ một vai trò quan trọng trong vấn đề giải tích mạng điện. Cụ thể hơn, theo mỗi chu trình cơ bản của đồ thị tương ứng với mạng điện cần phân tích ta sẽ thiết lập được một phương trình tuyến tính theo định luật Kirchoff: tổng hiệu điện thế dọc theo một mạch vòng là bằng không. Hệ thống phương trình tuyến tính thu được cho phép tính toán hiệu điện thế trên mọi đường dây của lưới điện.

Ta sẽ xây dựng thuật toán xây dựng các chu trình cơ bản dựa trên thủ tục tìm kiếm theo chiều sâu trên đồ thị. Thuật toán có cấu trúc tương tự như thuật toán xây dựng cây khung theo thủ tục tìm kiếm theo chiều sâu mô tả trong mục trước.

Thuật toán xây dựng tập các chu trình cơ bản.

Giả thiết rằng đồ thị G=(V,E) được mô tả bằng danh sách Ke(v),v∈ V.

Procedure Cycle(v);

(* tim kiem cac chu trinh co ban cua thanh phan lien thong chua dinh v; cac bien d, num , stack, index la bien toan cuc *)

begin

d:=d+1; stack[d]:=v; num:=num+1;index[v]:=num;

for u Ke(v) do

if index[u]=0 then cycle(u)

else

if (u <> stack[d-1]) and (index[v]>index[u]) then

<Ghi nhan chu trinh voi cac dinh:

stack[d], stack[d-1],. . ., stack[c], voi stack[c]=u>

d:=d-1;

end;

(* Main Program *)

begin

for v V do Index[v]:=0;

num:=0; d:=0; stack[0]:=0;

for v V do

if Index[v]=0 then cycle(v);

end.

Chú ý: Độ phức tạp tính toán của thuật toán vừa mô tả là O(|E| |V| ).

Đánh giá:
0 dựa trên 0 đánh giá
Nội dung cùng tác giả
 
Nội dung tương tự