Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Đồ thị

Những khái niệm và tính chất cơ bản Những khái niệm và tính chất cơ bản e1 O V= {v1, v2, v3, v4} E = {e1, e2, e3, e4, e5, e6, e7} e1= v1 v2, e2 =v1v2, e3 =v1v4, e4 =v2v3, e5 = v2v3, e6 = v2v4, e7 = v3v4 e2 AB e3 V= {O, A, B, AB} E ={e1,e2, e3, e4, e5, e6, e7, e8, e9} e4 v1 e1 v2 e4 v3 e5 e7 3 e7 e5 e6 B A e2 e6 e3 v4 e8 • • e9 4 1 .Những khái niệm và tính chất cơ bản Định nghĩa đồ thị Định nghĩa1.Đồ thị vô hướng G = (V, E) gồm: i) V là tập hợp khác rỗng mà các phần. | Đồ thị Biên soạn TS. Nguyễn Viết Đông 1 Những khái niệm và tính chất cơ bản Những khái niệm và tính chất cơ bản V Vi V2 V3 V4 E ei e2 ẻ3 64 e5 e6 e7 ei Vi V2 e2 ViV2 e3 ViV4 e4 V2V3 e5 V2V3 e6 V2V4 e7 V3V4 ei v V3 V O A B AB E ei e2 e3 84 e5 e6 e7 e8 e9 4 i Những khái niệm và tính chất cơ bản Định nghĩa đồ thị Định nghĩal .Đồ thị vô hướng G V E gồm i V là tập hợp khác rỗng mà các phần tử của nó gọi là đỉnh vertex của G. ii E là đa tập hợp gồm các cặp không sắp thứ tự của hai đỉnh. Mỗi phần tử của E được gọi là một cạnh edge của G. Ký hiệu uv. 5 b c a c fdiy e 0 T k ỡ 6 Những khái niệm và tính chất cơ bản Chú ý Ta nói cạnh uv nối u với v cạnh uv kề với u v. Nếu uv eE thì ta nói đỉnh u kề đỉnh v. Hai cạnh nối cùng một cặp đỉnh gọi là hai cạnh song song. Cạnh uu có hai đầu mút trùng nhau gọi là một khuyên. 7 3 u2 e4 3 61 í 1 ỉ 4 8 2 Những khái niệm và tính chất cơ bản Định nghĩa 2. Đồ thị vô hướng không có cạnh song song và không có khuyên gọi là đơn đồ thị vô hướng. Định nghĩa 3. Đồ thị vô hướng cho phép có cạnh song song nhưng không có khuyên gọi là đa đồ thị vô hướng. Định nghĩa 4. Đồ thị vô hướng cho phép có cạnh song song và có khuyên gọi là giả đồ thị 9 Những khái niệmvà tính chấtcơ bản Simple Graph Definition . A simple graph G V E consists of V a nonempty set of vertices and E a set of unordered pairs of distinct elements of V called edges. 11 Multigraph -A Non-Simple Graph There can be multiple telephone lines between two computers in the network. Detroit New York San Francisco Chicago -If Denver Washington Los Angeles In a multigraph G V E two or more edges may connect the same pair of vertices. ---------------------------------------------------T