Bài giảng Lý thuyết đồ thị - Chương 3: Các thuật toán duyệt đồ thị

Chương 3 Các Thuật Toán Duyệt Đồ Thị (Graph Searching, Graph Traversal)

Các thuật toán duyệt đồ thị

• Duyệt đồ thị: Graph Searching hoặc Graph Traversal

• Ứng dụng:

• Duyệt qua mỗi đỉnh và mỗi cạnh của đồ thị

• Cần để khảo sát các tính chất của đồ thị

• Hai thuật toán duyệt cơ bản:

• Là thành phần cơ bản của nhiều thuật toán trên đồ thị

• Tìm kiếm theo chiều rộng (Breadth First Search – BFS)

• Tìm kiếm theo chiều sâu (Depth First Search – DFS)

Ý tưởng chung của các thuật toán duyệt

Ý tưởng chung: • Trong quá trình thực hiện thuật toán, mỗi đỉnh ở một trong ba trạng thái:

• Chưa thăm, thể hiện bởi màu trắng • Đã thăm (nhưng chưa duyệt xong), thể hiện bởi màu xám • Đã duyệt xong, thể hiện bởi màu đen

• Trạng thái của đỉnh sẽ biến đổi theo qui tắc sau:

• Thoạt đầu mỗi đỉnh đều có màu trắng (chưa thăm - not visited). • Đỉnh đã được thăm sẽ chuyển thành màu xám (trở thành đã thăm nhưng chưa duyệt

xong - visited).

• Khi tất cả các đỉnh kề của một đỉnh v là đã được thăm, đỉnh v sẽ có màu đen (đã

duyệt xong – discovered).

Tìm kiếm theo chiều rộng Breadth-first Search (BFS)

Tìm kiếm theo chiều rộng Breadth-first Search

• Input: Đồ thị G = (V, E), vô hướng hoặc có hướng.

• Output:

• d[v] = khoảng cách (độ dài của đường đi ngắn nhất) từ s (là đỉnh xuất phát tìm kiếm) đến v, với mọi v  V. d[v] =  nếu v không đạt tới được từ s.

• [v] = u đỉnh đi trước v trong đường đi từ s (là đỉnh xuất phát

tìm kiếm) đến v có độ dài d[v].

• Xây dựng cây BFS với gốc tại s chứa tất cả các đỉnh đạt tới được

từ s.

Procedure BFS(s); Procedure BFS(s); (* Tìm kiếm theo chiều rộng bắt đầu từ đỉnh s *)

begin

color[s]  gray; d[s]  0; [s]  nil; Q  ; enqueue(Q,s); (* Nạp s vào Q *) while Q   do begin

Trắng: chưa thăm xám: đã thăm đen: đã duyệt xong

u  dequeue(Q); (* Lấy u từ Q *) for v Adj[u] do

if color[v] = white then begin

color[v]  gray; d[v]  d[u] + 1; [v]  u; enqueue(Q,v) (* Nạp v vào Q *)

end;

Q: hàng đợi các đỉnh được thăm color[v]: màu của đỉnh v d[v]: khoảng cách từ s đến v [u]: đỉnh đi trước v

color[u]  black

end;

end; BEGIN (* Main Program*)

Ví dụ: xem minh hoạ

for v  V do (* Khởi tạo *) begin

color[v]  white; d[v]  ; [v]  nil;

end; for v  V do

if color[v]=white then BFS(v);

END.

Ví dụ (BFS)

r  t  u  0

 

 v  w y x

Q: s 0

Ví dụ (BFS)

r s

t  u  0 1

 

 v 1 w y x

Q: w r 1 1

Ví dụ (BFS)

r s

u  t 2 0 1

 2

 v 1 w y x

Q: r t x 1 2 2

Ví dụ (BFS)

r s

u  t 2 0 1

 2

2 v 1 w y x

Q: t x v 2 2 2

Ví dụ (BFS)

r s

t 2 u 3 0 1

 2

2 v 1 w y x

Q: x v u 2 2 3

Ví dụ (BFS)

r s

t 2 u 3 0 1

2 v 1 w 3 y x

Q: v u y 2 3 3

Ví dụ (BFS)

r s

t 2 u 3 0 1

2 v 1 w 3 y x

Q: u y 3 3

Ví dụ (BFS)

r s

t 2 u 3 0 1

2 v 1 w 3 y x

Q: y 3

Ví dụ (BFS)

r s

t 2 u 3 0 1

2 v 1 w 3 y x

Q: 

Ví dụ (BFS)

r s

t 2 u 3 0 1

2 v 1 w 3 y x

Cây BFS(s)

Phân tích BFS

• Việc khởi tạo đòi hỏi O(|V|). • Vòng lặp duyệt

• Mỗi đỉnh được nạp vào và loại ra khỏi hàng đợi một lần, mỗi thao tác đòi hỏi thời gian O(1). Như vậy tổng thời gian làm việc với hàng đợi là O(V).

là O(|V|+|E|),là tuyến tính theo kích thước của danh sách kề biểu diễn đồ thị.

• Danh sách kề của mỗi đỉnh được duyệt qua đúng một lần. Tổng độ dài của tất cả các danh sách kề là (|E|). • Tổng cộng ta có thời gian tính của BFS(s)

Cây BFS(s)

• Đối với đồ thị G = (V, E) và đỉnh s. Thực hiện BFS(s), xét đồ thị con

• V={vV : [v] NIL}{s} • E={([v],v) E : v  V \ {s}}

G= (V, E) trong đó

• G= (V, E) là cây và được gọi là cây BFS(s) • Các cạnh trong Eđược gọi là cạnh của cây. |E| = |V| - 1. • BFS(s) cho phép đến thăm tất cả các đỉnh đạt tới được từ s. • Trình tự thăm các đỉnh khi thực hiện BFS(s): Đầu tiên đến thăm các đỉnh đạt được từ s bởi đường đi qua 1 cạnh, sau đó là thăm các đỉnh đạt được từ s bởi đường đi qua 2 cạnh, …Do đó nếu đỉnh t được thăm trong BFS(s) thì nó sẽ được thăm theo đường đi ngắn nhất theo số cạnh.

BFS – Loang trên đồ thị

• Thứ tự thăm đỉnh nhờ thực hiện BFS(A)

L0

L1

L2

Ứng dụng trực tiếp cuả BFS

• Sử dụng BFS để kiểm tra tính liên thông của đồ thị vô

hướng:

• Mỗi lần gọi đến BFS ở trong chương trình chính sẽ sinh ra

• Xét sự tồn tại đường đi từ đỉnh s đến đỉnh t:

một thành phần liên thông

• Thực hiện BFS(s). • Nếu [t] = NIL thì không có đường đi, trái lại ta có đường đi

• Chú ý: BFS tìm được đường đi ngắn nhất theo số cạnh.

t  [t]  [[ t]]  . . .  s

Tìm kiếm theo chiều sâu Depth-first Search (DFS)

Ý tưởng của tìm kiếm theo chiều sâu

• Ta sẽ bắt đầu tìm kiếm từ một đỉnh s nào đó của đồ thị. Sau đó chọn u là một đỉnh tuỳ ý kề với s và lặp lại quá trình đối với u.

• Ở bước tổng quát, giả sử ta đang xét đỉnh v: • Nếu như trong số các đỉnh kề với v tìm được đỉnh w là chưa được thăm thì ta sẽ thăm đỉnh này (nó sẽ trở thành đã thăm nhưng chưa duyệt xong) và bắt đầu từ nó ta sẽ tiếp tục quá trình tìm kiếm.

• Nếu như không còn đỉnh nào kề với v là chưa thăm thì ta sẽ nói rằng đỉnh này là đã duyệt xong và quay trở lại tiếp tục tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh v (nếu v = s, thì kết thúc tìm kiếm).

