Chào mừng
các Thầy, cô giáo đến dự giờ

TIẾTĐỘNG
6:
KHỞI

Trước khi vào một hồi nghị, các đại biểu bắt
tay nhau (hai người bắt tay nhau nhiều nhất 1
lần). Có một đại biểu không bắt tay ai hết và
thấy rằng có 4 người bắt tay 4 lần, 5 người
bắt tay 5 lần và 6 người bắt tay 6 lần. Nếu
hội nghị có đúng 16 đại biểu thì ông ta đếm
nhầm. Vì sao có thể kết luận như vậy?

KHỞI ĐỘNG

Mạng lưới giao thông toàn
cầu

Kết nối bạn bè trên
facebook

CHUYÊN ĐỀ 2: LÀM
QUEN
VỚI
MỘT
VÀI
TIẾT 6:
KHÁI NIỆM CỦA LÝ THUYẾT ĐỒ THỊ
Bài 8: MỘT VÀI KHÁI NIỆM CƠ BẢN
(3 tiết)
1. Đồ thị
2. Bậc của đỉnh
3. Đường đi và chu trình

TIẾT 6:
Bài 8: MỘT VÀI KHÁI NIỆM CƠ BẢN

HĐ 1:
Có bốn bạn học sinh khối 11 là An, Bình, Cường và Dung,
trong đó: An là bạn của Bình và Cường, nhưng không là bạn
của Dung; Dung là bạn của Cường, nhưng không là bạn của
Bình; Bình là bạn của Cường.
a) Hãy biểu diễn mỗi bạn An, Bình, Cường, Dung bằng một
điểm trên mặt phẳng và dùng chữ cái đầu (in hoa) trong tên
của họ để đặt tên cho các điểm này.
b) Nếu hai người là bạn của nhau, hãy nối các điểm biểu diễn
tương ứng bằng một đoạn thẳng (hay đoạn đường cong).
c) Từ hình vẽ thu được ở ý b, hãy cho biết: ai có nhiều bạn
nhất và ai có it bạn nhất?

Lời giải:
a) Lần lượt biểu diễn mỗi bạn An, Bình, Cường, Dung bằng
các điểm A, B, C, D trên mặt phẳng (hình vẽ).
b) Nếu hai người là bạn của nhau, nối các điểm biểu diễn
tương ứng (hình vẽ).

c) Từ hình vẽ thu được, ta thấy Cường có nhiều bạn nhất vì từ
điểm C đều có đoạn thẳng nối tới cả 3 điểm A, B, D và Dung có ít
bạn nhất vì từ điểm D chỉ có 1 đoạn thẳng nối đến điểm C.

1. Đồ thị
a) Khái niệm đồ thị

TIẾT 6:

Một đồ thị là một tập hợp hữu hạn các điểm ( gọi là các đỉnh của
đồ thị) cùng với tập hợp các đoạn đường cong hay thẳng (gọi là
cạnh của đồ thị) có đầu mút tại các đỉnh của đồ thị
 

Chú ý. Theo định nghĩa của đồ thị, các cạnh của đồ thị thẳng
TIẾT
hay cong, dài hay ngắn, các đỉnh
ở vị trí6:
nào đều không quan
trọng, mà bản chất là đồ thị có bao nhiêu đỉnh, bao nhiêu
cạnh và đỉnh nào được nối với đỉnh nào.
Kí hiệu:
V( G ) là tập hợp các đỉnh
E( G ) là tập hợp các cạnh của đồ thị
Và viết G ( V, E )
Cạnh nối hai đỉnh A và B kí hiệu: AB hoặc BA
khi đó A và B gọi là hai đỉnh kề nhau.
Nếu hai đầu mút của cạnh trùng nhau tại đỉnh thì ta gọi cạnh ấy là một
khuyên, kí hiệu là CC.

Ví dụ 1: Kể tên
các cạnh và các
đỉnh của đồ thị
trong hình

Ví dụ 2: Viết tập
hợp các đỉnh và
tập hợp các cạnh
của đồ thị G trong
hình

LT 1: Bảng F của giải vô địch bóng đá thế giới World Cup

