Tài liệu Các bài toán tối ưu trên mạng

4.1.1. Các định nghĩa.
1. Đồ thị hữu hạn (graph) là một cặp tập hợp, ký hiệu là G = (X, A), trong đó X = {x1,
x2, ., xn } là tập hữu hạn các điểm (đỉnh, mút), A = { (i, j): i,j =1, n } là tập hợp các nhánh (cung,
cạnh) nối tất cả hoặc một phần các điểm xi∈X lại với nhau. Cạnh nối liền đỉnh i với đỉnh j, ký
hiệu là (i,j).
Ví dụ: G = (X, A), trong đó X = {x1, x2, x3, x4, x5, x6, x7} (Hình 4.1) là một đồ thị hữu hạn.
A = {(1,2), (1,4), (1,3), (2,3), (2,5), (3,4), (3,5), (3,6), (3,7), (5,7), (4,6), (6,7) }.
2. Một nhánh của đồ thị gọi là có hướng nếu quy định rõ một đầu mút là đỉnh đầu, đầu kia là đỉnh
cuối .
3. Một nhánh trong tập hợp A được định hướng (ký hiệu mũi tên), thì gọi là một cung. Nếu A là tập
hợp các cung thì đồ thị được gọi là đồ thị có hướng (Hình 4.2).
4. Nếu các nhánh không được định hướng thì đồ thị gọi là đồ thị không có hướng, ký hiệu G = (
X, A ) (Hình 4.3).
5. Một nhánh có dạng (i, i) gọi là một khuyên.
6. Một đỉnh i gọi là kề với đỉnh j nếu (i, j) ∈ A, nghĩa là có một cạnh của đồ thị nối liền đỉnh i với
đỉnh j .
Mỗi đồ thị có thể được biểu thị bởi một hình vẽ trên mặt phẳng. (Hình 4.1; 4.2; 4.3; 4.4). Trong
thực tế, trên bản đồ hệ thống đường giao thông nối các cơ quan đơn vị dân chính Đảng v.v của một
thành phố hay một vùng chính là một đồ thị hữu hạn. Vậy bản đồ cũng là một kiểu đồ thị.