A. CÂY

1. Định nghĩa

_ Cây là một đồ thị vô hướng LT không có chu trình –> Cây là 1 ĐTVH đơn.

_ Rừng là 1 ĐTVH ko có chu trình –> Rừng thường có nhiều cây.

2. Tính chất

_ T là cây <=> duy nhất 1 đường đi nối 2 đỉnh bất kì của J

_ J=(X,T) là ĐTVH với số đỉnh n>=2 –> Định lý:

……….+ 1. J là cây

……….+ 2. Không có chu trình và có n-1 cạnh

……….+ 3. Liên thông

……….+ 4. Nếu thêm 1 cạnh nối 2 đỉnh bất kì ko kề sẽ xuất hiện chu trình

……….+ 5. Nếu bớt 1 cạnh bất kì sẽ mất tính LT

……….+ 6. Mỗi cặp đỉnh nối với nhau đúng 1 đường đi sơ cấp

3. Cây và rừng trên ĐTVH

_ ĐTVH G=(X,U) (4 đỉnh 6 cạnh)

_ Cây khung (cây bao trùm) : 1 ĐT bộ phận LT ko có chu trình (4 đỉnh 3 cạnh)

–> ĐTVH G có n đỉnh thì cây khung có n đỉnh n-1 cạnh.

_ Định lý Caley: nếu G là ĐTVH đầy đủ n đỉnh (kính cạnh) thì số cây khung trên G là n mũ (n-2)

_ Rừng tối đại  ĐTBP của G ko có chu trình (6 cạhn có hình <->)

_ Tính chất : (vẫn đúng  cho cây khung)
……….+ 1. Nếu G có n đỉnh, p bộ phận liên thông thì RTĐ có đúng n-p cạnh

……….+ 2. Nếu J là RTĐ trên G thì J và G có cùng số BPLT

……….+ 3. G có ĐTBP là cây khung của G <=> G là ĐTLT

……….+ 4. J là RTĐ thì u thuộc T gạch=U-T –> duy nhất 1 chu trình mi mũ u mà các cạnh của nó -(u) đều thuộc T

……….+ 5. ……………. u thuộc T –> ………….. cocycle (-) mũ u mà …………… đều thuộc T gạch = U-T

B. CÂY KHUNG VỚI TLNN

1. _ Tổng trọn lượng khi duyệt qua hết các đỉnh là nhỏ nhất

_ Điều kiện tồn tại : G là ĐTVHLT, J là CK.

………+ ĐL 1 : tồn tại u thuộc T thỏa \-/v (- (-)^u , v#u, w(u) <= w(v)

………+ ĐL 2 : … u … T gạch thỏa : \-/ v (- mi^u, v#u, w(u) >= w(v)

–> Chỉ phụ thuộc vào việc sắp xếp các cạnh theo thứ tự trọng số tăng dần. CKTLNN là duy nhất khi các cạnh có trọng số khác nhau.

2. Giải thuật Fruskal (BT)

3. Giải thật Prim

C. CÂY CÓ HƯỚNG 

1. Định nghĩa

_ J=(X,T) là 1 CCH gốc r thuộc X khi

………+ 1. J ko chứ chu trình vô hướng

………+ 2. Với mỗi i (- X tồn tại trong J 1 đường đi từ r đến i.

_ Gốc : r là gốc nếu tồn tại đường đi nối r với i, \-/ i (- X,  i#r

–> Một đồ thị LT mạnh mọi đỉnh đều là gốc

_ G có gốc <=> G là đồ thị gần LT mạnh

2. Đặc điểm

_ Định lí : J là đồ thị có hướng có n>1 đỉnh. Tương đương :

………+ 1. J là cây có hướng gốc r

………+ 2. E đỉnh r nối với mỗi đỉnh khác = 1 đường đi duy nhất xuất phá từ r

………+ 3. J gần LT mạnh và cực tiểu

………+ 4. J LT và E 1 đỉnh r có bậc trong =0, các đỉnh khác =1

………+ 5. J ko có chu trình và E …………

………+ 6. J gần LT mạnh và ko có chu trình

………+ 7. ……. và có n-1 cung

D. CÂY CÓ HƯỚNG CÓ TLNN

_ Định lý : Nếu J là CCH có TLNN trên G thì J chứa all các cung của chu trình mi ngoại trừ 1 cung nào đó

_ Điều kiện : J1 là CCH có TLNN trên đồ thị G1=G/mi

_ Giải thuật 4 bước.

E. LUỒNG CỰC ĐẠI – LÁT CẮT – TĂNG LUỒNG

1. Mạng

_ G=(X,E) là mạng khi :

………+ 1. E duy nhất s (- X, mà tại s ko có cung đi vào, chỉ có cung đi ra, điểm phát

………+ 2. …..t…. ko có cung đi ra, … đi vào… điểm thu

………+ 3. Mỗi cung e(i,j) gán giá trị ko âm, gọi là khả năng thông qua

–> Nếu không tồn tại cung -> khả năng thông qua = 0

2. Luồng trong mạng

_ Kí hiệu : val(f).

_ ĐK cân bằng : tổng luồng đi vào = đi ra

3. Lát cắt

_ ĐN : mỗi cung bất kì có gốc và ngọn ko cùng thuộc 1 bộ phận

_ Cung thuận : vừa là cung của ĐTTL Gf vừa là cung mạng G. Ngược lại là cung nghịch

_ Đường tăng luồng : Mọi đường đi trên ĐTLT từ điểm phát s đến thu t.