MAT3500 - Toán Rời Rạc: Ôn tập cuối kì

#discrete-mathematics #schoolwork
11/01/2025 34 Phút
Nội dung ôn tập môn Toán Rời Rạc của tôi cho cuối kì
Viết bởi: Yuk

Mục lục

Block

Lý thuyết đồ thị

Các Loại Đồ Thị

Đồ Thị Đầy Đủ (Complete Graph)

Một đồ thị đầy đủ là một đồ thị vô hướng mà giữa mọi cặp đỉnh trong đồ thị đều có một cạnh. Đối với một đồ thị đầy đủ, mọi đỉnh đều kết nối với tất cả các đỉnh còn lại trong đồ thị.

  • Ký hiệu: KnK_n, trong đó nn là số đỉnh của đồ thị.
  • Đặc điểm:
    • Số đỉnh: nn
    • Số cạnh: n(n−1)2\frac{n(n-1)}{2} (được tính theo công thức kết hợp 2 đỉnh từ nn đỉnh).
    • Tính chất: Đồ thị đầy đủ có tính liên thông cao nhất, nghĩa là giữa mọi cặp đỉnh đều có đường đi.
  • Ví dụ: Đối với K4K_4, đồ thị đầy đủ 4 đỉnh có số cạnh là 4(4−1)2=6\frac{4(4-1)}{2} = 6.

Đồ Thị Chu Trình (Cycle Graph)

Một đồ thị chu trình là một đồ thị vô hướng trong đó các đỉnh được sắp xếp thành một chuỗi khép kín, nghĩa là mỗi đỉnh được nối với hai đỉnh khác sao cho tất cả các đỉnh đều có bậc bằng 2.

  • Ký hiệu: CnC_n, trong đó nn là số đỉnh.
  • Đặc điểm:
    • Số đỉnh: nn
    • Số cạnh: nn
    • Tính chất: Đồ thị chu trình có hình dạng giống như một chuỗi các đỉnh nối với nhau, tạo thành một vòng khép kín.
  • Ví dụ: Đối với C4C_4, đồ thị chu trình với 4 đỉnh có số cạnh là 44 và bậc của mỗi đỉnh là 2.

Đồ Thị Bánh Xe (Wheel Graph)

Một đồ thị bánh xe là một đồ thị được tạo ra từ một đồ thị chu trình bằng cách thêm một đỉnh trung tâm và nối nó với tất cả các đỉnh của chu trình.

  • Ký hiệu: WnW_n, trong đó nn là số đỉnh trong đồ thị chu trình ban đầu (không bao gồm đỉnh trung tâm).
  • Đặc điểm:
    • Số đỉnh: n+1n+1
    • Số cạnh: 2n2n
    • Tính chất: Đồ thị bánh xe có một đỉnh trung tâm được kết nối với tất cả các đỉnh còn lại trong đồ thị chu trình.
  • Ví dụ: Đối với W4W_4, đồ thị bánh xe có 5 đỉnh và 8 cạnh.

Đồ Thị Khối-n Chiều (n-Dimensional Hypercube)

Một đồ thị khối-n chiều là một đồ thị mà mỗi đỉnh có thể biểu diễn bằng một chuỗi nhị phân dài nn và hai đỉnh được nối với nhau nếu chúng khác nhau ở đúng một vị trí trong chuỗi nhị phân.

  • Ký hiệu: QnQ_n, trong đó nn là số chiều.
  • Đặc điểm:
    • Số đỉnh: 2n2^n
    • Số cạnh: n×2n−1n \times 2^{n-1}
    • Tính chất: Đồ thị khối-n chiều có độ liên thông cao và được sử dụng trong các hệ thống mạng và lý thuyết mã hóa.
  • Ví dụ: Đối với Q3Q_3, đồ thị khối 3 chiều có 8 đỉnh và 12 cạnh.

Đồ thị hai phần

Định nghĩa

Một đồ thị hai phần (bipartite graph) là một đồ thị vô hướng G=(V,E)G = (V, E) mà tập đỉnh VV có thể được chia thành hai tập con V1V_1 và V2V_2 sao cho mọi cạnh trong đồ thị đều nối một đỉnh trong V1V_1 với một đỉnh trong V2V_2. Nói cách khác, không có cạnh nào nối hai đỉnh cùng thuộc một tập con.

Một cách khác để mô tả đồ thị hai phần là: Đồ thị GG là hai phần khi và chỉ khi tập đỉnh của nó có thể được phân chia thành hai phần sao cho không có cạnh nào nối hai đỉnh cùng thuộc một phần.

Tổng số bậc V1V_1 bằng tổng số bậc V2V_2

Điều kiện đồ thị hai phần

  1. Đồ thị hai phần có thể được tô màu các đỉnh bằng hai màu sao cho không có hai đỉnh kề nhau được tô cùng màu.
  2. Đồ thị này không có chu trình lẻ (odd cycle). Một đồ thị vô hướng có chu trình lẻ không thể là đồ thị hai phần.
  • Đặc điểm:
  • Tô màu đỉnh: Một đồ thị là đồ thị hai phần khi và chỉ khi có thể tô mỗi đỉnh bằng hai màu sao cho không có hai đỉnh kề nhau được tô cùng màu.
    • Nếu một đồ thị có thể tô như vậy, ta có thể phân chia tập đỉnh thành hai tập con V1V_1 và V2V_2, sao cho mọi cạnh đều nối một đỉnh thuộc V1V_1 với một đỉnh thuộc V2V_2.
  • Không có chu trình lẻ: Nếu đồ thị GG có một chu trình lẻ, thì đồ thị đó không thể là đồ thị hai phần. Điều này là vì trong một chu trình lẻ, không thể phân chia các đỉnh của chu trình thành hai nhóm sao cho các đỉnh kề nhau luôn thuộc hai nhóm khác nhau.

Chứng minh đồ thị hai phần

  • Nếu đồ thị GG là một đồ thị hai phần, thì có thể tô màu các đỉnh của GG bằng hai màu sao cho không có hai đỉnh kề nhau được tô cùng màu: Giả sử đồ thị G=(V,E)G = (V, E) là một đồ thị hai phần, nghĩa là tập đỉnh VV có thể được phân chia thành hai tập con V1V_1 và V2V_2. Tô màu các đỉnh trong V1V_1 bằng màu 1 và các đỉnh trong V2V_2 bằng màu 2. Do không có cạnh nào nối hai đỉnh trong cùng một tập con, ta có thể đảm bảo rằng các đỉnh kề nhau sẽ luôn có màu khác nhau.

  • Nếu có một cách tô màu các đỉnh của GG bằng hai màu sao cho không có hai đỉnh kề nhau được tô cùng màu, thì đồ thị GG là một đồ thị hai phần: Giả sử có một cách tô màu các đỉnh của GG sao cho không có hai đỉnh kề nhau được tô cùng màu. Từ đó, ta có thể phân chia tập đỉnh VV thành hai tập con V1V_1 và V2V_2, trong đó các đỉnh trong V1V_1 được tô màu 1 và các đỉnh trong V2V_2 được tô màu 2. Vì không có cạnh nào nối hai đỉnh trong cùng một tập, đồ thị GG là đồ thị hai phần.

  • Ví dụ: Xét đồ thị GG với các đỉnh V={A,B,C,D}V = \{A, B, C, D\} và các cạnh E={AB,AC,BD,CD}E = \{AB, AC, BD, CD\}. Đồ thị này có thể phân chia thành hai tập con:
  • V1={A,D}V_1 = \{A, D\} (tô màu 1)
  • V2={B,C}V_2 = \{B, C\} (tô màu 2)

Mọi cạnh trong đồ thị đều nối một đỉnh trong V1V_1 với một đỉnh trong V2V_2, vì vậy đây là đồ thị hai phần.

  • Kết luận: Một đồ thị vô hướng là đồ thị hai phần khi và chỉ khi có thể tô màu các đỉnh của nó bằng hai màu sao cho không có hai đỉnh kề nhau được tô cùng màu.

Tính liên thông trong đồ thị

Tính liên thông của một đồ thị chỉ ra rằng có thể đi từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác trong đồ thị. Một đồ thị vô hướng được gọi là liên thông nếu có một đường đi giữa mọi cặp đỉnh trong đồ thị. Ngược lại, đồ thị được gọi là không liên thông nếu có ít nhất một cặp đỉnh không có đường đi nối với nhau.

  • Đặc điểm:
  • Một đồ thị liên thông phải có ít nhất một đường đi từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác.
  • Đồ thị không liên thông có thể được chia thành nhiều thành phần liên thông.

Độ bền đỉnh (Vertex Connectivity) - κ(G)\kappa(G)

Độ bền đỉnh của một đồ thị là số lượng đỉnh tối thiểu cần loại bỏ để đồ thị trở thành không liên thông. Độ bền đỉnh được ký hiệu là κ(G)\kappa(G) và có thể được tính bằng cách xác định số đỉnh tối thiểu cần phải loại bỏ để phân tách đồ thị thành ít nhất hai thành phần liên thông.

  • Đặc điểm:
  • Độ bền đỉnh là một chỉ số quan trọng trong việc đánh giá tính ổn định của đồ thị.
  • Một đồ thị liên thông có độ bền đỉnh là một số nguyên không âm.

  • Đồ thị có độ bền đỉnh càng cao thì càng bền vững đối với việc loại bỏ các đỉnh.

  • Ví dụ:
  • Đồ thị chu trình C4C_4 có độ bền đỉnh κ(C4)=2\kappa(C_4) = 2 vì cần loại bỏ 2 đỉnh để làm đồ thị không liên thông.

Độ bền cạnh (Edge Connectivity) - λ(G)\lambda(G)

Độ bền cạnh của một đồ thị là số lượng cạnh tối thiểu cần loại bỏ để đồ thị trở thành không liên thông. Độ bền cạnh được ký hiệu là λ(G)\lambda(G) và có thể được tính bằng cách xác định số cạnh tối thiểu cần phải loại bỏ để làm đồ thị không còn liên thông.

  • Đặc điểm
  • Độ bền cạnh đánh giá mức độ ổn định của đồ thị trong việc bị phá vỡ bởi việc loại bỏ các cạnh.
  • Đồ thị có độ bền cạnh cao thì sẽ chịu ít tác động khi có các cạnh bị loại bỏ.

  • Tương tự như độ bền đỉnh, đồ thị càng có độ bền cạnh cao thì càng khó bị phân tách bằng cách loại bỏ các cạnh.

  • Ví dụ
  • Đồ thị chu trình C4C_4 có độ bền cạnh λ(C4)=2\lambda(C_4) = 2 vì cần loại bỏ 2 cạnh liên tiếp để đồ thị không còn liên thông.

Mối quan hệ giữa độ bền đỉnh và độ bền cạnh

Trong mọi đồ thị, ta có mối quan hệ sau giữa độ bền đỉnh và độ bền cạnh: κ(G)≤λ(G)\kappa(G) \leq \lambda(G) Điều này có nghĩa là độ bền đỉnh không bao giờ lớn hơn độ bền cạnh trong đồ thị.

  • Ví dụ
  • Trong đồ thị K4K_4 (đồ thị đầy đủ 4 đỉnh), độ bền đỉnh và độ bền cạnh đều là 3.

Đường đi và Chu trình Euler, Hamilton

Đường đi Euler

  • Định nghĩa: Một đường đi Euler trong đồ thị GG là một đường đi qua mỗi cạnh của GG đúng một lần. Đường đi này có thể đi qua đỉnh nhiều lần nhưng mỗi cạnh chỉ được sử dụng một lần.
  • Điều kiện tồn tại:
    • Đối với đồ thị vô hướng:
      • Đồ thị GG liên thông.
      • Có chính xác hai đỉnh có bậc lẻ.
    • Đối với đồ thị có hướng:
      • GG liên thông mạnh (hoặc yếu liên thông với đồ thị vô hướng tương ứng).
      • Số cung đi vào mỗi đỉnh uu bằng số cung đi ra mỗi đỉnh vv, ngoại trừ hai đỉnh đặc biệt:
        • Một đỉnh có số cung đi vào hơn số cung đi ra là 1.
        • Một đỉnh có số cung đi ra hơn số cung đi vào là 1.

Chu trình Euler

  • Định nghĩa: Một chu trình Euler là một đường đi Euler bắt đầu và kết thúc tại cùng một đỉnh.
  • Điều kiện tồn tại:
    • Đối với đồ thị vô hướng:
      • Đồ thị GG liên thông.
      • Tất cả các đỉnh của GG có bậc chẵn.
    • Đối với đồ thị có hướng:
      • GG liên thông mạnh.
      • Số cung đi vào mỗi đỉnh bằng số cung đi ra tại mỗi đỉnh.

Đặc điểm của Đường đi và Chu trình Euler

  • Đường đi Euler liên quan đến việc sử dụng tất cả các cạnh đúng một lần, không yêu cầu quay về đỉnh xuất phát.
  • Chu trình Euler yêu cầu sử dụng tất cả các cạnh đúng một lần và quay về đỉnh xuất phát.

Đường đi Hamilton

  • Định nghĩa: Một đường đi Hamilton trong đồ thị GG là một đường đi qua tất cả các đỉnh của GG đúng một lần (không cần đi qua tất cả các cạnh).
  • Điều kiện tồn tại:
    • Không có tiêu chuẩn đủ tổng quát, nhưng các điều kiện đủ thường được dùng:
      • Định lý Dirac: Nếu GG là đồ thị vô hướng đơn với ∣V∣=n≥3\mid V \mid = n \geq 3 và mọi đỉnh đều có bậc ≥n/2\geq n/2, thì GG có chứa đường đi Hamilton.
      • Định lý Ore: Nếu GG là đồ thị vô hướng đơn và với mọi cặp đỉnh không kề nhau u,vu, v, ta có deg⁡(u)+deg⁡(v)≥n\deg(u) + \deg(v) \geq n, thì GG có chứa đường đi Hamilton.

Chu trình Hamilton

  • Định nghĩa: Một chu trình Hamilton là một đường đi Hamilton bắt đầu và kết thúc tại cùng một đỉnh.
  • Điều kiện tồn tại:
    • Giống với đường đi Hamilton, không có tiêu chuẩn đủ tổng quát, nhưng các điều kiện trên cũng áp dụng cho chu trình Hamilton.
  • Một số tính chất có thể được sử dụng để chỉ ra một đồ thị không có chu trình Hamilton
    • Đồ thị có chứa đỉnh bậc 1 không có chu trình Hamilton
    • Nếu đỉnh v của đồ thị G có bậc 2 thì hai cạnh kề với v thuộc mọi chu trình Hamilton của G (nếu có)
    • Một chu trình Hamilton không chứa một chu trình con nào có số đỉnh nhỏ hơn nó

Đặc điểm của Đường đi và Chu trình Hamilton

  • Đường đi Hamilton đi qua tất cả các đỉnh của đồ thị đúng một lần, không yêu cầu quay về đỉnh xuất phát.
  • Chu trình Hamilton yêu cầu đi qua tất cả các đỉnh đúng một lần và quay về đỉnh xuất phát.
  • Khác với Euler, Hamilton quan tâm đến đỉnh, không phải cạnh.
Thuộc tính Euler Hamilton
Quan tâm đến Cạnh Đỉnh
Điều kiện tồn tại Dựa vào bậc và liên thông cạnh Không có điều kiện tổng quát, thường liên quan đến số đỉnh và bậc đỉnh
Đường đi Qua tất cả các cạnh đúng một lần Qua tất cả các đỉnh đúng một lần
Chu trình Qua tất cả các cạnh và quay lại đỉnh xuất phát Qua tất cả các đỉnh và quay lại đỉnh xuất phát

Tổng hợp thuật toán đồ thị

Duyệt chiều rộng (Breadth-First Search - BFS)

  • Thời gian: O(V+E)O(V + E).
  • Không gian: O(V)O(V).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ArrayList<Integer> bfsOfGraph(ArrayList<ArrayList<Integer>> adj) {
    int V = adj.size();
    ArrayList<Integer> bfs = new ArrayList<>();
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[V];

    queue.offer(0);

    while (!queue.isEmpty()) {
        int node = queue.poll();

        if (!visited[node]) {
            bfs.add(node);
            visited[node] = true;

            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                }
            }
        }
    }

    return bfs;
}
Java

Duyệt chiều sâu (Depth-First Search - DFS)

  • Thời gian: O(V+E)O(V + E).
  • Không gian: O(V)O(V).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Iterative
public ArrayList<Integer> dfsOfGraph(ArrayList<ArrayList<Integer>> adj) {
    int V = adj.size();
    ArrayList<Integer> dfs = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();
    boolean[] visited = new boolean[V];

    stack.push(0);

    while (!stack.isEmpty()) {
        int node = stack.pop();

        if (!visited[node]) {
            dfs.add(node);
            visited[node] = true;

            // Note: increment or decrement matter if order in output is require 
            // (eg. in order of original adj -> decrement)
            // Kinda like choosing to go left or right in trees
            for (int i = adj.get(node).size() - 1; i >= 0; i--) {
                int neighbor = adj.get(node).get(i);
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                }
            }
        }
    }

    return dfs;
}

// Recursive
public ArrayList<Integer> dfsOfGraph(ArrayList<ArrayList<Integer>> adj) {
    int V = adj.size();
    ArrayList<Integer> dfs = new ArrayList<>();
    boolean[] visited = new boolean[V];

    dfsHelper(0, adj, visited, dfs);

    return dfs;
}

private void dfsHelper(int node, ArrayList<ArrayList<Integer>> adj, boolean[] visited, ArrayList<Integer> dfs) {
    visited[node] = true;
    dfs.add(node);

    for (Integer neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfsHelper(neighbor, adj, visited, dfs);
        }
    }
}
Java

Thuật toán Dijkstra (Đường đi ngắn nhất)

  • Ma trận kề:
    • Thời gian: O(V2)O(V^2).
    • Không gian: O((V+E)log⁡V)O((V+E) \log V).
  • Danh sách kề:
    • Thời gian: O(V2)O(V^2).
    • Không gian: O(V+E)O(V+E).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
