Mục lục

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: \(K_n\), trong đó \(n\) là số đỉnh của đồ thị.
• Đặc điểm:
  • Số đỉnh: \(n\)
  • Số cạnh: \(\frac{n(n-1)}{2}\) (được tính theo công thức kết hợp 2 đỉnh từ \(n\) đỉ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 \(K_4\), đồ thị đầy đủ 4 đỉnh có số cạnh là \(\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: \(C_n\), trong đó \(n\) là số đỉnh.
• Đặc điểm:
  • Số đỉnh: \(n\)
  • Số cạnh: \(n\)
  • 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 \(C_4\), đồ thị chu trình với 4 đỉnh có số cạnh là \(4\) 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: \(W_n\), trong đó \(n\) 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+1\)
  • Số cạnh: \(2n\)
  • 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 \(W_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 \(n\) 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: \(Q_n\), trong đó \(n\) là số chiều.
• Đặc điểm:
  • Số đỉnh: \(2^n\)
  • Số cạnh: \(n \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 \(Q_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)\) mà tập đỉnh \(V\) có thể được chia thành hai tập con \(V_1\) và \(V_2\) sao cho mọi cạnh trong đồ thị đều nối một đỉnh trong \(V_1\) với một đỉnh trong \(V_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ị \(G\) 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 \(V_1\) bằng tổng số bậc \(V_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 \(V_1\) và \(V_2\), sao cho mọi cạnh đều nối một đỉnh thuộc \(V_1\) với một đỉnh thuộc \(V_2\).
• Không có chu trình lẻ: Nếu đồ thị \(G\) 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ị \(G\) là một đồ thị hai phần, thì có thể tô màu các đỉnh của \(G\) 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)\) là một đồ thị hai phần, nghĩa là tập đỉnh \(V\) có thể được phân chia thành hai tập con \(V_1\) và \(V_2\). Tô màu các đỉnh trong \(V_1\) bằng màu 1 và các đỉnh trong \(V_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 \(G\) bằng hai màu sao cho không có hai đỉnh kề nhau được tô cùng màu, thì đồ thị \(G\) là một đồ thị hai phần: Giả sử có một cách tô màu các đỉnh của \(G\) 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 \(V\) thành hai tập con \(V_1\) và \(V_2\), trong đó các đỉnh trong \(V_1\) được tô màu 1 và các đỉnh trong \(V_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ị \(G\) là đồ thị hai phần.

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

Mọi cạnh trong đồ thị đều nối một đỉnh trong \(V_1\) với một đỉnh trong \(V_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) - \(\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à \(\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 \(C_4\) có độ bền đỉnh \(\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) - \(\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à \(\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 \(C_4\) có độ bền cạnh \(\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: \(\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ị \(K_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ị \(G\) là một đường đi qua mỗi cạnh của \(G\) đú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ị \(G\) liên thông.
    • Có chính xác hai đỉnh có bậc lẻ.
  • Đối với đồ thị có hướng:
    • \(G\) 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 \(u\) bằng số cung đi ra mỗi đỉnh \(v\), 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ị \(G\) liên thông.
    • Tất cả các đỉnh của \(G\) có bậc chẵn.
  • Đối với đồ thị có hướng:
    • \(G\) 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ị \(G\) là một đường đi qua tất cả các đỉnh của \(G\) đú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 \(G\) là đồ thị vô hướng đơn với \(\mid V \mid = n \geq 3\) và mọi đỉnh đều có bậc \(\geq n/2\), thì \(G\) có chứa đường đi Hamilton.
    • Định lý Ore: Nếu \(G\) là đồ thị vô hướng đơn và với mọi cặp đỉnh không kề nhau \(u, v\), ta có \(\deg(u) + \deg(v) \geq n\), thì \(G\) 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.

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)\).
• Không gian: \(O(V)\).

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;
}

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

• Thời gian: \(O(V + E)\).
• Không gian: \(O(V)\).

// 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);
        }
    }
}

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

• Ma trận kề:
  • Thời gian: \(O(V^2)\).
  • Không gian: \(O((V+E) \log V)\).
• Danh sách kề:
  • Thời gian: \(O(V^2)\).
  • Không gian: \(O(V+E)\).

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;
}

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

• Thời gian: \(O(E \log E)\).
• Không gian: \(O(V+E)\).

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;
    }

}

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

• Ma trận kề:
  • Thời gian: \(O(V^2)\).
  • Không gian: \(O(V^2)\).
• Danh sách kề:
  • Thời gian: \(O((V+E) \log V)\).
  • Không gian: \(O(V+E)\).

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;
    }

}

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;
    }

}

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

Đồ thị

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

\[2m=\sum_{v \in V} \deg(v)\]

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

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

\[\mid E \mid = \sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v)\]

