Trong toán học và tin học, lý thuyết đồ thị nghiên cứu các tính chất của đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởi các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng. Đồ thị thường được vẽ dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạn thẳng (các cạnh). Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị. Ví dụ, cấu. | Đơn đồ thị, đa đồ thị Đồ thị G = (V,E) gọi là đa đồ thị nếu nó có ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh trở lên và không có khuyên C1 C3 C2 C4 C5 C7 C6 Ở mạng này có nhiều kênh thoại nối giữa hai máy. Mô hình mạng trên là một đa đồ thị. Giả đồ thị Giả đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh, E là tập các cặp không có thứ tự gồm hai phần tử (không nhất thiết khác nhau) của V gọi là các cạnh. Các e được gọi là khuyên nếu có dạng e=(u,u) Ví dụ: C1 C3 C2 C4 C5 C7 C6 Mạng máy tính có đường điện thoại từ một máy tính đến chính nó. Mô hình trên là một giả đồ thị vô hướng. Lý thuyết đồ thị Đồ thị có hướng G = (V,E) là đồ thị có hướng nếu với mọi cạnh e=(x,y) E có phân biệt thứ tự các đỉnh x và y, có hướng x đến y, hay (x,y) (y,x) Đối với một cung e = (x, y): x là đỉnh đi (gốc,đầu) y là đỉnh đến(ngọn, cuối) Cung e đi từ x và đến y x y Lý thuyết đồ thị Đồ thị có hướng 1 4 3 6 5 2 G = (V, E) V = {1, 2, 3, 4, 5, 6} E = { (1,4), (1,6), (2,1), (2,3), (3,2), | Đơn đồ thị, đa đồ thị Đồ thị G = (V,E) gọi là đa đồ thị nếu nó có ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh trở lên và không có khuyên C1 C3 C2 C4 C5 C7 C6 Ở mạng này có nhiều kênh thoại nối giữa hai máy. Mô hình mạng trên là một đa đồ thị. Giả đồ thị Giả đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh, E là tập các cặp không có thứ tự gồm hai phần tử (không nhất thiết khác nhau) của V gọi là các cạnh. Các e được gọi là khuyên nếu có dạng e=(u,u) Ví dụ: C1 C3 C2 C4 C5 C7 C6 Mạng máy tính có đường điện thoại từ một máy tính đến chính nó. Mô hình trên là một giả đồ thị vô hướng. Lý thuyết đồ thị Đồ thị có hướng G = (V,E) là đồ thị có hướng nếu với mọi cạnh e=(x,y) E có phân biệt thứ tự các đỉnh x và y, có hướng x đến y, hay (x,y) (y,x) Đối với một cung e = (x, y): x là đỉnh đi (gốc,đầu) y là đỉnh đến(ngọn, cuối) Cung e đi từ x và đến y x y Lý thuyết đồ thị Đồ thị có hướng 1 4 3 6 5 2 G = (V, E) V = {1, 2, 3, 4, 5, 6} E = { (1,4), (1,6), (2,1), (2,3), (3,2), (4,3), (4,5), (4,6), (5,3), (6,1), (6,5),(5,3)} (1, 4) = 1→4 Khuyên Song song Cạnh Kề Đỉnh Kề Đồ thị có hướng Cho G=(V,E) là một đồ thị có hướng và e=(vi,vj) E : vj được gọi là đỉnh sau của vi vi là một đỉnh trước của vj Tập các đỉnh sau và đỉnh trước của vi lần lượt được kí hiệu là (vi) và -1(vi) (x) = {y V | (x,y) E} G=(V,E) = (V, ) Lý thuyết đồ thị Đồ thị có hướng Lý thuyết đồ thị Lý thuyết đồ thị Đồ thị vô hướng G = (V,E) là đồ thị vô hướng nếu với mọi cạnh e=(x,y) E không phân biệt thứ tự các đỉnh x và y, tức là từ x đến y không kể hướng, hay (x,y) = (y,x) x y Lý thuyết đồ thị Đồ thị vô hướng 1 2 3 4 5 G = (V, E) V = {1, 2, 3, 4, 5} E = {(1,2), (1,3), (1,4), (2,3), (3,5), (4,5)} cạnh song song, khuyên? (x) = {y V | (x,y) E} Lý thuyết đồ thị Đồ thị có trọng số 1 2 3 4 5 40 70 60 20 50 10 Một đồ thị G = (V,E) gọi là có trọng lượng hay trọng số nếu mỗi cạnh(hoặc cung) được gán 1 số, nghĩa là có một .