ArrayList<Integer> dijkstra(ArrayList<ArrayList<iPair>> adj, int src) {
    int V = adj.size();
    ArrayList<Integer> dist = new ArrayList<>(Collections.nCopies(V, Integer.MAX_VALUE));
    PriorityQueue<iPair> pq = new PriorityQueue<>((a, b) -> a.second - b.second);
    
    dist.set(src, 0);
    pq.add(new iPair(src, 0));
    
    while (!pq.isEmpty()) {
        iPair current = pq.poll();
        int u = current.first;
        int d = current.second;

        if (d > dist.get(u)) continue;

        for (iPair neighbor : adj.get(u)) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (dist.get(u) + weight < dist.get(v)) {
                dist.set(v, dist.get(u) + weight);
                pq.add(new iPair(v, dist.get(v)));
            }
        }
    }
    return dist;
}
Java

Thuật toán Kruskal (Cây bao trùm nhỏ nhất)

  • Thời gian: O(Elog⁡E)O(E \log E).
  • Không gian: O(V+E)O(V+E).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Kruskal {
    static class Edge {
        int src, dest, weight;
        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }
    
    // Find the root of the set containing element x
    static int find(int parent[], int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent, parent[x]);
    }

    // Union by rank
    static void union(int parent[], int rank[], int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    // Function to find MST using Kruskal's algorithm
    public static ArrayList<Edge> kruskal(int V, ArrayList<Edge> edges) {
        // Sort the edges by weight
        Collections.sort(edges, Comparator.comparingInt(e -> e.weight));
        
        int[] parent = new int[V];
        int[] rank = new int[V];
        
        // Initialize disjoint sets
        for (int i = 0; i < V; i++) {
            parent[i] = i;
            rank[i] = 0;
        }

        ArrayList<Edge> mst = new ArrayList<>();
        for (Edge edge : edges) {
            int x = find(parent, edge.src);
            int y = find(parent, edge.dest);
            
            if (x != y) {
                mst.add(edge);
                union(parent, rank, x, y);
            }
        }

        return mst;
    }

}
Java

Thuật toán Prim (Cây bao trùm nhỏ nhất)

  • Ma trận kề:
    • Thời gian: O(V2)O(V^2).
    • Không gian: O(V2)O(V^2).
  • Danh sách kề:
    • Thời gian: O((V+E)log⁡V)O((V+E) \log V).
    • Không gian: O(V+E)O(V+E).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Prim {
    static class Edge {
        int src, dest, weight;
        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    // Function to find MST using Prim's algorithm
    public static ArrayList<Edge> prim(int V, ArrayList<ArrayList<Edge>> adj) {
        // Priority queue to select the edge with the minimum weight
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        
        // To keep track of vertices included in the MST
        boolean[] inMST = new boolean[V];
        
        ArrayList<Edge> mst = new ArrayList<>();
        
        // Start from vertex 0
        inMST[0] = true;
        
        // Add edges of vertex 0 to the priority queue
        for (Edge edge : adj.get(0)) {
            pq.add(edge);
        }

        while (!pq.isEmpty()) {
            // Get the edge with minimum weight
            Edge edge = pq.poll();
            
            int u = edge.src;
            int v = edge.dest;
            
            // If v is not included in the MST
            if (!inMST[v]) {
                mst.add(edge);
                inMST[v] = true;
                
                // Add all edges from v to the priority queue
                for (Edge nextEdge : adj.get(v)) {
                    if (!inMST[nextEdge.dest]) {
                        pq.add(nextEdge);
                    }
                }
            }
        }

        return mst;
    }

}
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Graph {
    int vertices;
    ArrayList<ArrayList<Integer[]>> adjacencyList; // 0: destination, 1: weight

    Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    // Undirected graph
    void addEdge(int src, int dest, int weight) {
        adjacencyList.get(src).add(new Integer[]{dest, weight});
        adjacencyList.get(dest).add(new Integer[]{dest, weight});
    }
}

public class PrimDriver {
    public static void main(String[] args) {
        // Example graph with 5 vertices
        Graph graph = new Graph(5);

        // Adding edges (src, dest, weight)
        graph.addEdge(0, 1, 2);
        graph.addEdge(0, 3, 6);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3, 8);
        graph.addEdge(1, 4, 5);
        graph.addEdge(2, 4, 7);
        graph.addEdge(3, 4, 9);

        // Call Prim's algorithm implementation
        List<int[]> mst = primMST(graph);

        // Output the MST
        System.out.println("Minimum Spanning Tree (Edge List):");
        for (int[] edge : mst) {
            System.out.println("(" + edge[0] + ", " + edge[1] + ") with weight " + edge[2]);
        }
    }

    public static List<int[]> primMST(Graph graph) {
        int v = graph.vertices;
        ArrayList<ArrayList<Integer[]>> adj = graph.adjacencyList;
        List<int[]> mst = new ArrayList<>();

        PriorityQueue<Integer[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]); // Min-heap for edges
        boolean[] visited = new boolean[v];
        Arrays.fill(visited, false);

        // Start from vertex 0
        visited[0] = true;
        for (Integer[] edge : adj.get(0)) {
            pq.add(new Integer[]{0, edge[0], edge[1]}); // Add edges from vertex 0
        }

        while (!pq.isEmpty()) {
            Integer[] edge = pq.poll(); // {source, destination, weight}
            int src = edge[0];
            int dest = edge[1];
            int weight = edge[2];

            // If the destination is already visited, skip it
            if (visited[dest]) {
                continue;
            }

            // Add the edge to the MST
            mst.add(new int[]{src, dest, weight});
            visited[dest] = true;

            // Add all edges from the new vertex to the priority queue
            for (Integer[] next : adj.get(dest)) {
                if (!visited[next[0]]) {
                    pq.add(new Integer[]{dest, next[0], next[1]});
                }
            }
        }

        return mst;
    }

}
Java

Tổng hợp định lý và mệnh đề

Đồ thị

Định lý bắt tay (Handshaking Lemma) Cho G=(V,E)G=(V, E) là một đồ thị vô hướng có mm cạnh, ta có:

2m=∑v∈Vdeg⁡(v)2m=\sum_{v \in V} \deg(v)
Block

Một đồ thị vô hướng có một số chẵn các đỉnh có bậc lẻ.

Block

Cho G=(V,E)G=(V,E) là một đồ thị có hướng, ta có:

