Thi đấu

Bài Toán 2-SAT (2-Satisfiability) Trong Lập Trình Thi Đấu

Bài toán 2-SAT tìm phép gán chân lý cho N biến logic thỏa mãn M mệnh đề dạng tuyển hai biến bằng cách quy về đồ thị suy diễn và thuật toán Tarjan tìm thành phần liên thông mạnh trong thời gian tuyến tính O(N + M).

Bài Toán 2-SAT (2-Satisfiability) Trong Lập Trình Thi Đấu

Trong lý thuyết độ phức tạp tính toán, bài toán thỏa mãn mệnh đề logic (Boolean Satisfiability Problem - SAT) là một trong những bài toán kinh điển nhất của khoa học máy tính. Vấn đề cốt lõi của bài toán là tìm một phép gán giá trị chân lý cho các biến logic sao cho toàn bộ biểu thức gồm nhiều mệnh đề đồng thời nhận giá trị đúng.

Năm 1971, định lý Cook-Levin đã chứng minh rằng bài toán SAT tổng quát, cũng như trường hợp 3-SAT (mỗi mệnh đề có 3 biến), là bài toán NP-đầy đủ (NP-complete). Điều đó đồng nghĩa với việc chưa từng có thuật toán thời gian đa thức nào giải được 3-SAT trong trường hợp tổng quát. Tuy nhiên, một ngoại lệ vô cùng kỳ diệu xuất hiện khi mỗi mệnh đề chỉ chứa tối đa hai biến logic: bài toán 2-SAT (2-Satisfiability) có thể giải quyết hoàn toàn triệt để trong thời gian tuyến tính \(O(N + M)\)!

Nhờ tính chất tuyến tính tuyệt đẹp này, 2-SAT trở thành một vũ khí thuật toán cực mạnh trong các kỳ thi Học sinh giỏi Quốc gia (VNOI / VOI), Olympic Tin học Sinh viên và kỳ thi lập trình quốc tế ICPC. Bất kỳ bài toán nào có thể quy về việc đưa ra các quyết định nhị phân có ràng buộc kéo theo đối kháng đều có thể được mô hình hóa và giải quyết trọn vẹn bằng 2-SAT.

ĐỒ THỊ SUY DIỄN 2-SAT (IMPLICATION GRAPH) Mệnh đề (u ∨ v) chuyển thành 2 cung có hướng: (¬u → v) và (¬v → u) Quy tắc biến đổi tương đương: (x1 ∨ ¬x3) ⇔ (¬x1 → ¬x3) ∧ (x3 → x1) (¬x1 ∨ x3) ⇔ (x1 → x3) ∧ (¬x3 → ¬x1) SCC #1 (Thành phần liên thông 1) SCC #2 (Thành phần liên thông 2) x1 x3 ¬x3 ¬x1 ĐIỀU KIỆN TỒN TẠI NGHIỆM: Hệ có nghiệm ⇔ Với mọi biến xi: comp(xi) ≠ comp(¬xi) Gán giá trị: Nếu comp(xi) < comp(¬xi) (SCC của xi được Tarjan chốt trước) → gán xi = TRUE, ngược lại FALSE.
ĐỒ THỊ SUY DIỄN 2-SAT Biến đổi mệnh đề logic sang đồ thị có hướng Quy tắc biến đổi tương đương: (u ∨ v) ⇔ (¬u → v) ∧ (¬v → u) (u → v) ⇔ (¬u ∨ v) SCC #1 (Thành phần liên thông 1) x1 x3 SCC #2 (Thành phần liên thông 2) ¬x3 ¬x1 ĐIỀU KIỆN CÓ NGHIỆM: Hệ có nghiệm ⇔ xi và ¬xi khác SCC. Nếu comp(xi) < comp(¬xi) → xi = TRUE. Độ phức tạp tuyến tính O(N + M) với Tarjan.
Mô hình đồ thị suy diễn (Implication Graph) và kiểm tra tính thỏa mãn bằng thành phần liên thông mạnh (SCC).

Định nghĩa bài toán 2-SAT và dạng chuẩn hội CNF

Cho \(N\) biến logic \(x_1, x_2, \dots, x_N\), mỗi biến chỉ nhận một trong hai giá trị chân lý nhị phân: Đúng (True / 1) hoặc Sai (False / 0). Phủ định của biến \(x_i\) được ký hiệu là \(\neg x_i\). Mỗi phần tử \(x_i\) hoặc \(\neg x_i\) được gọi là một literal.

