1.  Cho đồ thị sau: 

_ Áp dụng thuật toán Dijkstra tìm đường đi từ 1 đến 5.

_ Khi nào Kn là đồ thị Euler

2. Áp dụng giải thuật Kruskal tìm cây khung có TLNN:

____ B1: Sắp xếp thứ tự các cạnh theo trọng số tăng dần:

(1,6), (6,7), (4,6), (1,2), (2,7)…

(….1……2…….3…….4……..5)

____ B2 : Khởi đầu: T={(1,6)}, w(J)=w(1,6)=1

____ B3 : Bước lặp: (Ko tạo thành chu trình thì thêm vào, nếu tạo thì bỏ qua)

1)- Với cạnh (6,7) : T U {(6,7)} không tạo thành chu trình. T={(1,6),(6,7)}. w(J)=1+2=3

2)- Với cạnh (4,6) : T U {(4,6)} ko tạo thành chu trình. T={(1,6),(6,7),(4,6)}. w(J)=3+3=6

…

4)- Với cạnh (2,7) : T U {(2,7)} tạo thành chu trình

5)-….

____ B4 : Kết quả : T = {….}. CKNN J trên ĐT có trọng lượng w(J)=26 là : (Vẽ cây khung) 

3. Cho đồ thị có hướng hoặc vô hướng, biểu diễn danh sách liên kết :

4. Biểu diễn đồ thị bằng mà trận:

a) Ma trận đỉnh – cung :

b) Ma trận đỉnh – cạnh :

c) Ma trận kề đỉnh – đỉnh :

_ Có hướng :

_ Vô hướng :

d)  Ma trận trọng số : 

5. Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại :

a). 

b). 

c). Vẽ lại đồ thị xếp hạng :

6. Duyệt cây : 

7. Đồ thị tăng luồng

_ Nếu 3,3 — > Đổi hướng

_ Nếu 3,0 — > Giữ nguyên hướng, chỉ lấy 3

_ Nếu 3,2 — >Số nhỏ quay ngược về (2), hiệu giữ nguyên hướng (1)

8. Đồ thị tăng luồng cực đại :

_Lần lặp thứ 1, thứ 2, …..

_  Val(f) = c(X0,Y0) = c(x6,x7) + c(x2,x5) + c(x4,x5) = 5+4+12 = 21

9. Bài toán thi công :

____* Xác định t(i) :

_ Khởi tạo t(al)=0

_ Xét A : t(A)= max { t(al) + d(al)= 0+0 = 0)=0

_ Xét B : t(B)= max { t(A) + d(A = 0+7=7}= 7

_ Xét C  : t(C)= max {t(B) + d(B)= 7+3 =10}=10

…

_ Xét E : t(E) = max {t(C) + d(C)= 10+1=11 / t(D) + d(D)= 7+8=15} = 15

_ Xét w : t(w) = max {…}=21

____*Xác định T(i) :

_ Khởi tạo T(w) = t(u) = 21

_ Xét K : T(K) : min {T(w) – d(K)=21-1=20} = 20

…

_ Xét C : T(C) = min { T(E) – d(C) = 18-1=17}

………………………….{T(F) – d(C) = 15-1=14}…….=14

…………………………. {T(G) – d(C) = 19-1=18}

_ Xét A : T(A)= min{…}=0

_ Xét al : T(al)=min{..}=0

____*Kết quả là một đồ thị có nhãn như sau :