2018 gồm bốn đội: Đức, Hàn Quốc, Mexico và Thụy Điển.
Biểu diễn các đội này bằng các điểm phân biệt kí hiệu lần lượt
là D, H, M, T (vẽ sao cho không có ba điểm nào thẳng hàng để
dễ quan sát) và nếu hai đội nào đấu với nhau thì ta nối hai điểm
tương ứng bằng một đoạn thẳng, ta sẽ được một đồ thị.
Viết tập hợp các đỉnh và tập hợp các cạnh của đồ thị.
Lời giải:
Trong một bảng đấu, các đội sẽ thi đấu vòng tròn, có nghĩa là mỗi
một đội sẽ lần lượt thi đấu với ba đội còn lại. Do đó, từ mỗi điểm D,
H, M, T, ta vẽ các đoạn thẳng đến các điểm còn lại ta được đồ thị G
như hình vẽ dưới đây.

Lời giải:

Trong một bảng đấu, các đội sẽ thi đấu vòng tròn, có
nghĩa là mỗi một đội sẽ lần lượt thi đấu với ba đội còn lại.
Do đó, từ mỗi điểm D, H, M, T, ta vẽ các đoạn thẳng đến
các điểm còn lại ta được đồ thị G như hình vẽ dưới đây.

Khi đó ta có: V(G) = {D; H; M; T}.
E(G) = {DH; DT; DM; HT; HM; MT}.

HĐ2: Nhận biết khái niệm đơn đồ thị
Xét đồ thị cho trong Hình 2.2.
a) Đồ thị trên có khuyên không?
b) Có hai đỉnh nào của đồ thị được nối với nhau bằng
nhiều hơn một cạnh không?

Lời giải:
a) Đồ thị trên không có khuyên vì không có cạnh nào có
hai đầu mút trùng nhau tại một đỉnh.
b) Không có hai đỉnh nào của đồ thị được nối với nhau
bằng nhiều hơn một cạnh.

b) Đơn đồ thị và đa đồ thị

Một đồ thị không có khuyên, trong đó hai đỉnh được nối bằng nhiều
nhất một cạnh (không có hai cạnh nào cùng nối một cặp đỉnh) gọi là
một đơn đồ thị.
Một đồ thị không có khuyên, trong đó hai đỉnh có thể nối bằng nhiều
cạnh, gọi là một đa đồ thị. 
Chú ý:Trong cuốn sách này, khi chỉ nói từ "đồ thị" thì ta hiểu là
đơn đồ thị. Khi nào cần xét đa đồ thị thì ta sẽ nói rõ.

Ví dụ 3: Hình nào sau đây biểu diễn một đơn đồ thị,
một đa đồ thị?

LT 2: Vẽ đồ thị G với các đỉnh và các cạnh như sau:
V (G ) U , W, X , Z 

E (G )  UW, WX , WZ , XZ 

G có phải là một đơn đồ thị không?

G là một đơn đồ thị, do hai đỉnh bất kì đều nối
với nhau bởi không quá một cạnh.

HĐ3: Xét đồ thị nhận được trong Luyện tập 1. Có cặp đỉnh nào
của đồ thị này mà không có cạnh nào nối chúng không?
Lời giải:

Quan sát đồ thị có được từ Luyện tập 1, ta thấy không có bất kì cặp
đỉnh nào của đồ thị mà không có cạnh nối chúng với nhau hay mỗi
cặp đỉnh của đồ thị đều được nối với nhau bằng một cạnh.

c) Đồ thị đầy đủ
Một đồ thị là đầy đủ khi và chỉ khi mỗi cặp đỉnh của nó đều
được nối bằng một cạnh
Nhận xét. Một đồ thị đầy đủ là đồ thị mà mọi cặp đỉnh
của nó đều là kề nhau. Một đồ thị đầy đủ hoàn toàn
được xác định bởi số đỉnh của nó.
Kn
Đồ thị đầy đủ có n đỉnh thường được kí hiệu
.

LT 3: Vẽ các đồ thị đầy đủ K5 , K6

2. BẬC CỦA ĐỈNH
HĐ 4. Nhận biết bậc của đỉnh
Cho đồ thị như Hình 2.5. Tìm các đỉnh là đầu mút của:
0 cạnh; 1 cạnh; 2 cạnh; 3 cạnh.

Lời giải:
Đỉnh là đầu mút của 0 cạnh là đỉnh G.
Đỉnh là đầu mút của 1 cạnh là đỉnh F.
Các đỉnh là đầu mút của 2 cạnh là các đỉnh A, B.
Các đỉnh là đầu mút của 3 cạnh là các đỉnh C, D, E.

2. BẬC CỦA ĐỈNH

Một đỉnh của đồ thị được gọi
là đỉnh bậc n nếu nó là đầu
mút của n cạnh
Chú ý: Đỉnh bậc 0 gọi là đỉnh cô
lập. Đỉnh bậc 1 gọi là đỉnh treo.
Trong đồ thị Hình 2.5, D là đỉnh
bậc 3, F là đỉnh treo, G là đỉnh
cô lập.