Hệ phương trình logic 2-SAT bao gồm \(M\) mệnh đề dạng tuyển (OR), nối với nhau bằng phép hội (AND) để tạo thành dạng chuẩn hội CNF (Conjunctive Normal Form):

\[\Phi = (u_1 \lor v_1) \land (u_2 \lor v_2) \land \dots \land (u_M \lor v_M)\]

Trong đó, mỗi \(u_i, v_i\) là một literal đại diện cho một biến hoặc phủ định của biến đó. Yêu cầu của bài toán đặt ra gồm hai phần:

  1. Kiểm tra tính khả thỏa (Decision Problem): Xác định xem có tồn tại ít nhất một phép gán giá trị chân lý cho \(N\) biến sao cho toàn bộ biểu thức \(\Phi\) nhận giá trị Đúng hay không.
  2. Dựng nghiệm cụ thể (Search Problem): Nếu hệ khả thỏa, hãy tìm ra một bộ giá trị chân lý cụ thể cho từng biến \(x_1, x_2, \dots, x_N\) thỏa mãn mọi ràng buộc.

Xây dựng đồ thị suy diễn Implication Graph

Chìa khóa mang tính quyết định giúp chuyển hóa bài toán logic rời rạc thành bài toán đồ thị nằm ở phép biến đổi tương đương trong đại số Boole:

\[(u \lor v) \iff (\neg u \implies v) \land (\neg v \implies u)\]

Ý nghĩa trực giác của phép biến đổi này rất tự nhiên và chặt chẽ: Để mệnh đề tuyển \((u \lor v)\) nhận giá trị đúng, nếu phần tử \(u\) bị gán giá trị Sai (\(\neg u\) đúng), thì phần tử còn lại là \(v\) bắt buộc phải nhận giá trị Đúng. Hoàn toàn tương tự, nếu \(v\) bị gán giá trị Sai (\(\neg v\) đúng), thì bắt buộc \(u\) phải nhận giá trị Đúng.

Dựa trên tính chất này, ta xây dựng một đồ thị có hướng \(G = (V, E)\) được gọi là Đồ thị suy diễn (Implication Graph):

  • Tập đỉnh \(V\): Với mỗi biến logic \(x_i\) (\(1 \le i \le N\)), ta tạo ra hai đỉnh phân biệt:
    • Một đỉnh đại diện cho trạng thái biến \(x_i\) nhận giá trị True (thường được đánh số \(2i\)).
    • Một đỉnh đại diện cho trạng thái phủ định \(\neg x_i\) nhận giá trị True (thường được đánh số \(2i + 1\)).
    • Tổng số đỉnh trên đồ thị là đúng \(2N\) đỉnh.
  • Tập cung có hướng \(E\): Với mỗi mệnh đề \((u \lor v)\) trong biểu thức \(\Phi\), ta thêm vào đồ thị đúng hai cung có hướng:
    • Cung từ \(\neg u\) đến \(v\) (\(\neg u \to v\)): thể hiện suy diễn logic nếu \(\neg u\) đúng thì kéo theo \(v\) phải đúng.
    • Cung từ \(\neg v\) đến \(u\) (\(\neg v \to u\)): thể hiện suy diễn logic nếu \(\neg v\) đúng thì kéo theo \(u\) phải đúng.

Dưới đây là bảng quy đổi các ràng buộc thực tế thường gặp sang các cung suy diễn trên đồ thị:

Ràng buộc logic bài toán Biểu diễn đại số logic Cung có hướng thêm vào đồ thị
Ít nhất một trong hai phải đúng \(u \lor v\) \(\neg u \to v\) và \(\neg v \to u\)
Nếu \(u\) xảy ra thì \(v\) phải xảy ra \(u \implies v \iff \neg u \lor v\) \(u \to v\) và \(\neg v \to \neg u\)
Bắt buộc \(u\) phải đúng \(u \lor u\) \(\neg u \to u\)
Bắt buộc \(u\) phải sai \(\neg u \lor \neg u\) \(u \to \neg u\)
Hai lựa chọn xung khắc (XOR) \((u \lor v) \land (\neg u \lor \neg v)\) \(\neg u \to v, \neg v \to u, u \to \neg v, v \to \neg u\)
Hai lựa chọn phải tương đương (XNOR) \((\neg u \lor v) \land (u \lor \neg v)\) \(u \to v, \neg v \to \neg u, v \to u, \neg u \to \neg v\)

