Bài giảng Toán rời rạc và lý thuyết đồ thị: Bài 4 - Võ Tấn Dũng

Phần tiếp theo bài giảng "Toán rời rạc và lý thuyết đồ thị - Bài 4: Các khái niệm về đồ thị" cung cấp cho người học các kiến thức: Đơn đồ thị vô hướng, đa đồ thị vô hướng, đồ thị có hướng, bậc của đỉnh... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc và lý thuyết đồ thị: Bài 4 - Võ Tấn DũngTRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCMMÔN TOÁN RỜI RẠCGV: Võ Tấn DũngĐƠN ĐỒ THỊ VÔ HƯỚNG Đơn đồ thị vô hướng G = (V,E) là một bộ gồm hai tậphợp V và E. V là tập các đỉnh (vertices). E là tập các cạnh (edges), mỗi cạnh là một cặp không cóthứ tự gồm 2 đỉnh khác nhau của tập V. Ví dụ: Đơn đồ thị G1 = (V1, E1), trong đóV1={a, b, c, d, e, f, g, h},E1={(a,b), (b,c), (c,d), (a,d), (d,e), (a,e), (d,b), (f,g)}.afbhecdĐồ thị G13gĐA ĐỒ THỊ VÔ HƯỚNG Đa đồ thị vô hướng G= (V, E) bao gồm V là tập cácđỉnh, và E là tập các cặp không có thứ tự gồm hai phầntử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh song song nếuchúng cùng tương ứng với một cặp đỉnh. Ví dụ: Đa đồ thị G2 = (V2, E2), trong đóV2={a, b, c, d, e, f, g, h},E2={(a,b), (b,c), (b,c), (c,d), (a,d), (d,e),(a,e), (a,e), (a, e), (d,b), (f,g)}.aCạnh song songbfhecgdĐồ thị G2