Các khái niệm cơ bản của Lý thuyết đồ thị. Đồ thị Euler

Đồ thị đầy đủ.

Đồ thị đầy đủ n đỉnh, ký hiệu bởi K_n, là đơn đồ thị vô hướngmà giữa hai đỉnh bất kỳ của nó luôn có cạnh nối.

Các đồ thị K₃, K₄, K₅ cho trong hình dưới đây.

Hình 1 Đồ thị đầy đủ.

Đồ thị đầy đủ K_n có tất cả n(n-1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhất.

Đồ thị vòng.

Đồ thị vòng C_n, n≥3. gồm n đỉnh v₁, v₂,. . . .v_n và các cạnh (v₁,v₂), (v₂,v₃) . . . (v_n-1,v_n), (v_n,v₁).

Đồ thị vòng C₃, C₄, C₅, C₆ cho trong hình 2

Hình 2 Đồ thị vòng C 3 , C 4 , C 5 , C 6 .

Đồ thị bánh xe.

Đồ thị W_n thu được từ C_n bằng cách bổ sung vào một đỉnh mới nối với tất cả các đỉnh của C_n (xem hình 3).

Hình 3 Đồ thị bánh xe W 3 , W 4 , W 5 , W 6 .

Đồ thị lập phương.

Đồ thị lập phương n đỉnh Q_n là đồ thị với các đỉnh biểu diễn 2ⁿ xâu nhị phân độ dài n. Hai đỉnh của nó gọi là kề nhau nếu như hai xâu nhị phân tương ứng chỉ khác nhau 1 bit. Hình 4 cho thấy Q_n với n=1,2,3.

Hình 4 Đồ thị lập phương Q 1 , Q 2 , Q 3 .

Đồ thị hai phía.

Đơn đồ thị G = (V, E) được gọi là hai phía nếu như tập đỉnh V của nó có thể phân hoạch thành hai tập X và Y sao cho mỗi cạnh của đồ thị chỉ nối một đỉnh nào đó trong X với một đỉnh nào đó trong Y. Khi đó ta sẽ sử dụng ký hiệu G = (XY, E) để chỉ đồ thị hai phía với tập đỉnh XY.

Định lý sau đây cho phép nhận biết một đơn đồ thị có phải là hai phía hay không.

Định lý 1 Đơn đồ thị là đồ thị hai phía khi và chỉ khi nó không chứa chu trình độ dài lẻ.

Để kiểm tra xem một đồ thị liên thông có phải là hai phía hay không có thể áp dụng thủ tục sau. Cho v là một đỉnh bất kỳ của đồ thị. Đặt X={v}, còn Y là tập các đỉnh kề của v. Khi đó các đỉnh kề của các đỉnh trong Y phải thuộc vào X. Ký hiệu tập các đỉnh như vậy là T. Vì thế nếu phát hiện T  Y ≠ ∅ thì đồ thị không phải là hai phía, kết thúc. ngược lại, đặt X = X  T. Tiếp tục xét như vậy đối với T’ là tập các đỉnh kề của T,. ..

Đồ thị hai phía G=(X  Y, E) với |X|= m, |Y| = n được gọi là đồ thị hai phía đầy đủ và ký hiệu là K_2,3, K_3,3, K_3,4 được cho trong hình 5.

Hình 5 : Đồ thị hai phía.

Đồ thị phẳng.

Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh. Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đồ thị.

Ví dụ đồ thị K₄ là phẳng, vì có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh (xem hình 6).

Hình 6: Đồ thị K 4 là đồ thị phẳng.

Một điều đáng lưu ý nếu đồ thị là phẳng thì luôn có thể vẽ nó trên mặt phẳng với các cạnh nối là các đoạn thẳng không cắt nhau ngoài ở đỉnh (ví dụ xem cách vẽ K₄ trong hình 6).

Để nhận biết xem một đồ thị có phải là đồ thị phẳng có thể sử dụng định lý Kuratovski, mà để phát biểu nó ta cần một số khái niệm sau: Ta gọi một phép chia cạnh (u,v) của đồ thị là việc loại bỏ cạnh này khỏi đồ thị và thêm vào đồ thị một đỉnh mới w cùng với hai cạnh (u,w), (w, u) . Hai đồ thị G(V,E) và H=(W,F) được gọi là đồng cấu nếu chúng có thể thu được từ cùng một đồ thị nào đó nhờ phép chia cạnh.

Định lý 2 (Kuratovski). Đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con đồng cấu với K 3,3 hoặc K 5 .

Trong trường hợp riêng, đồ thị K_3,3 hoặc K₅ không phải là đồ thị phẳng. Bài toán về tính phẳng của đồ thị K_3,3 là bài toán đố nổi tiếng về ba căn hộ và ba hệ thống cung cấp năng lượng cho chúng: Cần xây dựng hệ thống đường cung cấp năng lượng với mỗi một căn hộ nói trên sao cho chúng không cắt nhau.

Đồ thị phẳng còn tìm được những ứng dụng quan trọng trong công nghệ chế tạo mạch in.

Biểu diễn phẳng của đồ thị sẽ chia mặt phẳng ra thành các miền, trong đó có thể có cả miền không bị chặng. Ví dụ, biểu diễn phẳng của đồ thị cho trong hình 7 chia mặt phẳng ra thành 6 miền R_1, R_2,. . . .R₆.

Hình 7: Các miền tương ứng với biểu diễn phẳng của đồ thị.

Euler đã chứng minh được rằng các cách biểu diễn phẳng khác nhau của một đồ thị đều chia mặt phẳng ra thành cùng một số miền. Để chứng minh điều đó, Euler đã tìm được mối liên hệ giữa số miền, số đỉnh của đồ thị và số cạnh của đồ thị phẳng sau đây.

Định lý 3 (Công thức Euler). Giả sử G là đồ thị phẳng liên thông với n đỉnh, m cạnh. Gọi r là số miền của mặt phẳng bị chia bởi biểu diễn phẳng của G. Khi đó

r = m-n + 2

Có thể chứng minh định lý bằng qui nạp. Xét Ví dụ minh hoạ cho áp dụng công thức Euler.

Ví dụ 1 Cho G là đồ thị phẳng liên thông với 20 đỉnh, mỗi đỉnh đều có bậc là 3. Hỏi mặt phẳng bị chia làm bao nhiêu phần bởi biểu diễn phẳng của đồ thị G?

Giải. Do mỗi đỉnh của đồ thị đều có bậc là 3, nên tổng bậc của các đỉnh là 3x20=60. Từ đó suy ra số cạnh của đồ thị m=60/20=30. Vì vậy, theo công thức Euler, số miền cần tìm là

r = 30-20+2=12.

Ma trận kề. Ma trận trọng số

Xét đơn đồ thị vô hướng G =(V,E), với tập đỉnh V={1, 2,. . . ,n} , tập cạnh E= {e₁, e₂, . . . ,e_m }. Ta gọi ma trận kề của đồ thị G là ma trận.

A=( a_i,j : i, j = 1, 2, . . . ,n)

Với các phần tử được xác định theo qui tắc sau đây:

a_{i, j} = 0, nếu (i, j) ∈ E và

a_i,j = 1 , nếu (i, j) ∈ E, i, j =1, 2,. . ., n.

Ví dụ 2 Ma trận trận kề của đồ thị vô hướng G cho trong hình 2.8 là:

	1	2	3	4	5	6
1	0	1	1	0	1	0
2	1	0	1	0	1	0
3	1	1	0	1	0	0
4	0	0	1	0	1	1
5	1	1	0	1	0	1
6	0	0	0	1	1	0

Hình 2.8 Đồ thị vô hướng G và Đồ thị có hướng G 1 .

Các tính chất của ma trận kề:

1) Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là