Điều kiện tồn tại nghiệm và thuật toán Tarjan SCC

Một đường đi có hướng từ đỉnh \(A\) đến đỉnh \(B\) (\(A \leadsto B\)) trên đồ thị suy diễn đồng nghĩa với một chuỗi suy diễn logic kéo theo: nếu đỉnh \(A\) được chọn là True thì đỉnh \(B\) cũng bắt buộc phải được gán True.

1. Điều kiện vô nghiệm

Nếu trên đồ thị suy diễn tồn tại một biến \(x_i\) sao cho:

  • Từ đỉnh \(x_i\) có đường đi đến đỉnh \(\neg x_i\) (tức là \(x_i \implies \neg x_i\)).
  • Đồng thời từ đỉnh \(\neg x_i\) cũng có đường đi quay trở lại đỉnh \(x_i\) (tức là \(\neg x_i \implies x_i\)).

Khi đó, hai đỉnh \(x_i\) và \(\neg x_i\) có thể đi tới nhau qua lại, nghĩa là chúng thuộc cùng một thành phần liên thông mạnh (Strongly Connected Component - SCC) của đồ thị. Nếu điều này xảy ra, ta rơi vào một nghịch lý logic không thể tháo gỡ: việc chọn \(x_i = \text{True}\) kéo theo \(x_i = \text{False}\), và việc chọn \(x_i = \text{False}\) cũng lại kéo theo \(x_i = \text{True}\). Do đó, hệ phương trình logic 2-SAT hoàn toàn vô nghiệm!

Ngược lại, nếu với mọi biến \(x_i\), hai đỉnh \(x_i\) và \(\neg x_i\) nằm ở hai thành phần liên thông mạnh khác nhau, ta luôn luôn đảm bảo tìm được ít nhất một bộ nghiệm thỏa mãn hệ. Đây chính là nội dung định lý cốt lõi của bài toán 2-SAT.

2. Thuật toán gán nghiệm qua thứ tự Topo ngược

Khi hệ khả thỏa, việc gán giá trị chân lý cho các biến cần tuân thủ quy tắc suy diễn: không bao giờ được gán True cho một đỉnh nếu từ đỉnh đó có thể đi tới một đỉnh khác mang giá trị False.

Để thực hiện điều này một cách tự nhiên, ta tận dụng cấu trúc của thuật toán Tarjan tìm thành phần liên thông mạnh:

  • Thuật toán Tarjan thực hiện duyệt DFS trên đồ thị và gán chỉ số định danh SCC cho các thành phần liên thông mạnh theo thứ tự kết thúc duyệt của các đỉnh.
  • Thành phần liên thông mạnh nào nằm ở vị trí lá (sink) của đồ thị ngưng tụ DAG (tức là không có cung đi tiếp tới SCC khác) sẽ được hoàn thành và chốt mã định danh SCC trước tiên.
  • Do đó, nếu có một cung suy diễn từ \(u\) sang \(v\) (\(u \to v\)), thì thành phần liên thông mạnh chứa \(v\) sẽ được chốt trước thành phần liên thông mạnh chứa \(u\). Điều này tương đương với việc mã định danh SCC của \(v\) sẽ nhỏ hơn mã định danh SCC của \(u\): \[\text{comp}(v) \lt \text{comp}(u)\]

Từ tính chất này, nếu \(\text{comp}(x_i) \lt \text{comp}(\neg x_i)\), đỉnh \(x_i\) nằm sau về mặt topo suy diễn so với \(\neg x_i\). Nếu ta gán \(x_i = \text{True}\), dòng suy diễn sẽ không thể quay ngược trở lại để ép \(\neg x_i = \text{True}\). Vì vậy, quy tắc dựng nghiệm tối ưu chỉ là một phép so sánh mã SCC đơn giản:

  • Nếu \(\text{comp}(x_i) \lt \text{comp}(\neg x_i)\): Gán \(x_i = \text{True} (1)\).
  • Nếu \(\text{comp}(x_i) \gt \text{comp}(\neg x_i)\): Gán \(x_i = \text{False} (0)\).

Kỹ thuật tối ưu số lượng cạnh Prefix Graph

Trong các bài toán thực tế của các kỳ thi học sinh giỏi quốc gia và quốc tế, ta thường gặp phải bài toán chọn tối đa một phần tử trong một tập hợp: "Cho một nhóm gồm \(K\) phần tử \(y_1, y_2, \dots, y_K\), hãy đảm bảo có nhiều nhất một phần tử nhận giá trị True" (ràng buộc At-most-one).