Một đơn đồ thị vô hướng \(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 \(G\) bằng hai màu sao cho không có hai đỉnh kề nhau được tô cùng màu.

Định lý Hall (Hall’s Marriage Theorem) Cho \(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 \subset E\) bao phủ \(V_1\) khi và chỉ khi với mọi \(S \subset V_1, \mid S \mid \leq \mid N_G(S) \mid\).

Cho \(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 \in V\) của \(G\), tồn tại một đường đi đơn giữa \(u\) và \(v\).

Cho \(G\) là một đồ thị với ma trận kề \(A\) tương ứng với thứu tự các đỉnh \(v_1, v_2, \ldots, v_n\). Số các đường đi khác nhau độ dài \(r\) từ \(v_i\) tới \(v_j\), trong đó \(r\) là một số nguyên dương, bằng giá trị \(A_{ij}\) của phần tử (\(i, j\)) của ma trận \(A^r\).

Đườ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.

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

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

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

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

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

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

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

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

Cây

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

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

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

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

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.

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.

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

Bài tập đồ thị

Bài 7.1

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

\[\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*}\]

\[\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*}\]

• 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)\), ký hiệu \(\bar{G}\), là đồ thị có tập đỉnh \(\bar{V} = V\) và tập cạnh \(E = [V]^2 \ E\) \(= \{uv \mid u, v \in V\) \(\text{ và } uv \notin E\}\).

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

Ta có:

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

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

• Nếu \(uv \in \bar{E}(G)\) thì tức là \(uv \notin E(G)\), dẫn đến \(f(u)f(v) \notin E(H)\) hay \(f(u)f(v) \in \bar{E}(H)\).
• Nếu \(uv \notin \bar{E}(G)\) thì tức là \(uv \in E(G)\), dẫn đến \(f(u)f(v) \in E(H)\) hay \(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ừ \(K_5\).

Bài 7.21

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

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

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

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

\[\delta(G) \geq \frac{n}{2}\]

Vậy mọi đỉnh của \(G\) sẽ thỏa mãn:

\[\deg(u) \geq \frac{n}{2}, \forall u \in V\]

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

\[\deg(u) + \deg(v) \geq n\]

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 \cdot 0 + \overline{(0 + 1)}\).

\[\begin{gather*} 1 \cdot 0 = 0 \\ 0 + 1 = 1 \\ \bar{1} = 0 \\ 0 + 0 = 0 \end{gather*}\]

Bài 8.2

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

\[(1 \cdot 1) + \overline{0} = 1\]

Bài 8.3

• (a) Lập bảng giá trị của các hàm Boole sau:

\[\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*}\]

• (b) Biểu diễn mỗi hàm ở phần (a) trên một khối lập phương \(Q_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:

\[\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*}\]

\[\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*}\]

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:

\[\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*}\]

\[\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*}\]

Mạch tổ hợp

Bài 8.6

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

\[\begin{align*} & (1) \quad \bar{x} \overline{(y + \bar{z})} \\ & (2) \quad (x + y + z)(\bar{x} + \bar{y} + \bar{z}) \end{align*}\]

Mạch (1):

x --->NOT----------------|
                         AND---> out
                         |
y ---------OR--->NOT-----|
           |
           |
z --->NOT--|

Mạch (2):
 x----|
      |
 y----OR----|
            |
 z----------OR---|
                 |
!x----|          AND---> out
      |          |
!y----OR----|    |
            |    |
!z----------OR---|

Bài 8.7

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

\[2^{2^n}\]

• 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)\).

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.

Bài 8.10

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

• (a) có đúng 2 trong 3 biến \(x, y, z\) nhận giá trị 1.
• (b) có một số chẵn biến nhận giá trị 1.

\[(a) \quad F(x, y, z) = (x \cdot y \cdot \bar{z}) + (x \cdot \bar{y} \cdot z) + (\bar{x} \cdot y \cdot 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)\]

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:

\[\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*}\]

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.

\[(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}\]

\[(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}\]

Bài 8.12

Cho:

Chứng minh rằng:

\[\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*}\]

• (Bảng chân trị)

\[x \mid y = \overline{x \cdot y}\]

Bài 8.13

Chứng minh rằng:

\[\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*}\]

• (Bảng chân trị)

\[x \downarrow y = \overline{x + y}\]

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:

\[\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*}\]

• Bảng Karnaugh (K-Map) cho 3 biến:

• K-Map (1)

Vậy \(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)

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 -> \(\bar{z}\)
• 110, 100 -> –0 -> \(\bar{z}\)
• 000, 100 -> –0 -> \(\bar{z}\)
• 110, 010 -> –0 -> \(\bar{z}\)

Vậy \(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

• VNU - HUS MAT3500: Toán Rời Rạc: Tập hợp bài giảng - Hoàng Anh Đức
• VNU - HUS MAT3500: Toán Rời Rạc: Danh sách bài tập - Hoàng Anh Đức