Đang chuẩn bị liên kết để tải về 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ũ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. . | TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM MÔN TOÁN RỜI RẠC GV: 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ập hợ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)}. a f b h e c d Đồ thị G1 3 g Đ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ần tử 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ếu chú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)}. a Cạnh song song b f h e c g d Đồ thị .