[LTDT] – Một số dạng đồ thị đặc biệt

Mục lục

Cho đồ thị G=(V,E) và H=(W,F) như trên; Chứng minh 2 đồ thị đẳng cấu?

Bài làm:

Ta có:

… xét tương tự cho f(U2) và f(U4)

…xét tương tự cho deg(U2), deg(U3), deg(U4)

=> G và H đẳng cấu

Lưu ý:

Trình bày là như vậy nhưng nếu đề nói chưng minh 2 đồ thi không đẳng cấu thì bước đầu nên đếm số đỉnh có bậc n bên này có bằng số đỉnh có bậc n bên kia không. Ngoài ra xem 2 đồ thì có số cạnh và số đỉnh bằng nhau hay không.
Việc chứng minh 2 đồ thì có đẳng cấu hay không thực sự khó, Ở trên do đề đã yêu cầu là chứng minh 2 đồ thị đẳng cấu nên đề đã xác định rõ cho ta rồi.

Dạng 2: Đồ thị hai phía (BIPARTITE GRAPHS)

Untitled

V1 V2

1 2

4 3

5 6

Dựa vào định nghĩa (bằng lời): “Có thể phân hoạch tập đỉnh thành hai tập sao cho mỗi cạnh nối hai đỉnh thuộc hai tập khác nhau” mà ta có cách chứng minh kế bên.
Giải thích: Đỉnh 1 kề với 2,3; Đỉnh 2 không kề với 3 (thỏa); Xét đỉnh kế tiếp là 4 kề với 3; Xét đỉnh 5 kề với 3,6; Đỉnh 6 không kề vởi 3 (thỏa); Hết đình xét vậy Đồ thị trên là dạng đồ thị hai phía
Các bạn có thể luyện tập thêm với các chữ A,B,C,D,E,F,G,H,K – giải ra thì cmt đáp án bên dưới để mình check kết quả hen ^^

Dạng 3: Đồ thị Euler

Chu trình Euler trong đồ thị G là chu trình đi qua mỗi cạnh của G đúng một lần
Đường đi Euler trong đồ thị G là đường đi qua mỗi cạnh của G đúng một lần
Đồ thị có chu trình Euler được gọi là đồ thị Euler
Đồ thi có đường đi Euler được gọi là đồ thị nửa Euler
Rõ ràng mọi đồ thị Euler là đồ thì nửa Euler

Định lý:

Đa đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi nó không có đỉnh bậc lẻ => là đồ thị Euler.
Đa đồ thị vô hướng liên thông có đường đi Euler khi và chỉ khi nó không có quá 2 đỉnh bậc lẻ => là đồ thị nửa Euler.

Untitled

? Chứng minh G là đồ thị Euler và chỉ ra đường đi Euler tìm được. Hãy chỉ ra 1 cạnh duy nhất nếu loại bỏ thì G là đồ thị Euler ?

Bài làm: