Danh sách liên thuộc (Incidence list) - Mỗi đỉnh có một danh sách các cạnh nối với đỉnh đó. Các cạnh của đồ thị được có thể được lưu trong một danh sách riêng (có thể cài đặt bằng mảng (array) hoặc danh sách liên kết động (linked list)), trong đó mỗi phần tử ghi thông tin về một cạnh, bao gồm: cặp đỉnh mà cạnh đó nối (cặp này sẽ có thứ tự nếu đồ thị có hướng), trọng số và các dữ liệu khác. Danh sách liên thuộc của mỗi đỉnh sẽ chiếu tới vị trí của các. | Chu ý rằng trong ví dụ này luồng ra khỏi đỉnh s là fsb fsd bằng luỏng đến đỉnh t fct fet và bằng 5. Thật vồy ta cý Dinh ly Gia su F là luồng trên mạng vận tai G V E . Khi đó luong ra khỏi đỉnh s bang luồng đến đỉnh t tức là X fsi XX fit ch ứng minh. Ta cỏ s s j e x fji đo mồi ve being Ee2E fe- Và vồy 0 fjeV E2V fij Ei2V fji Ei2V fit Pi2V fti Ei2V fis Ei2V fsi ĩlj2V j s t Ei2V fij Ei2V fji Ei2V fit Ei2V fsi đo fti 0 fis với mọi Vi 2 V và . Dinh nghĩa Già sử F là luồng trến mang vận tai G. E Ễậi lượng fsi fit gọi là giắ tri cửa luồng F. Bai toan trến mang vạn tai G cý thồ phýt biếu Bai toán Tìm một luêng chếp nhạn được lến nhết trên đê thi G tUc là trong sế tết ca cac luóng trên G tìm luêng F có giế tri lến nhết. Thuồt toan gýn nhan cua Forđ va Fulkerson 27 giai bai toan nay đựa trến Dinh ly . Trước hết ta co mot so khai niếm . 177 Dinh nghĩa Nếu các đỉnh cua đồ thi G V E dược phân hoạch thành hai tập con Vo và Vo trong dó Vo c V vá Vo lá phán bu cUa Vo trong V thì tập các cung cUa G vOi đỉnh xuết phót thuếc Vo vá đỉnh kết thuc thuếc Vo goi là thiết diện ciỉa G. Tếp các cung ciìa thiết điện thường được ky hiệu bởi Vo Vo . Giá sir G lá mang ván tái. Thiết điện Vo V tách s khỏi t nếu s 2 Vo và t 2 Vo. Kha nang thông qua hay gia tri ciìa thiết điện lá tỏng ciĩa tát cá các khá năng ciìa tat cá các cung ciỉa G với đỉnh xuat phát thuếc Vo vá đỉnh kết thuc thuộc Vo tức lá v Vo Vo X qij. yi Vj 2 Vo Vo Thiôt diện nhỏ nhết lá thiết điện cỏ khá nang thong qua nhỏ nhết. Dinh ly Đinh ló thiết điện nho nhát-hà ng lớn nhết Gia tri cua luồng lơn nhất từ s đến t bằng kha nang thông qua của thiết diện nhỏ nhất Vm Vm tach s khỏi t. Chúng minh. Hiến nhiện ráng luong lớn nhết tù s đến t khếng thế lớn hơn v Vm Vm đo tat cá các đường đi tù s đến t đếu sử đung ít nhết mết cung ciìa thiết điện náy. Đo đó chỉ cán chứng minh rằng ton tái mết luếng đát gió tri náy. Tá xem luong đá cho F tương ứng voi mết vector m chiếu và đinh nghĩa thiết điện Vo Vo bằng
