TAILIEUCHUNG - Bài giảng về Lý thuyết đồ thị
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),
đang nạp các trang xem trước
