Bài giảng Toán rời rạc (Phần 3) - Trần Nguyễn Minh Thư

Đồ thị có hướng G=(X,E) được gọi là mạng khi:

 Tồn tại duy nhất một đỉnh sX mà tại s không có cung đi

vào, chỉ có cung đi ra. Gọi s là điểm phát.

 Tồn tại duy nhất một đỉnh tX mà tại t không có cung đi

ra, chỉ có cung đi vào. Gọi t là điểm thu.

 Mỗi cung e=(i,j) đều được gán một giá trị không âm c(e)

hay c(i,j), gọi là khả năng thông qua của cung.

 Nếu không tồn tại cung từ đỉnh i đến đỉnh j thì khả năng

thông qua của cung đó được qui ước là bằng không.