TAILIEUCHUNG - Nhận biết chu trình dominating là NP đầy đủ.

Nhận biết chu trình dominating là NP đầy đủ. Mối quan tâm chính của Điều khiển học là tìm kiếm những thuộc tính giống nhau ở các kiểu hệ thống khác nhau, ví dụ như: Liệu có sự giống nhau giữa hai hệ thống rất khác biệt về vật lý như một chiếc máy tính và bộ não người? | Tạp chí Tin học và Đĩêu khiền học T. 18 s. 3 2002 226-230 RECOGNIZING DOMINATING CYCLES IS NP-HARD vu DINH HOA DO NHU AN Abstract. We use cư G to denote the number of components in a given graph G. Chvátal 12 defines a graph G to be 1-tough if uj G S s for every subset s of the vertex set V with uj G s 1. Given a graph G a cycle c is called a hamiltonian cycle if c containes all vertices of G. A cycle c is said to be dominating if and only if G c has no edge. The problem of deciding the existence of a hamiltonian cycle in a given graph is known to be an NP-complete one hence it is mostly investigated in special claseses for example in 1-tough graph or specially investigated for studying of dominated cycles. In the following we show that the problem of deciding the existence of a dominating cycle in a given graph is NP-complete. Tóm tắt. Với ký hiệu iư G là số thành phần hên thông của một đồ thị G cho truớc. Chvátal 12 định nghĩa G là một đồ thị 1- tough nếu Uj G s s cho mọi tập con s của tập đỉnh V của G với Uj G s 1. Cho truớc môt đồ thi G môt chu trình c đuơc goi là chu trình Hamilton nếu c đi qua tất cả các đỉnh của G. Một chu trình c đuợc gọi là chu trình Dominating khi và chỉ khi G c không còn cạnh nào cả. Vấn đề xác đinh xem su tồn tai của chu trình Halmiton trong môt đồ thi cho truớc đuơc biết là môt vấn đề NP - đầy đủ và do đó vấn đề này thuờng đuợc xem xét trong các lớp đồ thị đặc biệt chằng hạn trong các đồ thị 1 - tough hoặc đuợc chuyển sang xem xét các đồ thị Dominating. Trong phần sau đây chúng ta chỉ ra rằng vấn đề xác định xem một đồ thị cho truớc có chu trình Dominating hay không cũng vẫn còn là bài toán NP - đầy đủ. 1. INTRODUCTION We begin with some definitions and convenient notation. We refer to 11 for undefined terminology and notation. All graphs here are finite and undirected graphs without loops and multiple edges. The vertex set of a graph G is V G and the edge set of G is E G . We use aj G to denote the number of components of G and a G .

• Kĩ thuật Viễn thông
• chu trình dominating
• khoa học điều khiển
• hệ thống kỹ thuật
• điều khiển học
• nghiên cứu tin học
• Lý thuyết thuật toán
• tự động học
• Quản lý hoạt động tự học
• Thực trạng hoạt động tự học
• Hoạt động tự học
• Hoạt động tự học của sinh viên
• Ý thức tự học
• Kỹ năng tự học
• Đề thi học kỳ
• Thiết bị tự động
• Hệ thống tự động
• Đề thi Thiết bị tự động
• Đề thi Hệ thống tự động
• Bài tập Thiết bị tự động
• Bài tập Hệ thống tự động
• Thực trạng quản lý hoạt động tự học
• Giải pháp quản lý hoạt động tự học
• Quản lý giáo dục đại học
• Thiết kế các hoạt động tự học cho học sinh
• Hoạt động tự học của học sinh
• Tự học theo chủ đề môn Hóa học
• Đánh giá năng lực tự học của học sinh
• Khung năng lực tự học môn Hóa học
• Tăng cường hoạt động tự học sinh viên
• Quản lý hoạt động tự học sinh viên
• Thực trạng hoạt động tự học sinh viên
• Công tác tự học sinh viên
• Sinh viên trường Đại học Sư Phạm
• Tự động hóa
• Tự động hóa quá trình công nghệ
• Lý thuyết điều khiển tự động
• Tự động hóa quá trình sản xuất
• Hệ thống rửa xe tự động
• Đồ án tự động hóa
• Đặc tính động học
• động học của hệ thống
• cơ sở tự động
• bài giảng cơ sở tự động
• tổng quan cơ sở tự động
• tài liệu cơ sở tự động
• Đặc tính động học của hệ thống
• Khâu động học điển hình
• Động học của hệ thống tự động
• Hệ thống tự động thủy khí
• Đề thi Hệ thống tự động thủy khí
• Thực trạng quản lí hoạt động tự học
• Quản lí hoạt động tự học của học sinh
• Kĩ năng tự học của học sinh
• Phát triển khả năng tự học của học sinh
• Biện pháp nâng cao tinh thần tự học của học sinh
• Giáo trình điều khiển tự động
• Hệ thống điều khiển tự động
• Toán học phần tử
• Hệ thông điều khiển
• Giải pháp tự động hóa của
• Tin học hóa
• Chế biến sâu khoáng sản
• Hệ thống tự động hoá trạm quạt gió
• Tự động hoá hầm bơm
• Tính tích cực tự học
• Biểu hiện tính tích cực tự học của sinh viên
• Thực trạng tính tích cực trong hoạt động tự học
• Hoạt động tự học ngoài giờ lên lớp của sinh viên
• Thái độ của sinh viên đối với hoạt động tự học
• Luận văn Thạc sĩ Giáo dục học
• Biện pháp quản lý hoạt động tự học
• Quản lý giáo dục
• Lý thiết điều khiển tự động
• Bài giảng Lý thiết điều khiển tự động
• Bài giảng Hệ thống điều khiển tự động
• Điều khiển tự động
• Đặc tính động học của các khâu
• Các khâu động học cơ bản
• bài giảng lý thuyết điều khiển tự động
• tài liệu lý thuyết điều khiển tự động
• giáo trình lý thuyết điều khiển tự động
• đề cương lý thuyết điều khiển tự động