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

KHỞI ĐỘNG

TIẾT 6:

KHỞI ĐỘNG

TIẾT 6:

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:
Tiết 15: Bài 8: MỘT VÀI KHÁI NIỆM CƠ BẢN
(Tiết 1)

Bài toán
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?

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

Ví dụ 3: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ị.

Hoạt động
theo cặp trong
2 phút

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ị?

Ví dụ 4: 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?

Hoạt động
theo cặp trong
1 phút

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
.

Ví dụ 4: Vẽ các đồ thị đầy đủK5 , K6

HƯỚNG DẪN HỌC Ở NHÀ
1. Làm lại các bài tập đã chữa và hoàn thiện các bài tập
sgk/58,59
2. Ôn tập kiến thức chương VII