Giáo án điện tử chuyên đề Toán 11 kết nối Bài 8: Một vài khái niệm cơ bản

CHÀO MỪNG 

TẤT CẢ CÁC EM

ĐẾN VỚI TIẾT HỌC! 

KHỞI ĐỘNG

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?

CHUYÊN ĐỀ 2: LÀM QUEN VỚI MỘT VÀI KHÁI NIỆM CỦA LÍ THUYẾT ĐỒ THỊ

BÀI 8: MỘT VÀI KHÁI NIỆM CƠ BẢN

NỘI DUNG BÀI HỌC 

1.

ĐỒ THỊ

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

• 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à dung 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 ở HĐ1b, hãy cho biết: ai có nhiều bạn nhất và ai có ít bạn nhất?

Giải:

c) Bạn Cường có nhiều bạn nhất. Bạn Dung có ít bạn nhất.

Tổng quát

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 hay cong, dài hay ngắn, các đỉnh ở vị trí 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ị G, và viết G = (V, E).

Cạnh nối hai đỉnh AB kí hiệu là AB hoặc BA. Khi đó, A, B gọi là hai đỉnh kề nhau.

Nếu hai đầu mút của cạnh trùng nhau tại đỉnh C thì ta gọi cạnh ấy là một khuyên, kí hiệu CC.

Ví dụ: Hình 2.1

Đồ thị có 4 đỉnh A, B, C, D; có 5 cạnh: AB, AC, AD, BC và CC.

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

Giải:

Tập hợp các đỉnh của đồ thị là

Tập hợp các cạnh của đồ thị là

Luyện tập 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à Thuy Đ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ì nối hai điểm tương ứng bằng một đoạn thẳng, ta sẽ được một đồ thị G. Viết tập hợp các đỉnh và tập hợp các cạnh của đồ thị G.

Giải:

Tập hợp các đỉnh của đồ thị G là: 

V(G) = {D, H, M, T}

Tập hợp các cạnh của đồ thị G là:

E(G) = {DH, DM, DT, HT, HM, MT}.

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

• HĐ2. 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?

Giải:

a) Đồ thị trên không có khuyên.

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.

KẾT LUẬN

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

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

Giải:

Hình a) không có khuyên và có hai cạnh nối hai đỉnh Z và W, nên là một đa đồ thị.

Hình b) có khuyên nên không phải là đơn đồ thị, cũng không phải là đa đồ thị.

Hình c) không có khuyên và hai đỉnh chỉ được nối bằng nhiều nhất một cạnh nên là một đơn đồ thị.

Luyện tập 2

Vẽ đồ thị với các đỉnh và các cạnh như sau:

và

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

Giải:

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

c) Đồ thị đầy đủ

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

Không có cặp đỉnh nào của đồ thị này mà không có cạnh nào nối chung.

Kết luận

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ó. Đồ thị đầy đủ có đỉnh thường được kí hiệu là .

Ví dụ 3:

Vẽ các đồ thị đầy đủ và .

Giải:

Ta có các đồ thị và như Hình 2.4.

Luyện tập 3

Vẽ các đồ thị đầy đủ có 5 đỉnh, có 6 đỉnh.

Giải:

Đồ thị đầy đủ có 5 đỉnh:

Đồ thị đầy đủ có 6 cạnh:

2.

BẬC CỦA ĐỈNH

--------------- Còn tiếp ---------------