Nếu ta giải quyết bằng cách ghép cặp ngây thơ giữa mọi cặp biến \((y_i, y_j)\) với mệnh đề \(\neg y_i \lor \neg y_j\), số lượng cung suy diễn sinh ra sẽ bằng \(K(K - 1)\), tức là độ phức tạp không gian và thời gian lên tới \(O(K^2)\). Khi \(K = 10^5\), cách làm này sẽ ngay lập tức gây tràn bộ nhớ và quá thời gian.

Để giảm số lượng cung xuống mức tuyến tính \(O(K)\), kỹ thuật đỉnh phụ tiền tố (Prefix Graph) được áp dụng vô cùng tinh tế:

  1. Ta tạo thêm \(K\) biến phụ \(P_1, P_2, \dots, P_K\). Ý nghĩa logic của biến phụ \(P_i\) là: "Có ít nhất một phần tử trong đoạn tiền tố từ \(y_1\) đến \(y_i\) nhận giá trị True".
  2. Ta thiết lập các cung suy diễn cục bộ:
    • \(P_i \implies P_{i+1}\): Nếu tiền tố độ dài \(i\) đã có phần tử True thì tiền tố độ dài \(i + 1\) cũng có phần tử True.
    • \(y_i \implies P_i\): Nếu bản thân biến \(y_i\) nhận giá trị True thì tiền tố tới \(i\) nhận True.
    • \(y_i \implies \neg P_{i-1}\): Nếu bản thân biến \(y_i\) nhận giá trị True thì bắt buộc toàn bộ tiền tố đứng trước nó từ \(y_1\) đến \(y_{i-1}\) phải nhận False. Nhờ cấu trúc tuyến tính này, mỗi biến \(y_i\) chỉ tạo ra một số lượng hằng số cung suy diễn, giúp giảm tổng số đỉnh và cạnh của hệ thống về đúng \(O(K)\). Kỹ thuật này cho phép bài toán xử lý được các hệ thống hàng trăm nghìn biến một cách nhẹ nhàng.
Học cùng giảng viên

Chủ đề này nằm trong Buổi 03 - Bridge, Articulation Point & SCC / Tarjan của Tài năng lập trình. Xem đề cương

Các mô hình bài toán quy về 2-SAT kinh điển

Dưới đây là ba dạng bài toán lập trình thi đấu phổ biến nhất có thể giải quyết bằng 2-SAT:

1. Bài toán xếp lịch khoảng thời gian (Interval Scheduling with Choices)

Cho \(N\) sự kiện cần diễn ra, mỗi sự kiện thứ \(i\) có hai khoảng thời gian có thể chọn: \([S_{i,1}, E_{i,1}]\) hoặc \([S_{i,2}, E_{i,2}]\). Hai sự kiện bất kỳ không được phép diễn ra trùng thời gian với nhau.

  • Ta đặt biến nhị phân \(x_i\): nếu \(x_i = 1\) nghĩa là chọn khoảng thời gian thứ nhất, nếu \(x_i = 0\) nghĩa là chọn khoảng thời gian thứ hai.
  • Nếu khoảng thời gian thứ \(a\) của sự kiện \(i\) giao nhau với khoảng thời gian thứ \(b\) của sự kiện \(j\), hai lựa chọn này xung khắc nhau, sinh ra ràng buộc logic: \(\neg (\text{chọn } a) \lor \neg (\text{chọn } b)\).
  • Đây chính là một bài toán 2-SAT hoàn chỉnh.

2. Bài toán nhị phân trên đáp án kết hợp kiểm tra 2-SAT

Nhiều bài toán hình học yêu cầu tìm bán kính lớn nhất \(R\) sao cho có thể đặt \(N\) trạm phát sóng tại một trong hai vị trí khả dĩ mà không có hai trạm phát sóng nào giao thoa sóng với nhau.

  • Với một giá trị bán kính \(R\) cố định qua tìm kiếm nhị phân, ta kiểm tra xem các vòng tròn bán kính \(R\) có xung đột vị trí hay không.
  • Nếu hai vị trí đặt trạm xung đột, ta tạo ràng buộc 2-SAT tương ứng.
  • Thuật toán Tarjan sẽ kiểm tra tính khả thỏa trong thời gian tuyến tính để điều chỉnh khoảng tìm kiếm nhị phân.

