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

Định nghĩa 1

Nếu thêm một cạnh ngoài e ∈ ET 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à C_e. Tập các chu trình  = { C_e : e ∈ ET } đượ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| ).