∣E∣=∑v∈Vdeg⁡−(v)=∑v∈Vdeg⁡+(v)\mid E \mid = \sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v)
Block

Một đơn đồ thị vô hướng G=(V,E)G=(V,E) là một đồ thị hai phần khi và chỉ khi có một cách tô màu mỗi đỉnh của GG bằng hai màu sao cho không có hai đỉnh kề nhau được tô cùng màu.

Block

Định lý Hall (Hall’s Marriage Theorem) Cho G=(V1∪V2,E)G=(V_1 \cup V_2, E) là một đồ thị hai phần. Tồn tại một ghép cặp M⊂EM \subset E bao phủ V1V_1 khi và chỉ khi với mọi S⊂V1,∣S∣≤∣NG(S)∣S \subset V_1, \mid S \mid \leq \mid N_G(S) \mid.

Block

Cho G=(V,E)G=(V, E) là một đồ thị vô hướng liên thông có ít nhất hai đỉnh. Với hai đỉnh bất kỳ u,v∈Vu, v \in V của GG, tồn tại một đường đi đơn giữa uu và vv.

Block

Cho GG là một đồ thị với ma trận kề AA tương ứng với thứu tự các đỉnh v1,v2,…,vnv_1, v_2, \ldots, v_n. Số các đường đi khác nhau độ dài rr từ viv_i tới vjv_j, trong đó rr là một số nguyên dương, bằng giá trị AijA_{ij} của phần tử (i,ji, j) của ma trận ArA^r.

Block

Đường đi

Một đa đồ thị vô hướng liên thông có một chu trình Euler khi và chỉ khi mỗi đỉnh của đồ thị có bậc chẵn.

Block

Một đa đồ thị vô hướng liên thông GG có đường đi Euler nhưng không có chu trình Euler khi và chỉ khi có đúng hai đỉnh của GG có bậc lẻ.

Block

Định lý Dirac (Dirac’s Theorem) Nếu G=(V,E)G=(V,E) là một đơn đồ thị vô hướng gồm n≥3n \geq 3 đỉnh thỏa mãn điều kiện bậc của mỗi đỉnh trong GG lớn hơn hoặc bằng n/3n / 3 thì GG có một chu trình Hamilton.

Block

Định lý Ore (Ore’s Theorem) Nếu G=(V,E)G = (V, E) là một đơn đồ thị vô hướng gồm nn đỉnh (n≥3)(n \geq 3) thỏa mãn điều kiện deg⁡(u)+deg⁡(v)≥n\deg(u) + \deg(v) \geq n với mọi cặp đỉnh u,vu, v không kề nhau trong GG thì GG có một chu trình Hamilton.

Block

Công thức Euler (Euler’s formula) Giả sử GG là một đơn đồ thị phẳng và liên thông gồm mm cạnh, nn đỉnh, và rr miền. Ta có n−m+r=2n - m + r = 2.

Block

Định lý Kuratowski (Kuratowski’s theorem) GG là đồ thị phẳng khi và chỉ khi nó không chứa bất kỳ đồ thị nào đồng phôi với K5K_5 hoặc K3,3K_{3,3}.

Block

Định lý bốn màu (4 Color theorem) Với mọi đồ thị phẳng GG, ta luôn có χ(G)≤4\chi(G) \leq 4. Chú ý rằng sau đó được chứng minh lại là sai và χ(G)≤6\chi(G) \leq 6.

Block

Cho G=(V,E)G = (V,E) là đơn đồ thị vô hướng có nn đỉnh. Ta có χ(G)≤Δ(G)+1\chi(G) \leq \Delta(G) + 1.

Block

Định lý Brook (Brook’s theorem) Nếu GG không phải là một chu trình độ dài lẻ hoặc một đồ thị đầy đủ thì χ(G)≤Δ(G)\chi(G) \leq \Delta(G).

Block

Cây

Một đồ thị vô hướng GG là một cây khi và chỉ khi giữa hai đỉnh bất kỳ của GG tồn tại một đường đi đơn duy nhất.

Block

Mọi cây T=(V,E)T = (V, E) với ∣V∣≥2\mid V \mid \geq 2 có ít nhất hai đỉnh bậc 1.

Block

Mọi cây gồm nn đỉnh có chính xác n−1n − 1 cạnh.

Block

Mọi cây mm-phân đầy đủ (m≥1)(m \geq 1) với ii đỉnh trong có chính xác n=m⋅i+1n = m \cdot i + 1 đỉnh.

Block

Một cây m-phân đầy đủ với:

  • (i) n đỉnh có i = (n − 1)/m đỉnh trong và ℓ = ((m − 1)n + 1)/m đỉnh lá;
  • (ii) i đỉnh trong có n = mi + 1 đỉnh và ℓ = (m − 1)i + 1 đỉnh lá;
  • (iii) ℓ đỉnh lá có n = (mℓ − 1)/(m − 1) đỉnh và i = (ℓ − 1)/(m − 1) đỉnh trong.
Block

Mọi thuật toán sắp xếp n phần tử nào đó dựa trên các phép so sánh hai phần tử bất kỳ cần sử dụng ít nhất ⌈log2(n!)⌉ phép so sánh trong trường hợp xấu nhất.

Block

Mọi đơn đồ thị liên thông GG có một cây bao trùm.

Block

Bài tập đồ thị

Bài 7.1

Cho GG là một đồ thị vô hướng có nn đỉnh và mm cạnh. Gọi Δ(G)\Delta(G) và δ(G)\delta(G) lần lượt là bậc lớn nhất và nhỏ nhất của một đỉnh của GG. Chứng minh rằng δ(G)≤2mn≤Δ(G)\delta(G) \leq \frac{2m}{n} \leq \Delta(G).

Giả sử coˊ ıˊt nhaˆˊt một đỉnh coˊ bậc ba˘ˋng δ(G)n⋅δ(G)≤∑i=1ndi=2m  ⟹  δ(G)≤2mn(1)\begin{gather*} \text{Giả sử có ít nhất một đỉnh có bậc bằng } \delta(G) \\ n \cdot \delta(G) \leq \sum^n_{i=1} d_i = 2m \\ \implies \delta(G) \leq \frac{2m}{n} \quad (1) \end{gather*}
Block
Giả sử taˆˊt cả đỉnh coˊ bậc ıˊt nhaˆˊt laˋ Δ(G)n⋅δ(G)≥∑i=1ndi=2m  ⟹  δ(G)≥2mn(2)\begin{gather*} \text{Giả sử tất cả đỉnh có bậc ít nhất là } \Delta(G) \\ n \cdot \delta(G) \geq \sum^n_{i=1} d_i = 2m \\ \implies \delta(G) \geq \frac{2m}{n} \quad (2) \end{gather*}
Block
  • Từ (1) và (2) có ĐPCM.
