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 (lay nít) và một tập E các cung sao cho mỗi cung t€ E tương ứng với một cặp các định được sắp thứ tự. Nếu có đúng một cung & tương ứng các định được sắp thứ tự (a, b), ta sẽ viết <= (a, b). Chúng ta sẽ giả sử các định được đánh số là t1, , trong đó n = 4V là số các đỉnh của đồ thị. ta hay giảm tiện, 1,2,., I, Nếu e là một cung tương ứng cặp các định được sắp thứ tự tụ và ti thì đỉnh vị gọi là gốc và định vị gọi là ngọn; cung € gọi là liên thuộc hai đỉnh vị và ti Chúng ta sẽ thu rừng ký hiệu m = ##E = số cạnh của đồ thị G. Các anh thường được đánh số là 61, 62 , 6m Một cách hình học, các định được biểu diễn bởi các điểm, và c = (tự, được biểu diễn bởi một cung nối các điểm lý và vị: Một cung có gốc trùng với ngon goi là khuyên. Nếu có nhiều hơn một chung với gốc tại vị và ngon tại t, thì G gọi là đa đồ thị và các chung trong ứng gọi là Nig Orig. Đơn đề thi có hướng là đồ thị không khuyến trong đó hai đinh bất kỳ vị và vị có nhiều nhất một cung (ta. Vị). Chẳng hạn, đồ thị trong Hình 11 có cung em là khuyền; các chung ta và E9 là song song do cũng tương ứng cặp đỉnh ta và vị.