Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này, các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Giả sử Vlà tập hữu hạn, không rỗng các phần tử nào đó. Bộ G = (V,E)được gọi là đồ thị hữu hạn. Mỗi phần tử của Vgọi là một đỉnh và mỗi phần tử u = (x,y)của Eđược gọi là một cạnh của đồ thị G = (V,E). Xét một cạnh ucủa Ekhi đó tồn tại hai đỉnh x, ycủa Vsao cho u = (x,y), ta nói rằng xnối với yhoặc xvà yphụ thuộc u. – Nếu cạnh u = (x,y)mà xvà ylà hai đỉnh phân biệt thì ta nói x, ylà hai đỉnh kề nhau. – Nếu u = (x,x)thì ulà cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên. – Nếu u = (x,y)mà x, ylà cặp đỉnh có phân biệt thứ tự hay có hướng từ xđến y thì ulà một cung, khi đó xlà gốc còn ylà ngọn hoặc xlà đỉnh ra, ylà đỉnh vào. – Khi giữa cặp đỉnh (x,y)có nhiều hơn một cạnh thì ta nói rằng những cạnh cùng cặp đỉnh là những cạnh song song hay là cạnh bội.