a[i,j]=a[j,i], i,j =1,2,. . .,n. Ngược lại, mỗi (0,1)-ma trận đối xứng cấp n sẽ tương ứng, chính xác đến cách đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đơn đồ thị vô hướng n đỉnh.

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).

3) nếu ký hiệu a_ịj^p , i,j=1, 2,. . . ,n là phần tử của ma trận A^p =A.A. . .A p thừa số. Khi đó a_ịj^p , i,j=1, 2,. . . ,n cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung gian.

Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự.

Ví dụ 3 Đồ thị có hướng G₁ cho trong hình 8 có ma trận kề là ma trận sau:

	1	2	3	4	5	6
1	0	1	1	0	0	0
2	0	0	0	0	0	0
3	0	1	0	1	0	0
4	0	0	0	0	0	0
5	0	0	0	1	0	1
6	0	0	0	0	1	0

Lưu ý rằng ma trận kề của đồ thị có hướng không phải là ma trận đối xứng.

Chú ý: Trên đây chúng ta chỉ xét đơn đồ thị. Ma trận kề của đa đồ thị có thể xây dựng hoàn toàn tương tự, chỉ khác là thay vì ghi 1 vào vị trí a[i,j] nếu (i,j) là cạnh của đồ thị, chúng ta sẽ ghi k là số cạnh nối hai đỉnh i, j.

Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e=(u,v) của đồ thị được gán với một con số c(e) (còn viết là c(u,v) gọi là trọng số của cạnh e. Đồ thị trong trường hợp như vậy được gọi là đồ thị có trọng số. Trong trường hợp đồ thị có trọng số, thay vì mà trận kề, để biểu diễn đồ thị ta sử dụng ma trận trọng số.

C= {c[i,j], i, j = 1, 2,. . ., n}

với   c[i,j]=c(i,j) nếu (i,j) ∈ E và  c[i,j]= δ nếu (i, j) ∉ E

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, + , -.

Ư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 n² đơn vị bộ nhớ để lưu trữ ma trận kề của nó.

Danh sách cạnh (cung)

Trong trường hợp đồ thị thưa (đồ thị có số cạnh m thoả mãn bất dẳng thức: m < 6n) người ta thường dùng cách biểu diễn đồ thị dưới dạng danh sách cạnh.

Trong cách biểu diễn đồ thị bởi 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ột cạnh (cung) e = (x,y) của đồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. như vậy, để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của cách biểu diễn này là để xác định những đỉnh nào của đồ thị là kề với một đỉnh cho trước chúng ta phải làm cỡ m phép so sánh (khi duyệt qua danh sách tất cả các cạnh của đồ thị).

Chú ý: Trong trường hợp đồ thị có trọng số ta cần thêm m đơn vị bộ nhớ để lưu trữ trọng số của các cạnh.

Ví dụ 2.4 Danh sách cạnh (cung) của đồ thị G (G₁) cho trong hình 2.8 là:

Dau	Cuoi		Dau	Cuoi
1	2		1	2
1	3		1	3
1	5		3	2
2	3		3	4
2	5		5	4
3	4		5	6
4	5		6	5
4	6
5	6

Danh sách cạnh của G                                Danh sánh cung của G₁

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 nhất đượ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ó, mà ta sẽ ký hiệu là

Ke(v)= { u ∈ V: (v,u)∈ E }

Khi đó vòng lặp thực hiện với mỗi một phần tử trong danh sách này theo thứ tự các phần tử được sắp xếp trong nó sẽ được viết như sau:

for u ∈ Ke(v) do. . .

Chẳng hạn, trên PASCAL có thể mô tả danh sách này như sau (Gọi là cấu trúc Forward Star):

Const

m=1000; {m-so canh}

n= 100; {n-so dinh}

var

Ke: array[1..m] of integer;

Tro: array[1..n+1] of integer;

Trong đó Tro[i] ghi nhận vị trí bắt đầu của danh sách kề của đỉnh i, i=1, 2,. . .,n, Tro[n+1]=2m+1.

Khi đó dòng lệnh qui ước

for u ∈ Ke(v) do

begin . . . end.

Có thể thay thế bởi cấu trúc lệnh cụ thể trên PASCAL như sau

For i:=Tro[v] to Tro[v+1]-1 do

Begin

U:=Ke[i];

. . . .

End;

Trong rất nhiều thuật toán làm việc với đồ thị chúng ta thường xuyên phải thực hiện các thao tác: Thêm hoặc bớt một số cạnh. Trong trường hợp này cấu trúc dữ liệu dùng ở trên là không thuận tiện. Khi đó nên chuyển sang sử dụng danh sách kề liên kết (Linked Adjancency List) như mô tả trong chương trình nhập danh sách kề của đồ thị từ bàn phím và đưa danh sách đó ra màn hình sau đây:

Program AdjList;

Const

maxV=100;

Type

link=^node;

node=record

v:integer;

next:link;

End;

Var

j,x,y,m,n,u,v:integer;

t:link;

Ke:array[1. .Vmax] of link;

Begin

Write(‘Cho so canh va dinh cua do thi:’); readln(m,n);

(*Khoi tao*)

for j:=1 to n do Ke[j]:=nil;

for j:=1 to m do

begin

write(‘Cho dinh dau va cuoi cua canh ‘,j,’:’);

readln(x,y);

new(t); t^.v:=x, t^.next:=Ke[y]; Ke[y]:=t;

new(t); t^.v:=y, t^.next:=Ke[x]; Ke[x]:=t;

end;

writeln(‘Danh sach ke cua cac dinh cua do thi:’);

for J:=1 to m do

begin

writeln(‘Danh sachcac dinh ke cua dinh ‘,j,’:’);

t:=Ke[j];

while t^.next<>nil do

begin

write(t^.v:4);

t:=t^.next;

end;

end;

readln;

End.

 

Ví dụ 5 Danh sách kề của các đồ thị trong hình 2.8 được mô tả trong hình sau:

Đỉnh đầu

Đỉnh đầu

Hình 2.9 Danh sách kề của đồ thị vô hướng G và có hướng G 1 cho trong hình 2.8.

Để ý rằng trong cách biểu diễn này chúng ta cần phải sử dụng cỡ m+n đơn vị bộ nhớ.

Trong các thuật toán mô tả ở các phần tiếp theo hai cấu trúc danh sách kề và ma trận trọng số được sử dụng thường xuyên.