• Có thể nói nôm na là tìm kiếm theo chiều sâu bắt đầu từ đỉnh s được thực hiện trên cơ sở tìm kiếm theo chiều sâu từ tất cả các đỉnh chưa thăm kề với s.

Mô tả DFS

• Input: Đồ thị G = (V, E) cho bởi danh sách kề

• Output:

• 2 mốc thời gian cho mỗi đỉnh (là các số nguyên trong khoảng 1

và 2|V|).

• d[v] = thời điểm bắt đầu thăm (v chuyển từ trắng sang

xám)

• f [v] = thời điểm kết thúc thăm (v chuyển từ xám sang đen)

• [v] : đỉnh đi trước v – tức là đỉnh mà từ đó ta đến thăm v.

• Sử dụng biến color để ghi nhận trạng thái của các đỉnh như đã mô

tả.

Depth-First Search: Code

procedure DFS(u);

DFS(G)

begin

BEGIN

color[u] = GRAY;

for vV do

time = time+1;

begin

d[u] = time;

color[v] = WHITE;

for v  Ke(u)do

[v] = NIL

if (color[v]= WHITE)then

end;

begin

time = 0;

[v] = u;

for uV do

DFS(v);

begin

end;

if (color[u]= WHITE) then

color[u] = BLACK;

DFS(u);

time = time+1;

end;

f[u] = time;

END.

end;

Phân tích thuật toán DFS

• Mỗi đỉnh được thăm đúng 1 lần, việc thăm mỗi đỉnh đòi hỏi chi phí thời gian O(1), suy ra thao tác thăm đỉnh đòi hỏi thời gian O(|V|).

• Mỗi cạnh được duyệt qua đúng một lần nếu đồ thị là có hướng và 2 lần

nếu đồ thị là vô hướng

• Như vậy tổng số lần lặp là O(|E|).

• Vòng lặp trong DFS(u) thực hiện việc duyệt cạnh của đồ thị

• Vậy, thuật toán có thời gian O(|V|+|E|)

• Đối với đồ thị, thuật toán có đánh giá như vậy gọi là thuật toán

thời gian tuyến tính

Ví dụ: DFS

Đỉnh xuất phát tìm kiếm (Source vertex)

Để hoạt động của thuật toán là xác định, giả thiết rằng ta duyệt các đỉnh trong danh sách kề của một đỉnh theo thứ tự từ điển

Ví dụ: DFS

source vertex

d[v] f[v]

1 | | |

| |

| | |

Ví dụ: DFS

source vertex

1 | | |

2 | |

| | |

Ví dụ: DFS

source vertex

1 | | |

2 | |

3 | | |

Ví dụ: DFS

source vertex

1 | | |

2 | |

3 | 4 | |

Ví dụ: DFS

source vertex

1 | | |

2 | |

3 | 4 | 5 |

Ví dụ: DFS

source vertex

1 | | |

2 | |

| 3 | 4 5 | 6

Ví dụ: DFS

source vertex

1 | | 8 |

2 | 7 |

| 3 | 4 5 | 6

Ví dụ: DFS

source vertex

1 | | 8 |

2 | 7 |

| 3 | 4 5 | 6

Ví dụ: DFS

source vertex

1 | 8 | |

2 | 7 9 |

| 3 | 4 5 | 6

Ví dụ: DFS

source vertex

1 | | 8 |

2 | 7 9 |10

| 3 | 4 5 | 6

Ví dụ: DFS

source vertex

1 | 8 |11 |

2 | 7 9 |10

| 3 | 4 5 | 6

Ví dụ: DFS

source vertex

1 |12 8 |11 |

2 | 7 9 |10

3 | 4 5 | 6 |

Ví dụ: DFS

source vertex

1 |12 8 |11 13|

2 | 7 9 |10

3 | 4 5 | 6 |

Ví dụ: DFS

source vertex

1 |12 8 |11 13|

2 | 7 9 |10

3 | 4 5 | 6 14|

Ví dụ: DFS

source vertex

1 |12 8 |11 13|

2 | 7 9 |10

