Tài Liệu bồi dưỡng hay

Phần 1 : Khái niệm chung

I / Định nghĩa đồ thị :

Đồ thị gồm tập hợp X và một ánh xạ F từ X vào X ( ánh xạ này có thể đa trị ). Kí hiệu đồ thị là G(X,F) .

Thí dụ : Trong mặt phẳng , hình ảnh hình học của đồ thị có thể như :
+ Tập X : tập điểm ( gọi là tập đỉnh của đồ thị )
+ ánh xạ F biểu hiện như tập cung U ( có hướng hoặc vô hướng )

Cung nối đỉnh xi với đỉnh xk kí hiệu là u i k .
Đỉnh xi gọi là đỉnh gốc , đỉnh xk gọi là đỉnh ngọn của cung uik . Cung nối 1 đỉnh với chính đỉnh ấy gọi là cung khuyên .
Đỉnh treo là đỉnh chỉ có 1 cung nối với nó , cung này cũng gọi là cung treo
Đỉnh cô lập là đỉnh không có cung nào nối với nó .
Tập hợp các cung của một đồ thị kí hiệu là U , thì đồ thị ký hiệu là G(X,U)

Ma trận kề của đồ thị ( có N đỉnh ) là ma trận A(N,N) được tạo như sau :
Nếu có s cung nối đỉnh i với đỉnh k thì A[i,k] = s ( thông thường s=1 ) . Nếu không có cung nào nối thì A[i,k]=0


0
0
1
1
0
0
0

0
0
1
0
0
0
1

1
1
0
1
0
0
0

1
0
1
0
1
0
0

0
0
0
1
0
0
0

0
0
0
0
1
0
0

0
1
0
0
0
0
0


Trong ma trận A(7,7) qui định A[i,i]=0 (i=1..7)




II / Phân loại đồ thị :

Cách phân loại theo số cung S nối 2 đỉnh : nếu S = 0..1 thì có đơn đồ thị , nếu S>1 có đa đồ thị
Cách phân loại theo cung có hướng và vô hướng :
+ Trong đồ thị có hướng qui định chiều đi trên cung từ đỉnh gốc đến đỉnh ngọn.
+ Trong đồ thị vô hướng không phân biệt chiều đi trên cung ( nghĩa là không định hướng trên cung ). Khi đó trong ma trận kề ta có A[i,k] = A[k,i] ( số cung từ i tới k cũng là số cung từ k tới i ). Đồ thị vô hướng còn gọi là đồ thị đối xứng . Cung trong đồ thị đối xứng được gọi là cạnh của đồ thị

III / Một số định nghĩa khác :

a ) Trong đồ thị có hướng :

+ Tổng số cung đi vào một đỉnh gọi là bán bậc vào của đỉnh .Tổng số cung đi ra từ một đỉnh gọi là bán bậc ra của đỉnh .
+ Một dãy cung liên tiếp ( có thể không cùng chiều ) gọi là một dây chuyền.
+ Một dây chuyền mà ngọn của cung này là gốc của cung tiếp theo (trừ cung cuối cùng ) được gọi là một mạch ( còn gọi là đường đi có hướng )
+ Một mạch khép kín (ngọn cung cuối cùng trùng với gốc cung đầu tiên ) gọi là mạch đóng ( còn gọi là chu trình có hướng )
+ Chu trình sơ cấp là chu trình đi qua các đỉnh của nó không quá 1 lần (trừ đỉnh đầu và đỉnh cuối)
+ Độ dài của mạch là tổng khoảng cách các cung của nó (trong một số trường hợp người ta coi mỗi cung dài bằng 1 thì độ