Đồ thị Euler

Reorder

Sắp xếp các đồ thị sau theo thứ tự thành phần liên thông tăng dần

1

2

3

4

5

• 1
• 2
• 3
• 4
• 5

​ĐỒ THỊ EULER

Multiple Select

Những hình vẽ nào sau đây có thể vẽ bằng một nét liền, không có đường nào bị lặp lại?

Đường đi Euler của đồ thị là đường đi đơn giản đi qua tất cả các cạnh của đồ thị.

Chu trình Euler của đồ thị là chu trình đơn giản đi qua tất cả các cạnh của đồ thị.

Đồ thị Euler là đồ thị có chứa chu trình Euler.

​Liệt kê bậc các đỉnh của các đồ thị. Nhận xét.

​Định lý: Cho đồ thị G liên thông. Khi đó, G là đồ thị Euler khi và chỉ khi G có tất cả các đỉnh đều có bậc chẵn.

​Gợi ý: (=>) Lấy đỉnh v tùy ý của đồ thị. Giả sử v xuất hiện k lần trên đường đi, hãy tính số cạnh nhận v làm đầu mút trên đường đi.

​Hệ quả: Cho đồ thị liên thông G. Khi đó, G có đường đi Euler nhưng không phải chu trình Euler khi và chỉ khi G có đúng hai đỉnh bậc lẻ.

Multiple Choice

Đồ thị sau có là đồ thị Euler không?

• Có

• Không

Multiple Select

Đồ thị nào là đồ thị Euler?

Multiple Choice

Chọn khẳng định đúng

• Đồ thị Euler có tất cả các đỉnh đều có bậc chẵn

• Đồ thị có đúng hai đỉnh bậc lẻ không có chu trình Euler

• Đồ thị có bốn đỉnh bậc lẻ không có đường đi Euler

• Cả ba khẳng định đều đúng

Multiple Choice

Đồ thị liên thông G có đường đi Euler khi và chỉ khi G có tối đa hai đỉnh bậc lẻ.

• Đúng

• Sai

• Hông biết

Drag and Drop

Đồ thị K_n có đường đi Euler khi và chỉ khi n=​​

Placeholder

hoặc ​

Placeholder

Drag these tiles and drop them in the correct blank above

2

n là số lẻ

n là số chẵn

1

0

n chia hết cho 3

n là số chính phương

3

4

Multiple Select

Cho đồ thị G có bậc các đỉnh lần lượt như các đáp án. Chọn tất cả các bộ số sao cho G chắc chắn không có chu trình Euler.

• 4,4,2,2,2

• 3,3,3,3

• 5,3,2,2,2,2

• 4,4,4,4,4,0

Hệ quả: Đồ thị G là đồ thị Euler khi và chỉ khi G có tất cả các đỉnh đều có bậc chẵn và có tối đa một thành phần liên thông có cạnh.

Multiple Select

Trong các hình vẽ sau, những hình nào có thể vẽ bằng một nét bút?

Multiple Choice

Đồ thị sau cần thêm ít nhất bao nhiêu cạnh để trở thành đồ thị Euler?

• 1

• 2

• 3

• 4

Poll

Mức độ hiểu bài hôm nay của em?

• 97%

• 98%

• 99%

• 100%

• 96%