tailieunhanh - Các lớp siêu đồ thị phi chu trình và các thuật toán đoán nhận chúng.

Các lớp siêu đồ thị phi chu trình và các thuật toán đoán nhận chúng. Để mô tả sự tương tự về mặt tổ chức (cấu trúc) của 2 hệ thống, điều khiển học đã xây dựng ra ngôn ngữ hình thức với các khái niệm như tổ chức, cấu trúc, trật tự, sự đa dạng, sự ràng buộc, ngẫu nhiên, tự do, sự phức tạp. | Tạp chí Tin học và Đĩêu khiền học T. 18 s. 3 2002 231-236 CÁC LỚP SIÊU ĐỒ THỊ PHI CHU TRÌNH VÀ CÁC THUẬT TOÁN ĐOÁN NHẬN CHÚNG NGUYỄN VĂN ĐỊNH Abstract. In 1 and 4 ớ-acyclic hypergraphs were introduced where 0 is Berge a 3 or 7. Several desirable properties of these corresponding acyclic database schemes have been established. In this paper we give a simple and clear presentation of the above classes of acyclic hypergraphs and the algorithms for their recognition. Tóm tắt. Trong 1 và 4 đã định nghĩa một loạt các kiểu siêu đồ thị phi chu trình bao gồm Berge-phi chu trình a-phi chu trình 3-phi chu trình y-phi chu trình. Nhiều tính chất mong muốn của các luợc do CSDL phi chu trình tuơng ứng cũng đã đuợc nhiều tác giả nghiên cứu và chứng minh. Trong bài báo này các loại siêu đồ thị phi chu trình sẽ đuợc giới thiệu một cách ngan gọn và rõ ràng cùng với các thuật toán đoán nhận chúng. 1. SIÊU ĐỒ THỊ PHI CHU TRÌNH VÀ Lược Đồ CSDL PHI CHU TRÌNH Định nghĩa 1. Trong mô hình CSDL quan hệ một lược đồ CSDL R trên một tập thuộc tính ư là một tập các lược đồ quan hệ ký hiệu R Ri R2 Rm sao cho Rị c u i u Rị ư. Một CSDL quan hệ r trên R là tập các quan hệ ri T2 . rm trong đó mỗi Vị là một l i m thể hiện của lược đồ quan hệ Rị. Định nghĩa 2. Một siêu đồ thị là một cặp Tí J f 8 trong đó J f là một tập hữu hạn các đỉnh và 8 C 0 là một tập các siêu cạnh mà mỗi siêu cạnh để đơn giản ta cũng gọi là cạnh là một tập con khác rỗng của J f. Như vậy một lược đồ CSDL R R1 R2 Rm trên tập thuộc tính u hiển nhiên được xem như một siêu đồ thị với tập các đỉnh là tập thuộc tính ư còn các lược đồ quan hệ con Ri R2 . Rm là các siêu cạnh của siêu đồ thị này. Ta gọi Tí u R là siêu đồ thị hên kết với lược đồ CSDL R R1 R2 Rm - Định nghĩa 3. Cho Tí J f 8 là một siêu đồ thị các đỉnh s t Ăf. Một đường đi từ đỉnh s tới đỉnh t là một dãy gồm k cạnh k 1 Ei Ẽ2 Ek sao cho a s G E b t Ek c Eị n Eị-ị-1 0 nếu 1 i k. Ta cũng nói dãy trên là một đường đi từ Ei tới Ek. Hai đỉnh hay hai cạnh được gọi là liên thông nếu .