Bài 7.6

Đồ thị bù (complement graph) của một đơn đồ thị vô hướng G=(V,E)G = (V, E), ký hiệu Gˉ\bar{G}, là đồ thị có tập đỉnh Vˉ=V\bar{V} = V và tập cạnh E=[V]2 EE = [V]^2 \ E ={uv∣u,v∈V= \{uv \mid u, v \in V  vaˋ uv∉E}\text{ và } uv \notin E\}.

Giả sử GG và HH là các đơn đồ thị thỏa mãn G≃HG ≃ H. Chứng minh rằng Gˉ≃Hˉ\bar{G} ≃ \bar{H}.

Ta có:

  • uv∈E(G)uv \in E(G) thì f(u)f(v)∈E(H)f(u)f(v) \in E(H).

  • uv∉E(G)uv \notin E(G) thì f(u)f(v)∉E(H)f(u)f(v) \notin E(H).

  • Nếu uv∈Eˉ(G)uv \in \bar{E}(G) thì tức là uv∉E(G)uv \notin E(G), dẫn đến f(u)f(v)∉E(H)f(u)f(v) \notin E(H) hay f(u)f(v)∈Eˉ(H)f(u)f(v) \in \bar{E}(H).
  • Nếu uv∉Eˉ(G)uv \notin \bar{E}(G) thì tức là uv∈E(G)uv \in E(G), dẫn đến f(u)f(v)∈E(H)f(u)f(v) \in E(H) hay f(u)f(v)∉Eˉ(H)f(u)f(v) \notin \bar{E}(H).

Các tính chất vẫn được bảo toàn, ta có ĐPCM.

Bài 7.7

Tìm đồ thị tự bù với 5 cạnh -> xây dưng từ K5K_5.

Bài 7.21

Định lý Dirac (Dirac’s Theorem) Nếu G=(V,E)G=(V,E) là một đơn đồ thị vô hướng gồm n≥3n \geq 3 đỉnh thỏa mãn điều kiện bậc của mỗi đỉnh trong GG lớn hơn hoặc bằng n/3n / 3 thì GG có một chu trình Hamilton.

Block

Định lý Ore (Ore’s Theorem) Nếu G=(V,E)G = (V, E) là một đơn đồ thị vô hướng gồm nn đỉnh (n≥3)(n \geq 3) thỏa mãn điều kiện deg⁡(u)+deg⁡(v)≥n\deg(u) + \deg(v) \geq n với mọi cặp đỉnh u,vu, v không kề nhau trong GG thì GG có một chu trình Hamilton.

Block

Chứng minh định lý Dirac bằng định lý Ore.

Giả sử GG thỏa mãn điều kiện của định lý Dirac:

δ(G)≥n2\delta(G) \geq \frac{n}{2}
Block

Vậy mọi đỉnh của GG sẽ thỏa mãn:

deg⁡(u)≥n2,∀u∈V\deg(u) \geq \frac{n}{2}, \forall u \in V
Block

Xét 2 đỉnh không kề nhau u,vu, v:

deg⁡(u)+deg⁡(v)≥n\deg(u) + \deg(v) \geq n
Block

Vậy định lý Dirac là một trường hợp đặc biết của định lý Ore.

Đại số Boolean

Bài tập đại số Boolean

Bài 8.1

Tính 1⋅0+(0+1)‾1 \cdot 0 + \overline{(0 + 1)}.

1⋅0=00+1=11ˉ=00+0=0\begin{gather*} 1 \cdot 0 = 0 \\ 0 + 1 = 1 \\ \bar{1} = 0 \\ 0 + 0 = 0 \end{gather*}
Block
Bài 8.2

Dịch tương đương loogic (T∧T)∨¬F≡T(T \wedge T) \vee \neg F \equiv T sang một đẳng thức trong Đại số Boolean.

(1⋅1)+0‾=1(1 \cdot 1) + \overline{0} = 1
Block
Bài 8.3
  • (a) Lập bảng giá trị của các hàm Boole sau:
(1)F1(x,y,z)=xyˉz+xˉyˉzˉ(2)F2(x,y,z)=x(yz+yˉzˉ)\begin{align*} & (1) \quad F_1(x, y, z) = x \bar{y} z + \bar{x} \bar{y} \bar{z} \\ & (2) \quad F_2(x, y, z) = x (yz + \bar{y}\bar{z}) \end{align*}
Block
xx yy zz xˉ\bar{x} yˉ\bar{y} zˉ\bar{z} xyˉzx \bar{y} z xˉyˉzˉ\bar{x} \bar{y} \bar{z} F1(x,y,z)F_1(x, y, z)
0 0 0 1 1 1 0 1 1
0 0 1 1 1 0 0 0 0
0 1 0 1 0 1 0 0 0
0 1 1 1 0 0 0 0 0
1 0 0 0 1 1 0 0 0
1 0 1 0 1 0 1 0 1
1 1 0 0 0 1 0 0 0
1 1 1 0 0 0 0 0 0
xx yy zz yˉ\bar{y} zˉ\bar{z} yzy z yˉzˉ\bar{y} \bar{z} yz+yˉzˉy z + \bar{y} \bar{z} F2(x,y,z)F_2(x, y, z)
0 0 0 1 1 0 1 1 0
0 0 1 1 0 0 0 0 0
0 1 0 0 1 0 0 0 0
0 1 1 0 0 1 0 1 0
1 0 0 1 1 0 1 1 1
1 0 1 1 0 0 0 0 0
1 1 0 0 1 0 0 0 0
1 1 1 0 0 1 0 1 1
  • (b) Biểu diễn mỗi hàm ở phần (a) trên một khối lập phương Q3Q_3 bằng cách đánh dấu các đỉnh tại đó hàm đạt giá trị 1. (8 đỉnh ứng với 8 cột)
