7 bài tập đồ thị Euler – Lý thuyết đồ thị toán rời rạc & lời giải

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 đồ thị 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.

I.Một số lý thuyết đồ thị hữu hạn

1.Định nghĩa đồ thị Euler

Đồ thị Euler là đồ thị có chu trình Euler (đồ thị khép kín đi qua các cạnh, mỗi cạnh 1 lần). và gọi là nửa đồ thị Euler nếu có đường đi Euler
Nhận biết: Đồ thị Euler có các đỉnh là bậc chẵn

2. Đồ 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

3.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ị đó

II.Bài tập đồ thị Euler

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?

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?

Giải
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?

Giải
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

Giải
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\)

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!