Sau đây TTnguyen xin được gủi tới bài viết về lý thuyết và một số kiến thức cơ bản cùng các dạng bài tập chu trình euler trong môn toán rời rạc. Đây là các bài tập cơ bản thường hay gặp nhất trong quá trình học.
Xem thêm:
- bài tập toán rời rạc chương 2 có lời giải
- logic mệnh đề – Bài tập toán rời rạc chương 1 có lời giải
I. Đường đi và chu trình Euler
- Chu trình đơn trong đồ thị G đi qua mỗi cạnh của đồ thị đúng một lần được gọi là chu trình Euler.
- Đường đi đơn trong G đi qua mỗi cạnh của nó đúng một lần được gọi là đường đi Euler.
- Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler.
- Đồ thị có đường đi Euler được gọi là nửa Euler.
Ví dụ: Xét các đồ thị vô hướng sau: Xét các đồ thị G1, G2, G3
Đồ thị G1 là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a.
Đồ thị G3 không có chu trình Euler nhưng chứa đường đi Euler a, c, d, e, b, d, a, b vì thế G3 là nửa Euler.
G2 không có chu trình Euler cũng như đường đi Euler.
II. Điều kiện để có chu trình Euler
Đồ thị vô hướng liên thông G=(V, E) là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn.
Đồ thị vô hướng liên thông G=(V, E) là đồ thị nửa Euler khi và chỉ khi nó không có quá hai đỉnh bậc lẻ.
III. Bài tập tìm chu trình Euler
Bài 1: Xét các đồ thị có hướng H1, H2, H3
Đồ thị H2 là đồ thị Euler vì nó chứa chu trình Euler a, b, c, d, e, a vì vậy nó là đồ thị Euler.
Đồ thị H3 không có chu trình Euler nhưng có đường đi Euler a, b, c, a, d, c nên nó là đồ thị nửa Euler.
Đồ thị H1 không chứa chu trình Euler cũng như chu trình Euler
IV. Bài tập đồ thị Euler
Đồ thị đủ n đỉnh
Đồ thị đủ n đỉnh kí hiệu là Kn là đồ thị đơn vô hướng ,mà giữa 2 đỉnh bất kì của nó luôn có cạnh nối
Có tất cả cách cạnh là n(n-1)/2. Bậc của các đỉnh bằng nhau và bằng n-1
Cây bao trùm(cây khung)
Cây bao trùm là đồ thị con, không có chu trình chứa tất cả các đỉnh của đồ thị đó
Bài 1: Cho G là đồ thị vô hướng, đủ và có 9 đỉnh
a) Có bao nhiêu đồ thị con và bao nhiêu đồ thị bộ phận?
b) Có bao nhiêu cây bao trùm có một đỉnh bậc 6 và một đỉnh bậc 3?
c) Có bao nhiêu đồ thị con là đồ thị Euler, không phải đồ thị Euler?
d) Có bao nhiêu cây bao trùm có một đỉnh bậc 6?
e) Có bao nhiêu số đồ thị con có đỉnh là số lẻ?
f)Có bao nhiêu đồ thị con là đồ thị chính quy bậc 5?
g)Có bao nhiêu cây có độ dài lớn hơn 6?
Lời giải
a) Có bao nhiêu đồ thị con và bao nhiêu đồ thị bộ phận?
– Đồ thị con: là bỏ đi một số đỉnh và các cạch liên quan liên quan đến đỉnh đó
Bớt đi 1 đỉnh: có \( \ C_{9}^1 \) cách bớt tương ứng với 9 đồ thị con
Bớt đi 2 đỉnh: có \( \ C_{9}^2 \) cách bớt
Bớt đi 3 đỉnh: có \( \ C_{9}^3 \) các bớt
Bớt đi 4 đỉnh: có \( \ C_{9}^4 \) cách bớt
Bớt đi 5 đỉnh: có \( \ C_{9}^5 \) cách bớt
Bớt đi 6 đỉnh: có \( \ C_{9}^6 \) cách bớt
Bớt đi 7 đỉnh: có \( \ C_{9}^7 \) cách bớt
Bớt đi 8 đỉnh: có \( \ C_{9}^8 \) cách bớt
=> Số đồ thị con: \(\sum_{i=1}^8 \ C_{9}^i = 510 \) (đồ thị)
– Đồ thị bộ phận: bớt 1 một số cung và giữ nguyên số đỉnh
Số cạch là: 9.8/2=36 (cạnh)
Bớt đi 1 cạnh có \( \ C_{36}^1 \) cách bớt
…
Bớt đi 36 cạnh có cách bớt
=> Số đồ thị bộ phận là: \( \sum_{i=1}^36 \ C_{16}^i \) (đồ thị)
b) Có bao nhiêu cây bao trùm có một đỉnh bậc 6 và một đỉnh bậc 3?
Chọn 1 đỉnh trong 9 đỉnh để làm 1 đỉnh bậc 6 có \( \ C_{9}^1 =9 \) cách.
Còn lại 8 đỉnh, ta chọn 6 đỉnh để nối với đỉnh bậc 6 có \( \ C_{8}^6 = 28 \) cách.
Còn lại 2 đỉnh, thì 2 đỉnh đó phải gắn cùng với 1 đỉnh => Có \( \ C_{6}^1 = 6 \) cách.
Vậy số cây thoả mãn là: 9.28.6 =1512 (cây)
c) Có bao nhiêu đồ thị con là đồ thị Euler, không phải đồ thị Euler?
Số đồ thị con Euler là: \( \ C_{9}^3+C_{9}^5+C_{9}^7=246 \) (đồ thị)
Số đồ thị con không phải Euler là: 510-246= 264 (đồ thị)
d) Có bao nhiêu cây bao trùm có một đỉnh bậc 6
Chọn 1 đỉnh trong 9 đỉnh để làm 1 đỉnh bậc 6 có \( \ C_{9}^1 \)= 6=9 cách
Còn lại 8 đỉnh, ta chọn 6 đỉnh để nối với đỉnh bậc 6 có \( C_{6}^6 \)= 6=28 cách
Còn lại 2 đỉnh, thì 2 đỉnh:
- gắn cùng với đỉnh => Có \( C_{6}^1 \)=6 cách
- gắn với 2 đỉnh khác nhau trong 6 đỉnh: \( 2!.C_{6}^2 \)=30 cách
- gắn với 1 đỉnh và đỉnh còn lại gắn với đỉnh đó: 6.2=12
Vậy số cây thoả mãn là: 9.28.(6+12+30)= 12096 cây
e) Có bao nhiêu số đồ thị con có đỉnh là số lẻ
Đồ thị con có đỉnh là số lẻ là: \( C_{9}^1+C_{9}^3+C_{9}^5+C_{9}^7 \)
f) Có bao nhiêu đồ thị con là đồ thị chính quy bậc 5?
-Đồ thị chính quy bậc 5: đồ thị bậc các đỉnh bằng nhau và bằng 5, nên đồ thị phải có 6 đỉnh: \( C_{9}^5 \)
g) Có bao nhiêu cây có độ dài lớn hơn 6?
Cây có độ dài lớn hơn 6 thì số đỉnh phải là: 8,9
=> Số cây thoả mãn là: \(T_8+T_9=8^6+9^7\)
Bài 2: Một đơn đồ thị liên thông có 10 mặt, tất cả các đỉnh đều có bậc bằng 4, tìm số đỉnh của đồ thị.
Lời giải
Gọi f là số miền của mặt phẳng bị chia bởi biểu diễn phẳng của đồ thị, e là số cạnh và v là số đỉnh của đồ thị
Ta có tổng bậc của đồ thị bằng 2 lần số cạnh, tức là : 2e = 4v => e=2v
Mặt khác, ta có : f = e – v + 2 => 10 = 2v – v + 2 => v=8
Vậy đồ thị có 8 đỉnh và 16 cạnh.
Bài 3: Một đơn đồ thị liên thông có 10 mặt, tất cả các đỉnh đều có bậc bằng 4, tìm số đỉnh của đồ thị.
Lời giải
Gọi f là số miền của mặt phẳng bị chia bởi biểu diễn phẳng của đồ thị, e là số cạnh và v là số đỉnh của đồ thị
Ta có tổng bậc của đồ thị bằng 2 lần số cạnh, tức là : 2e = 4v => e=2v
Mặt khác, ta có : f = e – v + 2 => 10 = 2v – v + 2 => v=8
Vậy đồ thị có 8 đỉnh và 16 cạnh.
Hy vọng qua bài viết vừa rồi các bạn đã nắm vững kiến thức về đồ thị euler, đồ thị đầy đủ, đồ thị vô hướng và chu trình Euler. Nếu có bất kì thắc mắc nào thì đừng ngần ngại liên hệ với mình nhé. Chúc các bạn học tập môn toán rời rạc này thật tốt!
