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

TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM<br /> MÔN TOÁN RỜI RẠC<br /> <br /> GV: Võ Tấn Dũng<br /> <br /> ĐƠN ĐỒ THỊ VÔ HƯỚNG<br />  Đơn đồ thị vô hướng G = (V,E) là một bộ gồm hai tập<br /> hợp V và E.<br />  V là tập các đỉnh (vertices).<br />  E là tập các cạnh (edges), mỗi cạnh là một cặp không có<br /> thứ tự gồm 2 đỉnh khác nhau của tập V.<br /> <br />  Ví dụ: Đơn đồ thị G1 = (V1, E1), trong đó<br /> <br /> V1={a, b, c, d, e, f, g, h},<br /> E1={(a,b), (b,c), (c,d), (a,d), (d,e), (a,e), (d,b), (f,g)}.<br /> a<br /> <br /> f<br /> b<br /> h<br /> <br /> e<br /> c<br /> d<br /> Đồ thị G1<br /> <br /> 3<br /> <br /> g<br /> <br /> ĐA ĐỒ THỊ VÔ HƯỚNG<br />  Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các<br /> đỉnh, và E là tập các cặp không có thứ tự gồm hai phần<br /> tử khác nhau của V gọi là các cạnh.<br />  Hai cạnh e1 và e2 được gọi là cạnh song song nếu<br /> chúng cùng tương ứng với một cặp đỉnh.<br /> <br />  Ví dụ: Đa đồ thị G2 = (V2, E2), trong đó<br /> <br /> V2={a, b, c, d, e, f, g, h},<br /> E2={(a,b), (b,c), (b,c), (c,d), (a,d), (d,e),<br /> (a,e), (a,e), (a, e), (d,b), (f,g)}.<br /> a<br /> <br /> Cạnh song song<br /> <br /> b<br /> <br /> f<br /> h<br /> <br /> e<br /> <br /> c<br /> g<br /> d<br /> Đồ thị G2<br /> <br />