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ội dung trích xuất từ tài liệu:
Bài giảng về Lý thuyết đồ thị Đơ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 C5 C2 C1 C7 C4 C6 C3Ở mạng này có nhiều kênh thoại nối giữa haimá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) C5• Ví dụ: C1 C2 C7 C4 C6 C3Mạng máy tính có đường điện thoại từ một máytính đến chính nó. Mô hình trên là một giả đồ thịvô hướng. Đồ thị có hướngG = (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) x yĐố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 • Lý thuyết đồ thị 3 Đồ thị có hướng Song songKhuyên 1 G = (V, E) 6 4 V = {1, 2, 3, 4, 5, 6} 2 E = { (1,4), (1,6), (2,1), (2,3), 5 3 (3,2), (4,3), (4,5), (4,6), (5,3), (6,1), (6,5),(5,3)} (1, 4) = 1→4 Đỉnh Kề Cạnh Kề Lý thuyết đồ thị 4 Đồ 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à đinh sau của vi ̉ – vi là môt đinh trước cua vj ̣̉ ̉• Tập các đỉnh sau và đinh 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ị 5Đồ thị có hướng Lý thuyết đồ thị 6 Đồ 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ị 7 Đồ thị vô hướng 3 1 G = (V, E) 2 V = {1, 2, 3, 4, 5} E = {(1,2), (1,3), (1,4), (2,3), (3,5), (4,5)} 4 5• cạnh song song, khuyên?• Γ (x) = {y ∈ V | (x,y) ∈E} Lý thuyết đồ thị 8 Đồ thị có trọng số• Môt đồ thị G = (V,E) goi là có trong lượng hay trong sô ́ ̣ ̣ ̣ ̣ nêu môi canh(hoăc cung) được gan 1 sô, ́ ̃ ̣ ̣ ́ ́• nghia là có môt anh xạ ω: E R. ̃ ̣́• Khi đó ω(e) goi là trong lượng cua e. ̣ ̣ ̉ 40 3 1 20 60 10 2 70 4 50 5 Lý thuyết đồ thị 9 3.2. Các thuật ngữ cơ bản Kề nhau Cho G = (V,E) và e =(x,y) ∈ E là một• cạnh nối đỉnh x và y. Khi đó ta nói e là cạnh chứa đỉnh x,y hoặc x,y là các đỉnh thuộc cạnh e. Khi đó x,y được gọi là hai đỉnh kề nhau Hai cạnh kề nhau nếu giữa chúng có• đỉnh chung. Ví dụ với u=(x,y) và v =(y,z) thì u,v là hai – cạnh kề nhau Lý thuyết đồ thị 10 Khái niệm X2vàX3là haiđỉnhkề nhauX1vàX2làhaiđỉnhkề nhau x2 x3 x1 x4 X1vàX4là haiđỉnhkề x5 nhau Lý thuyết đồ thị 11 Bậc của đỉnh• G=(V,E) có hướng và vi ∈V – nửa bâc trong(nửa bậc vào) = số các cu ...