Đồ thị có hướng và biểu diễn
24 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Để kiểm tra đồ thị là strongly connected, chúng ta cần thực hiện bao nhiêu lần DFS?

  • 4 lần
  • 1 lần
  • 2 lần (correct)
  • 3 lần

    • Thuật toán nào dưới đây chỉ cần 1 lần DFS để chia đồ thị thành các tập con là một thành phần liên thông mạnh?

  • Gabow
  • Kosaraju
  • Tarjan (correct)
  • ijkstra

    • Ý nghĩa của cây khung (Spanning Tree) trong đồ thị là gì?

  • Cây chứa các cạnh của đồ thị
  • Cây chứa một số đỉnh của đồ thị
  • Cây chứa tất cả các đỉnh của đồ thị (correct)
  • Cây chứa các đỉnh của đồ thị

    • Thuật toán nào dưới đây được sử dụng để tìm cây khung có trọng số nhỏ nhất trên đồ thị?

    <p>Prim's</p> Signup and view all the answers

    Thời gian thực hiện của thuật toán Kosaraju là gì?

    <p>O(|V| + |E|)</p> Signup and view all the answers

    Bài toán chia đồ thị thành các tập con là một thành phần liên thông mạnh có tên là gì?

    <p>Strongly Connected Component</p> Signup and view all the answers

    Tại sao thuật toán Tarjan lại được ưa chuộng trong chia đồ thị thành các tập con là một thành phần liên thông mạnh?

    <p>Do nó cần 1 lần DFS</p> Signup and view all the answers

    Ý nghĩa của thuật toán duyệt đồ thị là gì?

    <p>Tất cả các đáp án trên</p> Signup and view all the answers

    Thuật toán nào được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh trên đồ thị không có trọng số âm?

    <p>Dijkstra</p> Signup and view all the answers

    Để tìm kiếm thành phần liên thông của đồ thị, người ta sử dụng thuật toán nào?

    <p>DFS hoặc BFS</p> Signup and view all the answers

    Bài toán nào liên quan đến việc tô màu các đỉnh trên đồ thị bằng 2 màu?

    <p>Bi-coloring graphs</p> Signup and view all the answers

    Thuật toán nào được sử dụng để tìm đường đi ngắn nhất trên đồ thị có trọng số âm nhưng không có chu trình âm?

    <p>Ford Bellman</p> Signup and view all the answers

    Khẳng định nào sau đây là đúng về thành phần liên thông của đồ thị?

    <p>Là tập đỉnh lớn nhất</p> Signup and view all the answers

    Thuật toán nào được sử dụng để tìm đường đi ngắn nhất trên đồ thị có chu trình âm?

    <p>Floyd Warshall</p> Signup and view all the answers

    Bài toán nào liên quan đến việc tìm kiếm đường đi ngắn nhất giữa hai đỉnh trên đồ thị?

    <p>Tìm đường đi ngắn nhất</p> Signup and view all the answers

    Thuật toán nào được sử dụng để kiểm tra đồ thị có liên thông hay không?

    <p>DFS hoặc BFS</p> Signup and view all the answers

    Nhược điểm của biểu diễn đồ thị bằng ma trận kề là gì?

    <p>Tốn bộ nhớ</p> Signup and view all the answers

    Khi nào nên dùng danh sách kề để biểu diễn đồ thị?

    <p>Trong trường hợp tổng quát</p> Signup and view all the answers

    Thuật toán nào tìm kiếm tất cả các đỉnh mà có thể tới được từ đỉnh nguồn s?

    <p>Tìm kiếm theo chiều rộng</p> Signup and view all the answers

    Ưu điểm của dùng danh sách kề là gì?

    <p>Tiết kiệm bộ nhớ</p> Signup and view all the answers

    Thư viện nào cung cấp các hàm về đồ thị?

    <p>LEDA</p> Signup and view all the answers

    Tìm kiếm theo chiều rộng được dùng để làm gì?

    <p>Tìm kiếm tất cả các đỉnh mà có thể tới được từ đỉnh nguồn</p> Signup and view all the answers

    Biểu diễn đồ thị bằng cấu trúc nào?

    <p>Danh sách kề</p> Signup and view all the answers

    Ưu điểm của dùng ma trận kề là gì?

    <p>Kiểm tra cạnh nhanh chóng</p> Signup and view all the answers

    Study Notes

    Kiểm tra đồ thị là strongly connected

    • Thực hiện DFS từ 1 đỉnh v tuỳ ý
    • Đổi hướng các đỉnh trên đồ thị cũ và thực hiện DFS lại với đỉnh v

    Thuật toán tìm thành phần liên thông mạnh

    • Kosaraju: cần 2 lần DFS trên đồ thị
    • Tarjan: 1 Lần DFS
    • Gabow
    • Thời gian ( + | |)

    Ứng dụng của các thuật toán duyệt đồ thị

    • Bài toán 8: Cây khung có trọng số nhỏ nhất trên đồ thị (minimum spanning tree - MST)
    • Cây khung: là cây chứa mà kết nối tất cả các đỉnh của đồ thị
    • Cost = 17 and Cost = 10

    Bài toán 1: Tìm đường đi ngắn nhất giữa hai đỉnh trên đồ thị

    • Trường hợp đồ thị không có trọng số âm: Thuật toán Dijkstra
    • Trường hợp đồ thị có trọng số âm: Thuật toán Ford Bellman
    • Trường hợp đồ thị có chu trình âm: Thuật toán Floyd Warshall

    Bài toán 2: Thành phần liên thông – connected components

    • Thành phần liên thông của 1 đồ thị vô hướng là tập đỉnh lớn nhất
    • Thực hiện DFS hoặc BFS để kiểm tra đồ thị liên thông
    • Tất cả các đỉnh đều được thăm  liên thông

    Bài toán 3: Bi-coloring graphs – tô màu các đỉnh trên đồ thị

    • Kiểm tra xem có thể tô màu các đỉnh trên đồ thị chỉ bằng 2 màu
    • 2 đỉnh của mỗi cạnh đều có màu khác nhau

    Biểu diễn đồ thị

    • Ma trận kề và danh sách kề
    • Kiểm tra cạnh và tìm bậc của node
    • Kích thước bộ nhớ và thêm xóa cạnh
    • Duyệt trên đồ thị

    Thư viện các hàm về đồ thị thông dụng

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Description

    Kiểm tra kiến thức về đồ thị có hướng, bao gồm các cách biểu diễn đồ thị và các vấn đề liên quan.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser