Giáo trình Đồ thị và các thuật toán - Chương 1: Đại cương về đồ thị

Đồ thị có hướng G = (V, E} gồm một tập V các phần tử gọi là đỉnh (hay nút) và một tập E các cung sao cho mỗi cung e G E tương ứng với một cặp các đỉnh được sắp thứ tự. Nến có đúng một cung e tương ứng các đỉnh được sắp thứ tự (ữ, 6), ta sẽ viết e = (a, b).

Chúng ta sẽ giả sử các đỉnh được đánh số là ni, n2,., vn hay giản tiện, 1, 2,.,n, trong đó n = là số các đỉnh của đồ thị.

Nếu e là một cung tương ứng cặp các đỉnh được sắp thứ tự Vi và Vj thì đỉnh Vi gọi là gốc và đỉnh Vj gọi là ngọn; cung e gọi là liên thuộc hai đỉnh Vị và Vj. Chúng ta sẽ thường ký hiệu m = #E—SC) cạnh của đồ thị G. Các cạnh thường được đánh số là e1? e2,., em.