Ví dụ 4. Xác định bậc của các đỉnh của đồ thị ở Hình 2.6.
Lời giải
A là đỉnh bậc 2, B là đỉnh bậc
3, C là đỉnh bậc4, D là đỉnh
bậc1, E là đỉnh bậc 0.
Ta có thể chứng minh định lí ( gọi là Định lí bắt tay) sau đây.
Trong mọi đồ thị G, tổng tất cả các bậc của đỉnh là một
số chẵn và bằng hai lần tổng tất cả các cạnh của G.
Hệ quả. Số đỉnh bậc lẻ của mọi đồ thị là một số chẵn.

Ví dụ 5. Cho đồ thị G với 14 đỉnh và 25 cạnh. Biết rằng
mỗi đỉnh của đô thị G đều có bậc 3 hoặc 5. Hỏi G có bao
nhiêu đỉnh bậc 3.
Lời giải
Gọi x là số đỉnh bậc 3 của G. Khi đó bậc 5 của G là 14x. Tổng tất cả các bậc của đỉnh là 3x+5(14-x)
Vì đồ thị có 25 cạnh nên ta có 3x + 5(14-x) = 2.25 = 50
 2x = 20  x =10
Vậy D có 10 đỉnh bậc 3.

Ví dụ 6. Hãy giải bài toán trong tính huống mở đầu.
Lời giải
Ta vẽ đồ thị với 16 đỉnh tương ứng với 16 đại biểu tham
dự hội nghị. Nếu hai đại biểu nào bắt tay nhau thì ta nối
hai đỉnh tương ứng bằng một cạnh.
Theo số liệu mà đại biểu đếm số bắt tay cung cấp, ta có
một đồ thị với 16 đỉnh, trong đó có 1 đỉnh bậc 0, 4 đỉnh
bậc 4, 5 đỉnh bậc 5, 6 đỉnh bậc 6.
Ở đây 5 đỉnh bậc 5, là một số lẻ. Điều này mâu thuẫn với
định lí bắt tay.
Vậy đại biểu đó đã đếm sai.

LT 4. Chứng minh rằng không có đơn đồ thị với 12 đỉnh
và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 4.
Lời giải:
Giả sử có đồ thị thỏa mãn yêu cầu bài toán. Gọi x
là số đỉnh bậc 3 của đồ thị.
Khi đó, ta có số đỉnh bậc 4 là: 12 – x.
Tổng số bậc của các đỉnh là: 3x + 4(12 – x).
Vì đồ thị có 28 cạnh nên theo Định lí bắt tay thì đồ thị có
tổng số bậc là 28 . 2 = 56.
Do đó, ta có phương trình 3x + 4(12 – x) = 56, tức là
8 + x = 0. Phương trình này không có nghiệm là số tự
nhiên, do đó không tồn tại đồ thị thỏa mãn điều kiện đề
bài.

3. ĐƯỜNG ĐI VÀ CHU TRÌNH
HĐ 5. Nhận biết khái niệm đường đi và chu trình
Cho đồ thị như Hình 2.7. Bằng cách đi dọc theo các cạnh,
với điều kiện không đi qua cạnh nào quá một lần (có thể có
cạnh không cần đi qua), hãy chỉ ra cách đê:
a) Đi từ đỉnh A đến đỉnh E.
b) Đi từ đỉnh A và quay lại về đỉnh A.

Lời giải:
a) Để đi từ đỉnh A đến đỉnh E ta có thể di chuyển theo con
đường từ A đến D rồi từ D đến E (hoặc cũng có thể chọn các
con đường khác, chẳng hạn đi theo đường từ A đến B rồi từ B
đến D và từ D đến E, ...)
b) Để đi từ đỉnh A và lại quay về đỉnh A ta có thể di chuyển theo
con đường từ A đến D rồi từ D đến B và từ B quay lại A (tương tự
cũng có thể chọn các con đường khác).

