Rate this post

Xét một đồ thị G (V, E) và G * (V *, E *) được cho là đẳng cấu nếu tồn tại một đối một tương ứng tức là f: V → V * sao cho {u, v} là một cạnh của G nếu và chỉ khi {f (u), f (v)} là một cạnh của G *.

Số đỉnh của đồ thị (a) phải bằng đồ thị (b), tức là tương ứng 1-1 với một số đối với các cạnh.

Các bài viết liên quan:

Đồ thị Homeomorphic:

Hai đồ thị G và G * được cho là đồng dạng nếu chúng có thể thu được từ cùng một đồ thị hoặc đồ thị đẳng cấu bằng phương pháp này. Các đồ thị (a) và (b) không phải là đẳng cấu, nhưng chúng là đồng cấu vì chúng có thể nhận được từ đồ thị (c) bằng cách thêm các đỉnh thích hợp.

Subgraph

Subgraph của đồ thị G = (V, E) là đồ thị G ‘= (V’, E ‘) trong đó V’⊆V và E’⊆E và mỗi cạnh của G’ có cùng đỉnh cuối trong G ‘ như trong đồ thị G.

Lưu ý: Một đỉnh đơn là một Subgraph.

Ví dụ: Hãy xem xét đồ thị G được hiển thị trong hình. Hiển thị Subgraph khác nhau của đồ thị này.

Giải pháp: Sau đây là tất cả các Subgraph của đồ thị trên như được hiển thị trong hình:

Spanning Subgraph:

Đồ thị G1 được gọi là Subgraph bao trùm của G nếu G1 chứa tất cả các đỉnh của G.

Ví dụ: Hình sau là Subgraph bao trùm của biểu đồ được hiển thị trong Hình:

Leave a Reply

Call now
%d bloggers like this: