Các bài toán đồ thị

Tìm đồ thị con Một bài toán thường gặp, được gọi là bài toán đồ thị con đẳng cấu (subgraph isomorphism problem), là tìm các đồ thị con trong một đồ thị cho trước. Nhiều tính chất của đồ thị có tính di truyền, nghĩa là nếu một đồ thị con nào đó có một tính chất thì toàn bộ đồ thị cũng có tính chất đó. Chẳng hạn như một đồ thị là không phẳng nếu như nó chứa một đồ thị hai phía đầy đủ (complete bipartite graph ) K3,3 (Xem Bài toán ba căn hộ và ba...