3. ĐƯỜNG ĐI VÀ CHU TRÌNH
a) Khái niệm đường đi và chu trình
Trong một đồ thị G, một dãy cạnh nối tiếp (hai cạnh nối tiếp là
hai cạnh có chung một đầu mút) AB, BC, CD, ..., MN, NP gọi là
một đường đi nối A vói P, kí hiệu là ABCD...MNP. Điểm A gọi là
đầu đường, điểm P gọi là cuối đường.
Một đường đi khép kín (đầu đường trùng với cuối đường ) gọi là
một chu trình.
Một đường (chu trình) qua n cạnh gọi là một đường đi (chu trình)
có độ dài n.
Một đường (chu trình) là sơ cấp nếu nó không đi qua đỉnh nào
hai lần trở lên.
Một đường (chu trình) là đơn giản nếu nó không đi qua cạnh nào
hai lần trở lên.

Ví dụ 7. Cho đồ thị đầy đủ có 4 đỉnh như Hình 2.8.
Tìm những chu trình sơ cấp xuất phát từ đỉnh A và có
độ dài 3; độ dài 4.
Lời giải:
Những chu trình sơ cấp có độ dài 3
xuất phát từ đỉnh A là:
ABCA, ABDA, ACBA, ACDA,
ADBA, ADCA
Những chu trình sơ cấp có độ dài 4
xuất phát từ đỉnh A là: ABCDA,
ABDCA, ACBDA, ACDBA,
ADBCA, ADCBA

LT 5: Cho đồ thị đầy đủ có 5 đỉnh như Hình 2.9. Tìm
những chu trình sơ cấp xuất phát từ đỉnh A và có độ dài 4;
độ dài 5.
Lời giải:
Những chu trình sơ cấp có độ dài 4 xuất
phát từ đỉnh A là:
ABCDA, ABCEA, ABDCA, ABDEA,
ABEDA, ABECA, ACBDA, ACBEA,
ACDBA, ACDEA, ACEBA, ACEDA,
ADBEA, ADBCA, ADCEA, ADCBA,
ADEBA, ADECA, AEBDA, AEBCA,
AECDA, AEDCA, AECBA, AEDBA.

LT 5: Cho đồ thị đầy đủ có 5 đỉnh như Hình 2.9. Tìm
những chu trình sơ cấp xuất phát từ đỉnh A và có độ dài 4;
độ dài 5.
Lời giải:
Những chu trình sơ cấp có độ dài 5 xuất phát
từ đỉnh A là:
ABCDEA, ABCEDA, ABECDA, ABEDCA,
ABDCEA, ABDECA, ACBEDA, ACBDEA,
ACDEBA, ACDBEA, ACEDBA, ACEBDA,
ADBECA, ADBCEA, ADCBEA, ADCEBA,
ADECBA, ADEBCA, AECDBA, AECBDA,
AEDCBA, AEDBCA, AEBCDA, AEBDCA.

b) Tính liên thông của đồ thị
HĐ 6: Trong đồ thị ở Hình 2.10. Hãy:
a) Tìm một đường đi từ đỉnh A đến
đỉnh E.
b) Có tồn tại một đường đi từ đỉnh A
đến đỉnh F hay không?

Lời giải:
a) Một đường đi từ đỉnh A đến đỉnh
E là: ABCDE. 
b) Không tồn tại đường đi nào từ đỉnh A
đến đỉnh F vì F là đỉnh cô lập.

b) Tính liên thông của đồ thị
Hai đỉnh A và B của một đồ thị gọi là liên thông nếu có một
đường đi nối A và B. Môt đồ thị G được gọi là liên thông nếu mọi
cặp đỉnh của G đều liên thông.
Một cạnh CD của đồ thị G gọi là cầu nếu khi bỏ cạnh CD thì đỉnh
C và D không còn liên thông nữa .
Mỗi đồ thị G không liên thông đều được chia thành một số đồ thị
(gọi là đồ thị con của G) liên thông, rời nhau, mỗi đồ thị con đó
gọi là một thành phần liên thông của G
Ví dụ 8. Tìm các thành phần liên thông của đồ thị trong hình 2.11

Ví dụ 8. Tìm các thành phần liên thông của đồ thị trong hình 2.11

Lời giải:
Đồ thị ở Hình 2.11 có hai thành phần liên thông: một thành phần gồm
3 đỉnh A, B, C và các cạnh AB, AC, BC; một thành phần gồm hai
đỉnh D, E và cạnh DE.

Ví dụ 9. Giả sử lớp có 40 học sinh. Biết rằng mỗi em có số điện
thoại ít nhất của 20 bạn trong lớp và nếu bạn A có số điện thoại
của bạn B thì bạn B cũng có số điện thoại của bạn A. Chứng minh
rằng bất cứ hai em nào trong lớp cũng có số điện thoại của nhau.

Lời giải:

Ta đặt tương ứng mỗi em học sinh trong lớp với
một đỉnh của đồ thị và hai đỉnh được gọi là liên
thông nếu hai em có số điệ̣n thoại của nhau.
Bài toán trở thành: Cho một đồ thị có 40 đỉnh. Biết
mỗi đỉnh bất kì đều liên thông với it nhất 20 đỉnh
khác. Chứng minh rằng đồ thị là liên thông.
Đồ thị này có 40 đỉnh, mỗi đỉnh có bậc ít nhất là 20,
do đó đồ thị là liên thông.
Vậy, bất cứ hai em học sinh nào trong lớp cũng có
số điện thoại của nhau.
Một đồ thị 2n đỉnh, mỗi đỉnh có bậc ít nhất bằng n, là đồ thị
liên thông.

LT 6. Chứng minh đồ thị ở Hình 2.12 là liên thông. Hãy chỉ ra một
đường đi nối đỉnh 1 và đỉnh 6.

Lời giải:
Đồ thị Hình 2.12 có 7 đỉnh, mỗi đỉnh có bậc là 4, do đó đồ thị
là liên thông.
Một đường đi nối đỉnh 1 và đỉnh 6: 123456.

BÀl TẬP
2.1. Vẽ hình biểu diễn của đồ thị G với tập đỉnh V(G) = {1; 2; 3; 4; 5} và tập
cạnh E(G) = {12; 14; 23; 25; 34; 35}. Đồ thị G có phải là đơn đồ thị không?
Có phải là đồ thị đầy đủ không?

Lời giải:
Đồ thị G không có khuyên, trong đó hai
đỉnh được nối bằng nhiều nhất một
cạnh nên là một đơn đồ thị. 
Đồ thị G có cặp đỉnh 1 và 5; 1 và 3; 2
và 4; 4 và 5 không được nối bằng 1
cạnh nên không là đồ thị đầy đủ. 

BÀl TẬP
2.2. Hãy vẽ một đồ thị có 4 đỉnh và:
a) có đúng hai đỉnh cùng bậc và bậc là 1 ;
b) có đúng hai đỉnh cùng bậc và bậc là 2.

Lời giải:
a) Đồ thị trên có hai đỉnh A và
D cùng có bậc là 1.
b) Đồ thị trên có hai đỉnh B và
C cùng có bậc là 2

BÀl TẬP
2.3. Một đồ thị con của đồ thị G là một đồ thị mà mọi đỉnh của nó
đều là đỉnh của G và mọi cạnh của nó cũng là cạnh của G.
Những đồ thị nào trong các hình a), b), c) dưới đây là đồ thị con của
đồ thị G ?

Lời giải:
Cả ba đồ thị a), b), c) không là đồ thị con của
đồ thị G.

BÀl TẬP
2.4. Chứng minh rằng một đồ thị đầy đủ có đỉnh thì có cạnh.
Lời giải:
Gọi các đỉnh của đồ thị lần lượt là , ,...,  
Đỉnh nối với đỉnh còn lại nên từ đỉnh  đồ thị có cạnh. Tương tự, từ
đỉnh  đồ thị có cạnh.
...
Từ đỉnh đồ thị có cạnh (vì các đỉnh , ,... đều nối với  rồi). Do đó, tổng
tất cả các cạnh của đồ thị là:
n  1  n  2   n  3  ...  n  n  n 2  1  2  3  ...  n 

n n  1
2 
Dễ dàng chứng minh được đẳng thức: 1  2  3  ...  n 
2

n n  1
n n  1

Từ (1)(2) suy ra: n 
2
2
pcm)
2

(đc

BÀl TẬP

2.5. Chứng minh rằng không tồn tại đồ thị với
các đỉnh 2, 3, 3, 4, 4 và 5.
Lời giải:
Ta thấy đồ thị đưa ra ở đề bài có 3 đỉnh bậc lẻ (3, 3
và 5), nên theo Hệ quả của Định lí bắt tay, không
có đồ thị nào thỏa mãn điều kiện đưa ra.

BÀl TẬP
2.6. Cho đồ thị G như Hinh 2.14.
a) Tìm một đường đi từ đỉnh A đến đỉnh B.
b) G có liên thông không?
c) Trong G có chu trình sơ cấp nào không?
Lời giải:
a) Một đường đi từ đỉnh A đến đỉnh
B là: ADGB.
b) Ta thấy hai đỉnh bất kì của đồ thị
đều liên thông (tức là đều có đường
đi nối chúng), nên G liên thông.
c) Chu trình sơ cấp trong G là:
AEHCFBGDA.