3 | 4 5 | 6 14|15

Ví dụ: DFS

source vertex

1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

DFS: Các loại cạnh

• DFS(G) sinh ra một cách phân loại các cạnh của đồ thị đã cho:

• Cạnh của cây (Tree edge): là cạnh mà theo đó từ một đỉnh ta đến

thăm một đỉnh mới (cạnh đi vào đỉnh trắng)

• Các cạnh này tạo thành một rừng gọi là rừng tìm kiếm DFS.

• Các đỉnh được thăm khi thực hiện DFS(v) và các cạnh của cây tạo thành

cây được gọi là cây DFS(v)

Ví dụ: Rừng DFS

Cây DFS(g)

source vertex a

Cây DFS(a)

1 |12 8 |11 13|16

source vertex g

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges

DFS: Cạnh ngược

• DFS tạo ra một cách phân loại các cạnh của đồ thị đã cho:

• Cạnh của cây (Tree edge): là cạnh mà theo đó từ một đỉnh ta đến thăm một

đỉnh mới (cạnh đi vào đỉnh trắng)

• Cạnh ngược (Back edge): đi từ con cháu (descendent) đến tổ tiên (ancestor)

• Đi vào đỉnh xám (đi từ đỉnh xám đến đỉnh xám)

Ví dụ: DFS Cạnh ngược

source vertex

1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

c Tree edges Back edges

DFS: Cạnh tới

• DFS tạo ra một cách phân loại các cạnh của đồ thị đã cho:

• Cạnh của cây (Tree edge): là cạnh mà theo đó từ một đỉnh ta đến thăm một

đỉnh mới (cạnh đi vào đỉnh trắng)

• Không là cạnh của cây • Đi từ đỉnh xám đến đỉnh đen

• Cạnh ngược (Back edge): đi từ con cháu (descendent) đến tổ tiên (ancestor) • Cạnh tới (Forward edge): đi từ tổ tiên đến con cháu

Ví dụ: DFS Cạnh tới

source vertex

1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges Back edges Forward edges

DFS: Cạnh vòng

• DFS tạo ra một cách phân loại các cạnh của đồ thị đã cho:

• Cạnh của cây (Tree edge): là cạnh mà theo đó từ một đỉnh ta đến thăm một

đỉnh mới (cạnh đi vào đỉnh trắng)

• Không là cạnh của cây, và giống như cạnh vòng cũng • Đi từ đỉnh xám đến đỉnh đen

• Cạnh ngược (Back edge): đi từ con cháu (descendent) đến tổ tiên (ancestor) • Cạnh tới (Forward edge): đi từ tổ tiên đến con cháu • Cạnh vòng (Cross edge): cạnh nối hai đỉnh không có quan hệ họ hàng

Ví dụ: DFS Cạnh vòng

source vertex

1 |12 8 |11 13|16

2 | 7 9 |10

3 | 4 5 | 6 14|15

Tree edges Back edges Forward edges Cross edges

DFS: Các loại cạnh

• DFS tạo ra một cách phân loại các cạnh của đồ thị đã cho: • Tree edge: cạnh theo đó từ một đỉnh đến thăm đỉnh mới (trắng)

• Back edge: đi từ con cháu đến tổ tiên

• Forward edge: đi từ tổ tiên đến con cháu

• Chú ý: Cạnh của cây & cạnh ngược là quan trọng; nhiều thuật toán

không đòi hỏi phân biệt cạnh tới và cạnh vòng

• Cross edge: giữa hai đỉnh không có họ hàng

DFS: Các loại cạnh

• Định lý: Nếu G là đồ thị vô hướng, thì DFS chỉ sản sinh ra cạnh của cây và cạnh ngược.

source

F?

• Chứng minh bằng phản chứng: • Giả sử có cạnh tới (forward edge)

• Nhưng khi đó F phải là cạnh ngược (back

edge)?!

DFS: Các loại cạnh

• Giả sử có cạnh vòng (cross edge)

source

• Khi đó C không thể là cạnh vòng bởi vì: • Nó phải được khảo sát từ một trong hai đỉnh đầu mút và trở thành cạnh của cây trước khi đỉnh kia được khảo sát

• Do đó bức tranh bên là không đúng…cả hai

cạnh bên không thể là cạnh của cây

C?

DFS: Phân biệt các loại cạnh

• Dễ dàng phân biệt các loại cạnh nhê ph©n tÝch mµu cña c¸c ®Ønh vµ/hoÆc xÐt c¸c gi¸ trÞ cña c¸c mèc thêi gian d vµ f. •

1. WHITE cho biết e là cạnh của cây

2. GRAY cho biết e là cạnh ngược

3. BLACK cho biết e là cạnh tới hoặc vòng

Khi ta duyệt cạnh e=(u, v) từ đỉnh u, căn cứ vào màu của v ta có thể biết cạnh này thuộc loại cạnh nào:

Phân tích DFS

(* Main Program*)

1. for u V do

2. color[u]  white

3. [u]  NIL

color[u]  GRAY (* Thăm đỉnh u *) time  time + 1 d[u]  time for each v  Adj[u] do

4. time  0

5. for u V do

if color[v] = WHITE then [v]  u

6. if color[u] = white

DFS-Visit(v)

7. then DFS-Visit(u)

DFS-Visit(u) 1. 2. 3. 4. 5. 6. 7. 8.

color[u]  BLACK (* Đỉnh u đã duyệt xong *) f[u]  time  time + 1

Các biến time, color,  là toàn cục .

Phân tích DFS

• Vòng lặp trên các dòng 1-2 và 5-7 đòi hỏi thời gian (|V|), chưa

tính thời gian thực hiện lệnh DFS(v).

• DFS(v) thực hiện đối với mỗi đỉnh trắng vV và ngay sau khi được thăm nó được tô màu xám. Các dòng 3-6 của DFS(v) sẽ thực hiện |Adj[v]| lần. Vậy thời gian tổng cộng của DFS(v) là vV|Adj[v]| = (|E|)

• Do đó thời gian của DFS là (|V|+|E|). • Thuật toán trên đồ thị có đánh giá thời gian như trên gọi là thuật

toán thời gian tuyến tính

CÁC ỨNG DỤNG CỦA DFS

•Tính liên thông của đồ thị •Tìm đường đi từ s đến t • Phát hiện chu trình • Kiểm tra tính liên thông mạnh • Định hướng đồ thị

Bài toán về tính liên thông

• Bài toán: Cho đồ thị vô hướng G = (V,E). Hỏi đồ thị gồm bao nhiêu thành phần liên thông, và từng thành phần liên thông gồm các đỉnh nào?

• Giải: Sử dụng DFS (BFS) :

• Mỗi lần gọi đến DFS (BFS) ở trong chương trình chính sẽ sinh

ra một thành phần liên thông

DFS giải bài toán liên thông

(* Main Program*)

1. for u V do

2. id[u]  0

id[u]  cnt for each v  Adj[u] do if id[v] = 0

3. cnt  0 (* cnt – số lượng tplt *)

DFS-Visit(u) 1. 2. 3. 4.

then DFS-Visit(v)

4. for u V do

5. if id[u] = 0

6. then cnt  cnt +1

DFS-Visit(u)

Tìm đường đi

• Bài toán tìm đường đi

• Input: Đồ thị G = (V,E) xác định bởi danh sách kề và hai đỉnh s,

• Đầu ra: Đường đi từ đỉnh s đến đỉnh t, hoặc khẳng định

• Thuật toán: Thực hiện DFS(s) (hoặc BFS(s)).

không tồn tại đường đi từ s đến t.

• Nếu [t] = NIL thì không có đường đi, trái lại ta có đường đi

t  [t]  [[ t]]  . . .  s

DFS giải bài toán đường đi

(* Main Program*)

1. for u V do

color[u]  GRAY (* Thăm đỉnh u *) for each v  Adj[u] do

2. color[u]  white

3. [u]  NIL

if color[v] = WHITE then [v]  u

4. DFS-Visit(s)

DFS-Visit(u) 1. 2. 3. 4. 5.

DFS-Visit(v)

DFS và Chu trình

• Bài toán: Cho đồ thị G=(V,E). Hỏi G có chứa chu trình hay không? • Định lý: Đồ thị G là không chứa chu trình khi và chỉ khi trong quá

trình thực hiện DFS ta không phát hiện ra cạnh ngược.

• Nếu G không chứa chu trình thì rõ ràng không có cạnh ngược (bởi vì sự tồn

tại cạnh ngược dẫn đến phát hiện chu trình)

• Nếu không có cạnh ngược thì G là không chứa chu trình (acyclic). Thực vậy

• Không có cạnh ngược tức là chỉ có cạnh của cây • Nếu chỉ có cạnh của cây thì G chỉ là cây hoặc rừng • Vậy G không chứa chu trinh

• Chứng minh:

• Như vậy DFS có thể áp dụng để giải bài toán đặt ra.

DFS và chu trình

• Cần phải điều chỉnh như thế nào để phát hiện chu trình?

(* Main Program*)

1. for u V do

2. color[u]  white

3. [u]  NIL

color[u]  GRAY (* Thăm đỉnh u *) time  time + 1 d[u]  time for each v  Adj[u] do

4. time  0

5. for u V do

if color[v] = WHITE then [v]  u

6. if color[u] = white

DFS-Visit(v)

7. then DFS-Visit(u)

DFS(u) 1. 2. 3. 4. 5. 6. 7. 8.

color[u]  BLACK (* Đỉnh u đã duyệt xong *) f[u]  time  time + 1

DFS và chu trình

• Câu hỏi: Thời gian tính là bao nhiêu? • Trả lời: Chính là thời gian thực hiện DFS: O(|V|+|E|). • Câu hỏi: Nếu G là đồ thị vô hướng thì có thể đánh giá thời gian tính

sát hơn nữa được không?

• Trả lời: Thuật toán có thời gian tính O(|V|), bởi vì:

• Trong một rừng (đồ thị không chứa chu trình) |E|  |V| - 1

• Vì vậy nếu đồ thị có |V| cạnh thì chắc chắn nó chứa chu trình, và thuật toán

kết thúc.

Kiểm tra tính liên thông mạnh

• Bài toán: Hỏi đồ thị có hướng G có là liên thông mạnh? • Mệnh đề: Đồ thị có hướng G=(V,E) là liên thông mạnh khi và chỉ khi luôn tìm được đường đi từ một đỉnh v đến tất cả các đỉnh còn lại và luôn tìm được đường đi từ tất cả các đỉnh thuộc V \ {v} đến v.

• Chứng minh: Hiển nhiên

Thuật toán kiểm tra tính liên thông mạnh

• Thuật toán. • Chọn v  V là một đỉnh tuỳ ý • Thực hiện DFS(v) trên G. Nếu tồn tại đỉnh u không được thăm

thì G không liên thông mạnh và thuật toán kết thúc. Trái lại thực hiện tiếp

• Thực hiện DFS(v) trên GT = (V, ET), với ET thu được từ E bởi việc đảo ngược hướng các cung. Nếu tồn tại đỉnh u không được thăm thì G không liên thông mạnh, nếu trái lại G là liên thông mạnh.

• Thời gian tính: O(|V|+|E|)

Thuật toán kiểm tra tính liên thông mạnh

a a d d a d

f f f c c c

Đồ thị G

Đồ thị GT

b b e e b e

Định hướng đồ thị

• Bài toán: Cho đồ thị vô hướng liên thông G= (V, E). Hãy tìm cách định hướng các cạnh của nó để thu được đồ thị có hướng liên thông mạnh hoặc trả lời G là không định hướng được.

• Thuật toán định hướng : Trong quá trình thực hiện DFS(G)

định hướng các cạnh của cây DFS theo chiều từ tổ tiên đến con cháu, các cạnh ngược theo hướng từ con cháu đến tổ tiên. Ký hiệu đồ thị thu được là G()

• Bổ đề. G là định hướng được khi và chỉ khi G() là liên

thông mạnh.

Ví dụ: Định hướng đồ thị

d a a a d

f f c c

Đồ thị G

Đồ thị G()

b e b e

Bài tập chương 1 Đồ thị

Hai đồ thị sau có đẳng cấu với nhau hay không?

A’

E’

B’

D’

C’

Ví dụ:

Hai đơn đồ thị G1 và G2 sau là đẳng cấu qua phép đẳng cấu f: a x, bu, cz, dv, ey:

Ví dụ:

• Hai đồ thị G1 và G2 sau đều có 5 đỉnh và 6 cạnh nhưng không đẳng cấu vì trong G1 có một đỉnh bậc 4 mà trong G2 không có đỉnh bậc 4 nào.

Ví dụ:

• Hai đồ thị G1 và G2 đều có 7 đỉnh, 10 cạnh, cùng có một đỉnh bậc 4, bốn đỉnh bậc 3 và hai đỉnh bậc 2. Tuy nhiên G1 và G2 là không đẳng cấu vì hai đỉnh bậc 2 của G1 (a và d) là không kề nhau, trong khi hai đỉnh bậc 2 của G2 (y và z) là kề nhau.

Ví dụ:

• Hãy xác định xem hai đồ thị sau có đẳng cấu hay không?

Ví dụ:

• Tìm đỉnh cắt (đỉnh khớp), cạnh cắt

(cạnh cầu)

Bài tập

• Hãy vẽ các đồ thị vô hướng được biểu diễn bởi ma trận liền kề

Bài tập

1. Nêu ý nghĩa của tổng các phần tử trên một hàng (t.ư. cột) của một ma trận liền kề đối với một đồ thị vô hướng ? Đối với đồ thị có hướng ?

Các đồ thị G và G’ sau có đẳng cấu với nhau không?

Bài tập

• Tìm ma trận liền kề cho các đồ thị sau:

• Một đồ thị bánh xe Wn có 36 cạnh. Tìm số đỉnh của đồ thị? • Cho đồ thị G= (V,E) có 10 đỉnh, mỗi đỉnh có bậc bằng 6. Tìm số

cạnh của đồ thị?

• Đồ thị nào có kích thước ma trận liên kề bằng ma trận liên

thuộc.(vẽ hình minh họa)

Bài tập

• Đồ thị vòng có phải là đồ thị phân đôi không? Giải thích, vẽ hình minh

họa?

Cho biết tên gọi của đồ thị?

Vẽ đồ thị với ma trận liền kề dưới đây.

Vẽ đồ thị bù của đồ thị sau:

Bài tập

• Đồ thị nào là đồ thị Hamilton?

Bài tập

• Đồ thị có chu trình (đường đi) Hamilton?

Bài tập

• Với giá trị nào của m và n các đồ thị phân đôi đầy đủ Km,n có

chu trình Hamilton?

• Vẽ chu trình Hamilton của đồ thị lập phương Q3? • Tìm đường đi Hamilton trong hình vẽ?

Bài tập

• Trong các đồ thị liên thông sau, đồ thị nào chứa chu trình

Hamilton

Cho các đồ thị có hướng như hình vẽ, đồ thị nào có đường đi Euler :

Cho các đồ thị vô hướng như hình vẽ, đồ thị nào là đồ thị Euler :

Có bao nhiêu đỉnh có bậc chẳn?

Có bao nhiêu đỉnh có bậc lẻ?

• Đồ thị đầy đủ Kn cũng chính là chu trình vòng Cn khi nào? • Một chu trình vòng Cn là đồ thị phân đôi khi n=? • Đồ thị nào không có tất cả các đỉnh cùng bậc? • Điều kiện nào để đồ thị đầy đủ Kn có đường đi Euler nhưng

không có chu trình Euler?

•