A. CÁC KHÁI NIỆM CƠ BẢN

1. Đồ thị có hướng  và ánh xạ

_ Đồ thị G=(X,U) : X là đỉnh, n đỉnh–>G bậc n. U là cung. Cung u=(i,j) có gốc i ngọn j.

_ Khuyên : gốc và ngọn trùng nhau.

_ Đỉnh treo : Đỉnh có 1 cung duy nhất đi tới. Cung treo cung duy nhất đi tới đỉnh treo. Đỉnh cô lập : không có cung đi ra và đi vô.

_ Ánh xạ : Kí hiệu : X |-> Tx={…} gồm các đỉnh mũi tên từ X chỉ tới. (T(-1)x : là các đỉnh có mũi tên chỉ tới X.

2. Đồ thị vô hướng

_ Đa ĐTVH : ĐTVH có nhiều cạnh nối hai đỉnh phân biệt bất kì.

_ Đồ thị đơn vô hướng : ĐTVH không có khuyên và không có quá 1 cạnh nối 2 đỉnh bất kì.

3. Các khái niệm khác:

_ Đỉnh kề : có cung/cạnh chung. _ Cung kề – Cạnh kề : có đỉnh chung.

_ Bậc của đỉnh x kí hiệu : d(x) là số cung/cạnh chứa x.

_ Nửa bậc trong kí hiệu d-(x) là số cung có ngọn là x. Nửa bậc ngoài kí hiệu d+(x) là số cung có gốc là x. —> d(x)=d-(x)+d+(x)

_ (-)(A) : w+(A) tập các cung có gốc thuộc A và ngọn không thuộc A (ra A). w-(A) là các cung có ngọn thuộc A và gốc không thuộc A (vào A). (-)(A)=w+(A)+w-(A) là tập hợp cung có một đỉnh chung với A.

_ ĐT đối xứng : ĐTCH mà với mọi cặp đỉnh i, j số cung từ i->j = số cung từ j->i. Đồ thị bất đối xứng : ĐTCH tồn tại hai đỉnh i và j mà số cung i->j # j->i.

_ ĐT đầy đủ : Luôn tồn tại cạnh nối 2 đỉnh bất kì của nó (Ngôi sao đầy)

_ ĐT con : A con của X, GA có đỉnh là A có cung là cung của G  mà đỉnh thuộc A. (Ngôi sao có 1 đỉnh chỉ có cung gạch gạch)

_ ĐT bộ phận : V con U, đồ thị có đỉnh là X, cạnh là V. (Ngôi sao liền vòng ngoài, ở trong gạch gạch)

_ ĐT bộ phận con : vừa là đồ thị con vừa là đồ thị bộ phận.

B. BIỂU DIỄN ĐỒ THỊ

_Ma trận đỉnh cung : 0: Không là gốc, ko là ngọn. 1là gốc. -1 là ngọn (Có mũi tên)

_Ma trận cạnh : 0:  x ko thuộc cung u. 1 thuộc cung u. (Chỉ là cạnh)

_ Ma trận kề đỉnh – đỉnh : 0 : cung (i,j) ko thuộc U. 1 thuộc U.

_  Ma trận trọng số : Đứng là gốc, ngang là ngọn, trong là cung.

C. ĐƯỜNG ĐI VÀ CHU TRÌNH

1. Vô hướng

_ Đường đi : một dãy các cạnh kề nhau (Có thể trùng). Đường đi sơ cấp :  Các đỉnh khác nhau từng đôi một (Không trùng).

_ Chu trình : đỉnh đầu và đỉnh cuối trùng nhau (Qua tất cả các đỉnh đến đỉnh đầu). Chu trình sơ cấp : Đỉnh khác nhau từng đôi một, trừ đỉnh đầu và đỉnh cuối (Chu trình chừa ra 1 đỉnh bất kì).

2. Có hướng

_ Đường đi : dãy liên tiếp các cung, ngọn của cung thứ nhất là gốc của cung thứ 2. Đường đi sơ cấp : đường đi các đỉnh khác nhau từng đôi một.

_ Chu trình : đường đi mà đỉnh đầu và đỉnh cuối trùng nhau. …

D. ĐỒ THỊ LIÊN THÔNG

1. Vô hướng

_ ĐTLT : mỗi cặp đỉnh (i,j) bất kì luôn tìm được đường đi nối i và j, cũng là đường nối j và i.

_ Bộ phận liên thông : Tập hợp các bộ phận ko liên kết của đồ thị

……………+ G là ĐTLT khi và chỉ khi G chỉ có 1 bộ phân LT

……………+ Mỗi bộ phận liên thông là một bộ phận liên thông.

……………+ Mỗi đỉnh cô lập là 1 bộ phận liên thông.

2. Có hướng

_ ĐT có hướng LT : LT yếu nếu đtvh tương ứng với G liên thông. LT một chiều : i, j bất kì luôn có đường đi. LT mạnh : i,j bất kì tồn tại đường đi đi từ i đến j.

_ Bộ phận LT : Những bộ phận con sinh ra bởi các lớp tường đương.

……………+ G là  ĐTLT mạnh khi G có một bộ phận LT

……………+ Mỗi bộ phận LT là một ĐTLT mạnh

……………+ Mỗi đỉnh cô lập là 1 bphận LT

E. ĐỒ THỊ EULER

1. Định nghĩa

_ G = (U,X) là ĐT hữu hạn LT

_ Đồ thị Euler : Một chu trình trên G đi qua tất cả các cạnh/cung của G và mỗi cạnh đứng một lần. Chu trình Euler : ĐT G chứa chu trình Euler. (Mỗi đỉnh chỉ qua 1 lần)

_ ĐT nửa Euler giống với ĐT Euler, chỉ khác chỗ chu trình # đường đi

==> Mọi đồ thị Euler đều là đồ thị nửa Euler.

2. Định lý

_ ĐL euler : G là ĐTVH hữu hạn LT, G là ĐT Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn (1 đỉnh chỉ ở giữa 2 cạnh)

_ Hệ quả : G là … G có ko quá 2 đỉnh có bậc lẻ.

_ Định lý : G là … bậc trong và bậc ngoài của 1 đỉnh là = nhau

3. Xác định chu trình Euler

_ 3 bước : 1. LT hay không. 2. Bậc chẵn hay không. 3. ghép chu trình đơn

F. ĐƯỜNG ĐI NGẮN NHẤT

_ u=(i,j) –> l(u) hay lij thuộc R là độ dài cung hay trọng số của cung

_ Độ dài cung, độ dài đường đi có thể là một số <=0

_Điều kiện tồn tại : mọi đường đi từ i đến j không chứa chu trình và khuyên có độ dài âm thì tồn tại dđnn từ i đến j

_ Liên hệ giữa các độ dài : l(uij)=l(u’)+l(w). l(w)<0 không tồn tại dđnn.

1. Giải thuật Moore – Dijkstra : từ đỉnh s cho trước đến các đinh còn lại (Có nhánh)

2. Đồ thị xếp hạng : ĐT có hướng ko có chu trình

G. BÀI TOÁN TỔ CHỨC THI CÔNG

_ Gant : G=(X,U), X là công việc, U là thời gian. G không có chu trình.

…………….+ Tồn tại cv mà trước đó ko có cv – đỉnh có tạo ảnh là tập rỗng

…………….+ Tồn tại ………. sau ……………… – đỉnh có ảnh là tập rỗng (Trước là tạo ảnh, sau là ảnh)