3. Bài toán phân chia hai tập hợp có điều kiện (Two-Coloring Constraints)

Các bài toán chia một tập hợp phần tử thành hai nhóm đối kháng sao cho thỏa mãn các điều kiện như: nếu phần tử \(A\) thuộc nhóm 1 thì phần tử \(B\) cũng phải thuộc nhóm 1, hoặc hai phần tử \(C\) và \(D\) không được cùng nằm chung một nhóm.

Cài đặt chuẩn C++17 và Python 3

Dưới đây là bộ giải 2-SAT tổng quát hoàn chỉnh, áp dụng thuật toán Tarjan tìm thành phần liên thông mạnh với thời gian tuyến tính \(O(N + M)\):

#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>

using namespace std;

// Cấu trúc giải bài toán 2-SAT (2-Satisfiability) bằng thuật toán Tarjan SCC
// Độ phức tạp thời gian: O(N + M)
// Độ phức tạp bộ nhớ: O(N + M)
struct TwoSAT {
    int n; // Số biến (từ 1 đến n)
    int num_nodes;
    vector<vector<int>> adj;
    vector<int> tin, low, comp;
    vector<bool> on_stack;
    stack<int> st;
    int timer, scc_count;
    vector<int> assignment; // Nghiệm tìm được (0 hoặc 1)

    TwoSAT(int num_vars) : n(num_vars), num_nodes(2 * num_vars) {
        adj.assign(num_nodes, vector<int>());
        tin.assign(num_nodes, -1);
        low.assign(num_nodes, -1);
        comp.assign(num_nodes, -1);
        on_stack.assign(num_nodes, false);
        timer = 0;
        scc_count = 0;
        assignment.assign(n + 1, 0);
    }

    // Biến x (1-based): x dương là x, x âm là NOT(|x|)
    // Định danh đỉnh: x > 0 -> 2*(x-1), NOT(x) -> 2*(x-1) + 1
    int to_node(int lit) {
        if (lit > 0) return 2 * (lit - 1);
        int v = -lit;
        return 2 * (v - 1) + 1;
    }

    int negate_node(int node) {
        return node ^ 1;
    }

    // Thêm mệnh đề tuyển: (u OR v) <=> (NOT u => v) AND (NOT v => u)
    void add_clause_or(int u, int v) {
        int node_u = to_node(u);
        int node_v = to_node(v);
        adj[negate_node(node_u)].push_back(node_v);
        adj[negate_node(node_v)].push_back(node_u);
    }

    // Mệnh đề kéo theo: (u => v) <=> (NOT u OR v)
    void add_implication(int u, int v) {
        add_clause_or(-u, v);
    }

    // Buộc biến u phải mang giá trị đúng: (u OR u)
    void set_true(int u) {
        add_clause_or(u, u);
    }

    // Buộc biến u phải mang giá trị sai: (NOT u OR NOT u)
    void set_false(int u) {
        add_clause_or(-u, -u);
    }

