Tài liệu Thư viện số

Danh mục TaiLieu.VN

Giáo trình lý thuyết đồ thị - Bài 5

Nhân của đồ thị Giả sử G = (V, E) là một đồ thị. Định nghĩa 3.8: Tập B ⊆ V được gọi là nhân của đồ thị G nếu nó vừa là tập ổn định trong vừa là tập ổn định ngoài của G, nghĩa là: ∀x ∈ B : B ∩ F(x) = ∅ và ∀y ∉ B : B ∩ F(y) ≠ ∅. Hai điều kiện trên của nhân tương đương với đẳng thức: F-1(B) = V \ B. Từ định nghĩa của nhân, ta suy ra: - Nhân không chứa đỉnh nút. - Nếu F(x) = ∅ thì x phải thuộc vào một nhân nào đó của đồ thị. Ví dụ 3.9: Xét các đồ thị sau đây:

Từ khóa: Chu trình Hamilton, thuật toán , đồ thị, ứng dụng cây, hàm trên đồ thị

8 p tailieuvn_hcmute 17/01/2012 447 2

Bình luận