Mục lục
10 quan hệ: Đa thức màu, Đồ thị đầy đủ, Đồ thị bánh xe, Đồ thị chu trình, Đồ thị hai phía, Định lý bốn màu, Bản đồ, Clique, Lý thuyết đồ thị, Thuật toán tô màu tham lam.
- Bài toán NP-đủ
- Lý thuyết đồ thị
- Lý thuyết đồ thị trong các bài toán tính toán
Đa thức màu
Trong lý thuyết đồ thị, Đa thức màu (tiếng Anh: Chromatic polynomial) của một đồ thị biểu diễn số cách tô màu các đỉnh của đồ thị đó theo số màu.
Xem Tô màu đồ thị và Đa thức màu
Đồ thị đầy đủ
Đồ thị đầy đủ n đỉnh (tiếng Anh: complete graph), ký hiệu là K_n (chữ K lấy từ tiếng Đức komplett), là đồ thị đơn vô hướng mà giữa hai đỉnh bất kì của nó luôn có cạnh nối.
Xem Tô màu đồ thị và Đồ thị đầy đủ
Đồ thị bánh xe
Trong lý thuyết đồ thị, đồ thị bánh xe (tiếng Anh: wheel graph) W_n được tạo thành từ đồ thị chu trình C_ bằng cách thêm 1 đỉnh và các cạnh nối đỉnh đó với tất cả các đỉnh còn lại.
Xem Tô màu đồ thị và Đồ thị bánh xe
Đồ thị chu trình
Hình:Cycle Graphs.PNG| Các đồ thị chu trình C_3,C_4,C_5,C_6.
Xem Tô màu đồ thị và Đồ thị chu trình
Đồ thị hai phía
Ví dụ về đồ thị hai phía không có chu trình Trong Lý thuyết đồ thị, đồ thị hai phía (đồ thị lưỡng phân hay đồ thị hai phần) (tiếng Anh: bipartite graph) là một đồ thị đặc biệt, trong đó tập các đỉnh có thể được chia thành hai tập không giao nhau thỏa mãn điều kiện không có cạnh nối hai đỉnh bất kỳ thuộc cùng một tập.
Xem Tô màu đồ thị và Đồ thị hai phía
Định lý bốn màu
Ví dụ về bản đồ bốn màu Định lý bốn màu (còn gọi là định lý bản đồ bốn màu) nghĩ rằng đối với bất kỳ mặt phẳng nào được chia thành các vùng phân biệt, chẳng hạn như bản đồ hành chính của một quốc gia, chỉ cần dùng tối đa bốn màu để phân biệt các vùng lân cận với nhau.
Xem Tô màu đồ thị và Định lý bốn màu
Bản đồ
Bản đồ thế giới do Johannes Kepler Bản đồ thế giới năm 2004 Bản đồ là hình thu nhỏ tương đối chính xác về một khu vực hay cả Trái Đất.
Clique
Một đồ thị đầy đủ K5 (5 đỉnh). Nếu đây là một đồ thị con thì tập đỉnh của nó sẽ tạo nên một clique kích thước 5. Đồ thị ''G'' có: 23 clique 1 đỉnh (bằng số đỉnh của ''G''), 42 clique 2 đỉnh (bằng số cạnh của ''G''), 19 clique 3 đỉnh (tô bởi màu xanh nhạt), và 2 clique 4 đỉnh (tô bởi màu xanh sẫm).
Lý thuyết đồ thị
Hình vẽ một đồ thị có 6 đỉnh và 7 cạnh Trong toán học và tin học, lý thuyết đồ thị nghiên cứu các tính chất của đồ thị.
Xem Tô màu đồ thị và Lý thuyết đồ thị
Thuật toán tô màu tham lam
Trong lý thuyết đồ thị và trí tuệ nhân tạo, Thuật toán tô màu tham lam (tiếng Anh: Greedy coloring) là một trong những phương pháp tô màu cho đồ thị áp dụng giải thuật tham lam (tiếng Anh: Greedy algorithm).
Xem Tô màu đồ thị và Thuật toán tô màu tham lam
Xem thêm
Bài toán NP-đủ
- Bài toán người bán hàng
- Bài toán người đưa thư Trung Hoa
- Bài toán xếp ba lô
- Bài toán đồ thị con đẳng cấu
- Dò mìn (trò chơi)
- FreeCell
- Kakuro
- NP-đầy đủ
- Oekaki Logic
- Phép đồng cấu đồ thị
- Phép đồng phôi (lý thuyết đồ thị)
- Quy hoạch số nguyên
- Sokoban
- Sudoku
- Tô màu đồ thị
- Tetris
- Tổ hợp độc lập
- Đường đi Hamilton
Lý thuyết đồ thị
- Bài toán bảy cây cầu Euler
- Bậc (lý thuyết đồ thị)
- Lý thuyết đồ thị
- Phép đẳng cấu đồ thị
- Phép đồng cấu đồ thị
- Phép đồng phôi (lý thuyết đồ thị)
- Tô màu đồ thị
- Thuật ngữ lý thuyết đồ thị
- Xích Markov
- Đồ thị (lý thuyết đồ thị)
- Đồ thị Petersen
- Đồ thị có hướng
- Đồ thị ngẫu nhiên
Lý thuyết đồ thị trong các bài toán tính toán
- Bài toán người bán hàng
- Bài toán người đưa thư Trung Hoa
- Bài toán đường đi ngắn nhất
- Bài toán đường đi rộng nhất
- Bài toán đồ thị con đẳng cấu
- Cây bao trùm
- Luồng cực đại
- Tô màu đồ thị
- Tổ hợp độc lập
- Đường đi Hamilton
Còn được gọi là Sắc số, Số màu cạnh.