Bài 8.4

Sử dụng luật De Morgan, ta có thể biểu diễn phép toán ++ theo hai phép toán ⋅\cdot và ˉ\bar{ } , từ đó có thể biểu diễn mọi hàm Boole bằng một biểu thức chỉ chứa hai phép toán đó. Hãy tìm một biểu diễn như vậy của các hàm sau:

(1)F1(x,y)=x+y(2)F2(x,y,z)=xˉ(x+yˉ)+z\begin{align*} & (1) \quad F_1(x, y) = x + y \\ & (2) \quad F_2(x, y, z) = \bar{x}(x+\bar{y})+z \end{align*}
Block
(1)F1(x,y)=x+y=xˉ⋅yˉ‾(2)F2(x,y,z)=xˉ(x+yˉ)+z=xˉ(xˉ⋅y‾)+z=xˉ⋅xˉ⋅y‾+z=xˉ⋅xˉ⋅y‾‾⋅zˉ‾\begin{align*} & (1) \quad F_1(x, y) = x + y = \overline{\bar{x} \cdot \bar{y}} \\ & (2) \quad F_2(x, y, z) = \bar{x}(x+\bar{y})+z \\ & \qquad = \bar{x}(\overline{\bar{x} \cdot y}) + z \\ & \qquad = \bar{x} \cdot \overline{\bar{x} \cdot y} + z \\ & \qquad = \overline{\overline{\bar{x} \cdot \overline{\bar{x} \cdot y}} \cdot \bar{z}} \end{align*}
Block
Bài 8.5

Sử dụng luật De Morgan, ta có thể biểu diễn mọi hàm Boole bằng một biểu thức chỉ chứa hai phép toán ++ và ˉ\bar{ } . Tìm một biểu diễn như vậy của các hàm sau:

(1)F1(x,y)=xy‾(2)F2(x,y,z)=x+yˉ(xˉ+z)\begin{align*} & (1) \quad F_1(x, y) = \overline{xy} \\ & (2) \quad F_2(x, y, z) = x + \bar{y}(\bar{x} + z) \end{align*}
Block
(1)F1(x,y)=xy‾=xˉ+yˉ‾‾(2)F2(x,y,z)=x+yˉ(xˉ+z)=x+yˉ+xˉ+z‾‾‾\begin{align*} & (1) \quad F_1(x, y) = \overline{xy} = \overline{\overline{\bar{x} + \bar{y}}} \\ & (2) \quad F_2(x, y, z) = x + \bar{y}(\bar{x} + z)\\ & \qquad = x + \overline{\overline{\bar{y} + \overline{\bar{x} + z}}} \end{align*}
Block

Mạch tổ hợp

Bài 8.6

Vẽ các mạch tổ hợp có đầu ra:

(1)xˉ(y+zˉ)‾(2)(x+y+z)(xˉ+yˉ+zˉ)\begin{align*} & (1) \quad \bar{x} \overline{(y + \bar{z})} \\ & (2) \quad (x + y + z)(\bar{x} + \bar{y} + \bar{z}) \end{align*}
Block
1
2
3
4
5
6
7
8
9
Mạch (1):

x --->NOT----------------|
                         AND---> out
                         |
y ---------OR--->NOT-----|
           |
           |
z --->NOT--|
Markdown
1
2
3
4
5
6
7
8
9
10
11
12
Mạch (2):
 x----|
      |
 y----OR----|
            |
 z----------OR---|
                 |
!x----|          AND---> out
      |          |
!y----OR----|    |
            |    |
!z----------OR---|
Markdown
Bài 8.7

Có tất cả bao nhiêu hàm Boole bậc nn khác nhau?

22n2^{2^n}
Block
  • n biến, mỗi biến có thể là 0 hoặc 1, cả hàm có thể cho kết quả 0 hoặc 1.
Bài 8.8

Bằng cách sử dụng bảng để biểu diễn các hàm Boole, hãy chứng minh luật phân phối x+yz=(x+y)(x+z)x + yz = (x + y)(x + z).

xx yy zz yzyz x+yzx + yz x+yx + y x+zx + z (x+y)(x+z)(x + y)(x + z)
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1
Bài 8.9

Bằng cách sử dụng bảng để biểu diễn các hàm Boole, hãy chứng minh luật hấp thụ x(x+y) = x.

xx yy x+yx + y x(x+y)x(x + y)
0 0 0 0
0 1 1 0
1 0 1 1
1 1 1 1
Bài 8.10

Tìm một biểu diễn của hàm Boole F(x,y,z)F(x, y, z) biết rằng FF nhận giá trị 1 khi và chỉ khi:

  • (a) có đúng 2 trong 3 biến x,y,zx, y, z nhận giá trị 1.
  • (b) có một số chẵn biến nhận giá trị 1.
(a)F(x,y,z)=(x⋅y⋅zˉ)+(x⋅yˉ⋅z)+(xˉ⋅y⋅z)(a) \quad F(x, y, z) = (x \cdot y \cdot \bar{z}) + (x \cdot \bar{y} \cdot z) + (\bar{x} \cdot y \cdot z)
Block
(b)F(x,y,z)=(xˉ⋅yˉ⋅zˉ)+(x⋅y⋅zˉ)+(x⋅yˉ⋅z)+(xˉ⋅y⋅z)(b) \quad F(x, y, z) = (\bar{x} \cdot \bar{y} \cdot \bar{z}) + (x \cdot y \cdot \bar{z}) + (x \cdot \bar{y} \cdot z) + (\bar{x} \cdot y \cdot z)
Block

Tổng tiểu hạng

Bài 8.11

Tìm biểu diễn dưới dạng tổng của các tiểu hạng (minterm) của các hàm sau:

(1)F1(x,y,z)=(x+zˉ)y(2)F2(x,y,z)=xyˉ+yzˉ\begin{align*} & (1) \quad F_1(x, y, z) = (x + \bar{z})y \\ & (2) \quad F_2(x, y, z) = x\bar{y} + y\bar{z} \end{align*}
Block

Tổng tiểu hạng (sum of minterms) là một cách biểu diễn hàm Boole dưới dạng một tổng của các tiểu hạng. Mỗi tiểu hạng (minterm) là một biểu thức Boole mà trong đó tất cả các biến xuất hiện với giá trị cụ thể (hoặc là chính biến, hoặc là phủ định của biến). Mỗi tiểu hạng đại diện cho một kết quả đầu ra của hàm Boole mà tại đó hàm có giá trị bằng 1.

Block
(a)F1(x,y,z)=x⋅y⋅zˉ+x⋅y⋅z+xˉ⋅y⋅zˉ(a) \quad F_1(x, y, z) = x \cdot y \cdot \bar{z} + x \cdot y \cdot z + \bar{x} \cdot y \cdot \bar{z}
Block
(b)F2(x,y,z)=x⋅yˉ⋅zˉ+x⋅yˉ⋅z+x⋅y⋅zˉ+xˉ⋅y⋅zˉ(b) \quad F_2(x, y, z) = x \cdot \bar{y} \cdot \bar{z} + x \cdot \bar{y} \cdot z + x \cdot y \cdot \bar{z} + \bar{x} \cdot y \cdot \bar{z}
Block
Bài 8.12

Cho:

xx yy x∣y(x NAND y)x \mid y (x \mathbf{\text{ NAND }} y) x↓y(x NOR y)x \downarrow y (x \mathbf{\text{ NOR }} y)
1 1 0 0
1 0 1 0
0 1 1 0
0 0 1 1

Chứng minh rằng:

(a)xˉ=x∣x(b)xy=(x∣y)∣(x∣y)(c)x+y=(x∣x)∣(y∣y)\begin{gather*} (a) \quad \bar{x} = x \mid x \\ (b) \quad xy = (x \mid y) \mid (x \mid y) \\ (c) \quad x + y = (x \mid x) \mid (y \mid y) \end{gather*}
Block
  • (Bảng chân trị)
x∣y=x⋅y‾x \mid y = \overline{x \cdot y}
Block
Bài 8.13

Chứng minh rằng:

(a)xˉ=x↓x(b)xy=(x↓y)↓(x↓y)(c)x+y=(x↓x)↓(y↓y)\begin{gather*} (a) \quad \bar{x} = x \downarrow x \\ (b) \quad xy = (x \downarrow y) \downarrow (x \downarrow y) \\ (c) \quad x + y = (x \downarrow x) \downarrow (y \downarrow y) \end{gather*}
Block
  • (Bảng chân trị)
x↓y=x+y‾x \downarrow y = \overline{x + y}
Block

Sơ đồ Karnaugh và phương pháp Quine-McCluskey

Bài 8.14

Dùng sơ đồ Karnaugh và phương pháp Quine-McCluskey để rút gọn các khai triển tổng các tích sau:

(1)xyzˉ+xyˉzˉ+xˉyzˉ+xˉyˉzˉ(2)xyˉz+xˉyˉz+xyˉzˉ+xˉyˉzˉ+xyˉzˉ(3)xyz+xyˉzˉ+xˉyzˉ+xˉyˉzˉ+xyz+xˉyz+xˉyˉz\begin{gather*} (1) \quad xy\bar{z} + x\bar{y}\bar{z} + \bar{x}y\bar{z} + \bar{x}\bar{y}\bar{z} \\ (2) \quad x\bar{y}z + \bar{x}\bar{y}z + x\bar{y}\bar{z} + \bar{x}\bar{y}\bar{z} + x\bar{y}\bar{z} \\ (3) \quad xyz + x\bar{y}\bar{z} + \bar{x}y\bar{z} + \bar{x}\bar{y}\bar{z} + xyz + \bar{x}yz + \bar{x}\bar{y}z \end{gather*}
Block
  • Bảng Karnaugh (K-Map) cho 3 biến:
  yzyz yzˉy\bar{z} yˉzˉ\bar{y}\bar{z} yˉz\bar{y}z
xx xyzxyz xyzˉxy\bar{z} xyˉzˉx\bar{y}\bar{z} xyˉzx\bar{y}z
xˉ\bar{x} xˉyz\bar{x}yz xˉyzˉ\bar{x}y\bar{z} xˉyˉzˉ\bar{x}\bar{y}\bar{z} xˉyˉz\bar{x}\bar{y}z
  • K-Map (1)
  yzyz yzˉy\bar{z} yˉzˉ\bar{y}\bar{z} yˉz\bar{y}z
xx   1 1  
xˉ\bar{x}   1 1  

Vậy xyzˉ+xyˉzˉ+xˉyzˉ+xˉyˉzˉ≡zˉxy\bar{z} + x\bar{y}\bar{z} + \bar{x}y\bar{z} + \bar{x}\bar{y}\bar{z} \equiv \bar{z}

  • Quine-McCluskey (1)
Tiểu hạng Chuỗi nhị phân Số chữ số 1
xyzˉxy\bar{z} 110 2
xyˉzˉx\bar{y}\bar{z} 100 1
xˉyzˉ\bar{x}y\bar{z} 010 1
xˉyˉzˉ\bar{x}\bar{y}\bar{z} 000 0

Nhóm theo số chữ số 1:

  • 0 chữ số 1: 000
  • 1 chữ số 1: 100, 010
  • 2 chữ số 1: 110

Rút gọn bằng cách so sánh các chuỗi chỉ khác nhau 1 bit:

  • 000, 010 -> –0 -> zˉ\bar{z}
  • 110, 100 -> –0 -> zˉ\bar{z}
  • 000, 100 -> –0 -> zˉ\bar{z}
  • 110, 010 -> –0 -> zˉ\bar{z}

Vậy xyzˉ+xyˉzˉ+xˉyzˉ+xˉyˉzˉ≡zˉxy\bar{z} + x\bar{y}\bar{z} + \bar{x}y\bar{z} + \bar{x}\bar{y}\bar{z} \equiv \bar{z}

Bài 8.15

Đôi khi một hệ thống đèn cố định được điều khiển bởi hai hay nhiều công tắc. Các mạch điện cần được thiết kế sao cho khi ấn một công tắc bất kỳ thì hệ thống đèn đang bật sẽ tắt và hệ thống đèn đang tắt sẽ bật. Hãy thử thiết kế mạch theo yêu cầu với ba công tắc.

Tài liệu tham khảo

***