tailieunhanh - Luận văn tốt nghiệp - Sự ổn định và tô màu đồ thị

Số ổn định trong Cho đồ thị vô hướng G = và A X. a) Tập A gọi là tập ổn định trong của đồ thị nếu hai đỉnh bất kỳ trong A là không kề nhau, tức là không có một cạnh nào của đồ thị chứa hai đỉnh x và y. b) Tập A gọi là tập ổn định trong cực đại của đồ thị G nếu: - A là tập ổn định trong - Nếu thêm vào A một đỉnh ngoài A thì A không phải là ổn định trong. Gọi L là tập hợp. | Luận văn tốt nghiệp Chương 2 SỐ ỔN ĐỊNH VÀ TÔ MÀU ĐÒ THỊ I. SỐ ỔN ĐỊNH TRONG SỐ ỔN ĐỊNH NGOÀI NHÂN ĐÒ THỊ 1. Số ổn định trong Cho đồ thị vô hướng G X U và A X. a Tập A gọi là tập ổn định trong của đồ thị nếu hai đỉnh bất kỳ trong A là không kề nhau tức là không có một cạnh nào của đồ thị chứa hai đỉnh x và y. b Tập A gọi là tập ổn định trong cực đại của đồ thị G nếu - A là tập ổn định trong - Nếu thêm vào A một đỉnh ngoài A thì A không phải là ổn định trong. Gọi L là tập hợp các tập ổn đỉnh trong của của G X U . Khi đó ký hiệu G Max A A L và G được gọi là số ổn định trong của đồ thị G. Như vậy G là số phần tử của 1 tập ổn định trong cực đại nào đó. 2. Số ổn định ngoài Cho đồ thị vô hướng G X U và B X a Tập B được gọi là tập ổn định ngoài của đồ thị nếu với mỗi phần tử y X B đều tồn tại x B sao cho có cạnh nối giữa x và y B còn được gọi là tập thống trị của đồ thị. b Tập B được gọi là tập ổn định ngoài cực tiểu nếu - B là tập ổn định ngoài - Nếu bớt 1 phần tử bất kỳ của B thị B không còn là tập ổn định ngoài. Gọi M là tập của tất cả các tập ổn định ngoài của G X U . Khi đó ký hiệu G Min Bü M và G được gọi là số ổn định ngoài của đồ thị G. Đối với các tập ổn định ngoài ta thường quan tâm đến tập ổn định ngoài có số phần tử ít nhất vì lực lượng của nó liên quan tới số ổn định ngoài của đồ thị. 3. Nhân đồ thị Cho đồ thị vô hướng G X U . Nếu tập A X vừa là tập ổn định trong vừa là tập ổn định ngoài của đồ thị G thị A được gọi là nhân của đồ thị. Đối với nhân của đồ thị ta quan tâm tới nhân có số phần tử ít nhất. 24 Luận văn tốt nghiệp Hình Ví dụ xét đồ thị hình ta có Các tập ổn định trong của đồ thị là A1 A2 A3 a5 1 5 7 1 6 7 3 5 7 3 6 7 2 5 7 A6 2 6 7 A7 4 5 7 A8 4 6 7 A9 2 4 5 7 A10 2 4 6 7 Tập A9 và A10 là các tập ổn định trong cực đại có 4 phần tử vì nếu thêm 1 đỉnh mới nữa vào các tập đó thì chúng không còn là tập ổn định trong nữa. Số ổn định trong của đồ thị trên là ũ G 4. Với đồ thị trên các tập ổn định ngoài cực tiểu là B1 A1 B2 A2 B3 A3 B4 A4. Vì các .

Hạ Uyên 59 11 pdf

Upload

Bấm vào đây để xem trước nội dung

Tải xuống

TÀI LIỆU LIÊN QUAN

Luận văn thạc sĩ giáo dục học: Phương pháp khai thác các kiến thức lý luận văn học trong đọc – hiểu văn bản văn học lớp 11 chương trình nâng cao