    void dfs_tarjan(int u) {
        tin[u] = low[u] = ++timer;
        st.push(u);
        on_stack[u] = true;

        for (int v : adj[u]) {
            if (tin[v] == -1) {
                dfs_tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (on_stack[v]) {
                low[u] = min(low[u], tin[v]);
            }
        }

        if (low[u] == tin[u]) {
            scc_count++;
            while (true) {
                int node = st.top();
                st.pop();
                on_stack[node] = false;
                comp[node] = scc_count;
                if (node == u) break;
            }
        }
    }

    bool solve() {
        for (int i = 0; i < num_nodes; i++) {
            if (tin[i] == -1) {
                dfs_tarjan(i);
            }
        }

        // Kiểm tra tính thỏa mãn: x và NOT x không được nằm cùng SCC
        for (int i = 1; i <= n; i++) {
            int node_pos = to_node(i);
            int node_neg = negate_node(node_pos);
            if (comp[node_pos] == comp[node_neg]) {
                return false; // Vô nghiệm
            }
            // Trong Tarjan, SCC kết thúc trước có số thứ tự comp nhỏ hơn (topologically later)
            // Nếu comp[node_pos] < comp[node_neg] => gán node_pos = true (giá trị 1)
            assignment[i] = (comp[node_pos] < comp[node_neg]) ? 1 : 0;
        }
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    TwoSAT sat(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        sat.add_clause_or(u, v);
    }

    if (sat.solve()) {
        cout << "YES\n";
        for (int i = 1; i <= n; i++) {
            cout << sat.assignment[i] << (i == n ? "" : " ");
        }
        cout << "\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

Phân tích độ phức tạp thuật toán

  • Thời gian xây dựng đồ thị: Với \(N\) biến và \(M\) mệnh đề, đồ thị có đúng \(2N\) đỉnh và \(2M\) cung có hướng. Quá trình khởi tạo danh sách kề tốn \(O(N + M)\).
  • Thời gian tìm thành phần liên thông mạnh: Thuật toán Tarjan duyệt DFS qua mỗi đỉnh và mỗi cung đúng một lần duy nhất. Độ phức tạp là \(O(V + E) = O(N + M)\).
  • Thời gian kiểm tra và dựng nghiệm: Duyệt qua \(N\) cặp đỉnh \((2i, 2i+1)\) để so sánh giá trị mảng comp tốn \(O(N)\).
  • Tổng thời gian toàn bộ thuật toán: \[O(N + M)\] Đây là độ phức tạp thời gian tối ưu tuyệt đối, tuyến tính theo kích thước dữ liệu đầu vào.
  • Bộ nhớ (Space Complexity): Mảng danh sách kề và các mảng trạng thái phụ trợ của Tarjan chiếm \(O(N + M)\) bộ nhớ.

Luyện ngay trên Big-O Coding

Để nắm vững kỹ thuật xây dựng đồ thị suy diễn và phân tích thành phần liên thông mạnh, bạn hãy thực hành ngay các bài tập sau trên hệ thống Big-O Coding:

Vì sao 3-SAT lại là NP-đầy đủ trong khi 2-SAT lại giải được trong O(N + M)?

Trong 2-SAT, mệnh đề \((u \lor v)\) chỉ có hai biến, cho phép ta biến đổi thành hai mệnh đề kéo theo dứt khoát: \(\neg u \implies v\) và \(\neg v \implies u\). Nhờ đó, bài toán chuyển hóa hoàn hảo thành bài toán tìm đường đi trên đồ thị có hướng. Ngược lại, trong 3-SAT với mệnh đề \((u \lor v \lor w)\), nếu \(\neg u\) xảy ra ta chỉ suy ra được \((v \lor w)\) vẫn là phép OR, không thể tạo thành một cung suy diễn dứt khoát duy nhất, khiến không gian tìm kiếm bùng nổ theo hàm mũ.

Thuật toán Kosaraju có thể dùng thay cho Tarjan trong 2-SAT không?

Hoàn toàn được! Thuật toán Kosaraju tìm SCC bằng hai lượt duyệt DFS cũng đạt độ phức tạp \(O(N + M)\). Điểm thú vị là Kosaraju tự nhiên duyệt đồ thị ngưng tụ theo thứ tự topo xuôi, nên việc gán nghiệm thậm chí còn trực quan hơn: nếu SCC của \(x_i\) được duyệt sau SCC của \(\neg x_i\) thì gán \(x_i = \text{True}\). Tuy nhiên, Tarjan được ưa chuộng hơn trong phòng thi vì chỉ cần 1 lần DFS duy nhất và không phải đảo chiều đồ thị.

Nếu có mệnh đề chỉ gồm một biến duy nhất thì biểu diễn như thế nào?

Nếu bài toán yêu cầu biến \(x_i\) bắt buộc phải nhận True, ta có thể viết lại dưới dạng mệnh đề tuyển hai biến trùng nhau: \((x_i \lor x_i)\). Mệnh đề này sẽ sinh ra cung \(\neg x_i \to x_i\). Nếu \(\neg x_i\) xảy ra thì ép \(x_i\) phải xảy ra, tạo mâu thuẫn ngay lập tức nếu chọn \(\neg x_i\), buộc thuật toán phải chọn \(x_i = \text{True}\).

Nguồn tham khảo

  • CP-Algorithms - 2-SAT - Toàn cảnh lý thuyết 2-SAT và chứng minh tính đúng đắn của thuật toán gán nghiệm.
  • VNOI Wiki - 2-SAT - Đồ thị suy diễn, điều kiện có nghiệm và cách dựng nghiệm bằng thành phần liên thông mạnh (Tarjan, Kosaraju).
  • USACO Guide - Strongly Connected Components - Thuật toán Kosaraju, Tarjan và mục 2-SAT kèm bài tập áp dụng.
Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483