Phép đồng phôi (lý thuyết đồ thị)

Bách khoa toàn thư mở Wikipedia

Trong lý thuyết đồ thị, tồn tại một phép đồng phôi (tiếng Anh: homeomorphism, còn gọi là phép biến đổi tôpô) giữa hai đồ thị GG′nếu tồn tại một đồ thị H sao cho cả GG′ đều là kết quả thu được sau khi thực hiện một số phép chia cạnh đối với đồ thị H. Nếu các cạnh của một đồ thị được coi là các đường nối từ một đỉnh tới một đỉnh khác (như chúng thường được vẽ trong các minh họa về đồ thị), thì trong ngữ cảnh lý thuyết đồ thị hai đồ thị được gọi là đồng phôi với nhau nếu chúng được coi là đồng phôi với nhau theo nghĩa của thuật ngữ này trong ngành tôpô học.

Phép chia cạnh trên đồ thị G đối với cạnh e {u,w} cho một đồ thị chứa một đỉnh mới v, và cạnh e được thay bởi hai cạnh mới {u,v} và {v,w}.

Ví dụ, nếu ta có đồ thị G1

*--*--*--*

G2

*--*--*--*--*

hai đồ thị này là đồng phôi, do có đồ thị sau

*---*---*
x   y

thỏa mãn: nếu chia cạnh x ta được đồ thị G1, và nếu chia cả hai cạnh xy ta được G2.

[sửa] Xem thêm

  • Minor (graph theory)
Ngôn ngữ khác