102 381 5

Ebook Luyện cách lập luận trong đoạn văn nghị luận cho học sinh phổ thông: Phần 2

111 280 0

Luận văn Thạc sĩ Khoa học Ngữ văn: Văn chính luận của Ngô Thì Nhậm

86 371 21

Làm thế nào để viết luận văn khoa học tốt một luận văn khoa học

6 354 0

Mấy ý kiến về viết luận văn thạc sĩ lí luận và phương pháp dạy học văn - Trần Thanh Bình

4 417 3

HƯỚNG DẪN QUY CÁCH TRÌNH BÀY LUẬN VĂN, TÓM TẮT LUẬN VĂN, XẾP TÀI LIỆU THAM KHẢO VÀ CÁCH TRÍCH DẪN, MẪU BÌA LUẬN VĂN VÀ TÓM TẮT LUẬN VĂN

14 371 6

LUẬN VĂN TỐT NGHIỆP NGÀNH NGỮ VĂN “ GIỌNG ĐIỆU NGHỆ THUẬT CỦA NHÀ VĂN BALZAC TRONG BA TIỂU THUYẾT TIÊU BIỂU

151 363 2

Khoá luận tốt nghiệp Sư phạm Ngữ Văn: Áp dụng mô hình vòng tròn thảo luận văn chương trong dạy học văn nghị luận văn học

78 9 3

Ebook Luyện cách lập luận trong đoạn văn nghị luận cho học sinh phổ thông: Phần 1

106 313 0

Luận văn Thạc sĩ Giáo dục học: Rèn luyện kỹ năng lập luận trong văn nghị luận cho học sinh Trung học phổ thông

148 377 1

TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8 461974 55

Giới thiệu :Lập trình mã nguồn mở

14 23275 64

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11015 533

Câu hỏi và đáp án bài tập tình huống Quản trị học

14 10225 452

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”

3 9583 106

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8440 1138

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức

16 8302 423

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7900 2237

Đề tài: Dự án kinh doanh thời trang quần áo nữ

17 6876 257

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 6246 1517

TỪ KHÓA LIÊN QUAN

TÀI LIỆU MỚI ĐĂNG

Bơm máy nén quạt trong công nghiệp part 8

20 210 3 29-05-2024

QUẢN LÝ CHẤT LƯỢNG KHÔNG KHÍ

75 146 0 29-05-2024

Báo cáo tốt nghiệp: Vận hành và bảo dưỡng trong MPLS

92 155 3 29-05-2024

ĐỀ THI THỬ ĐẠI HỌC 2009 – THPT ĐÔNG SƠN 1 – LẦN 2 – MÔN TOÁN

8 109 0 29-05-2024

GYNECOLOGIC CANCERS IN PREGNANCY: GUIDELINES OF AN INTERNATIONAL CONSENSUS MEETING

12 104 0 29-05-2024

Giáo trình hình thành tỷ suất dinh lợi và các phương thức thanh toán nợ theo dư nợ ban đầu p3

5 99 1 29-05-2024

báo cáo hóa học:" A decade of modelling research yields considerable evidence for the importance of concurrency: a response to Sawers and Stillwaggon"

7 94 0 29-05-2024

Bài giảng Next Generation Network : Dịch vụ trong NGN part 1

6 96 0 29-05-2024

ĐẠI TRÀNG THANH ÂM Ở THAI NHI VÀ SỎI THẬN TRẺ EM - NGƯỜI LỚN

5 102 0 29-05-2024

Donald và bạn hữu 25

32 100 0 29-05-2024

TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7900 2237

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 6246 1517

Ebook Chào con ba mẹ đã sẵn sàng

112 3849 1274

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1

62 5467 1141

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8440 1138

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu

561 3572 658

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân

122 3773 567

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11015 533

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm

274 4210 526

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe

35 4216 483