zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Các bài toán đồ thị

Chia sẻ: Hanh My | Ngày: | Loại File: PDF | Số trang:2

Báo xấu

111
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tìm đồ thị con Một bài toán thường gặp, được gọi là bài toán đồ thị con đẳng cấu (subgraph isomorphism problem), là tìm các đồ thị con trong một đồ thị cho trước. Nhiều tính chất của đồ thị có tính di truyền, nghĩa là nếu một đồ thị con nào đó có một tính chất thì toàn bộ đồ thị cũng có tính chất đó. Chẳng hạn như một đồ thị là không phẳng nếu như nó chứa một đồ thị hai phía đầy đủ (complete bipartite graph ) K3,3 (Xem Bài toán ba căn hộ và ba...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các bài toán đồ thị

Các bài toán đồ thị Tìm đồ thị con Một bài toán thường gặp, được gọi là bài toán đồ thị con đẳng cấu (subgraph isomorphism problem), là tìm các đồ thị con trong một đồ thị cho trước. Nhiều tính chất của đồ thị có tính di truyền, nghĩa là nếu một đồ thị con nào đó có một tính chất thì toàn bộ đồ thị cũng có tính chất đó. Chẳng hạn như một đồ thị là không phẳng nếu như nó chứa một đồ thị hai phía đầy đủ (complete bipartite graph ) K3,3 (Xem Bài toán ba căn hộ và ba hệ thống cung cấp năng lượng (Three cottage problem) hoặc nếu nó chứa đồ thị đầy đủ K5. Tuy nhiên, bài toán tìm đồ thị con cực đại thỏa mãn một tính chất nào đó thường là bài toán NP-đầy đủ (NP-complete problem). bài toán đồ thị con đầy đủ lớn nhất (clique problem) (NP-  đầy đủ) bài toán tập con độc lập (independent set problem) (NP-đầy  đủ) Tô màu đồ thị Bài chi tiết: Tô màu đồ thị Định lý bốn màu (four-color theorem)  Định lý đồ thị hoàn hảo mạnh (strong perfect graph  theorem)
Bài toán Erdős-Faber-Lovász conjecture (hiện chưa ai giải  được) Bài toán total coloring conjecture (hiện chưa ai giải được)  Bài toán list coloring conjecture (hiện chưa ai giải được)  Các bài toán đường đi Bài toán bảy cây cầu Euler (Seven Bridges of Königsberg)  còn gọi là "Bảy cây cầu ở Königsberg" Cây bao trùm nhỏ nhất (Minimum spanning tree)  Cây Steiner  Bài toán đường đi ngắn nhất  Bài toán người đưa thư Trung Hoa (còn gọi là "bài toán tìm  hành trình ngắn nhất") Bài toán người bán hàng (Traveling salesman problem)  (NP-đầy đủ) cũng có tài liệu (tiếng Việt) gọi đây là "Bài toán người đưa thư" Luồng Định lý luồng cực đại lát cắt cực tiểu  Reconstruction conjecture  Visibility graph problems

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.