Giáo án điện tử chuyên đề Khoa học máy tính 12 chân trời Bài 3.1: Các khái niệm cơ bản của đồ thị

CHÀO MỪNG CÁC EM

ĐẾN BUỔI HỌC HÔM NAY!

Một khách du lịch xuất phát từ sân bay của thành phố, muốn ghé thăm tất cả các địa điểm nổi tiếng A, B, C, D, E, F, mỗi địa điểm đúng một lần sau đó quay trở lại sân bay. Theo em, có tồn tại một hành trình như vậy không?

Hình 1. Bản đồ đường đi giữa các địa điểm tham quan

KHỞI ĐỘNG

KHỞI ĐỘNG

Hình 1. Bản đồ đường đi giữa các địa điểm tham quan

Trả lời:

• Địa điểm B và D có số lượng đường nối lẻ.

• Địa điểm F và Sân bay chỉ có 1 đường nối.

→ Dựa trên nguyên tắc của đường đi Euler và không có thông tin thêm về hướng di chuyển hay khoảng cách, một hành trình như Hình 1 không tồn tại.

CHUYÊN ĐỀ 3: TÌM HIỂU KĨ THUẬT

DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

BÀI 3.1: CÁC KHÁI NIỆM

CƠ BẢN CỦA ĐỒ THỊ

NỘI DUNG BÀI HỌC

1

Khái niệm đồ thị

2

Một số dạng đồ thị

1. KHÁI NIỆM

ĐỒ THỊ

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

Đọc SGK tr.49-50 và tìm hiểu các khái niệm:

• Đồ thị, đồ thị rỗng, đồ thị trống.
• Cách kí hiệu các đỉnh, các cạnh của đồ thị.
• Hai đỉnh kề nhau.
• Hai cạnh kề nhau.
• Khuyên.

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

Những sơ đồ gồm những điểm biểu thị các đối tượng được xem xét (địa điểm, người, đội bóng,…) và nối một số điểm với nhau bằng đoạn đường cong (hoặc thẳng) hay mũi tên tượng trưng cho mối quan hệ nào đó giữa các đối tượng → những hình ảnh về đồ thị.

Sơ đồ truyền tải điện năng

Sơ đồ giao thông (tuyến Metro Sài Gòn)

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

Khái niệm

Đồ thị G = (V, E) là một cấu trúc gồm hai tập hợp, trong đó tập V chứa các đỉnh và tập E chứa các cạnh, mỗi cạnh kết nối hai đỉnh của đồ thị với nhau.

Nếu đồ thị G = (V, E) với V =  và E =  thì G được gọi là đồ thị rỗng.

Nếu đồ thị G = (V, E) với V   và E =  thì G được gọi là đồ thị trống.

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

Cách kí hiệu:

• Các đỉnh của đồ thị thường được kí hiệu bằng các chữ cái A, B, C,… hoặc u, v,… hoặc bằng cách đánh số 1, 2, 3,…

• Cạnh kết nối đỉnh A với đỉnh B được kí hiệu là {A, B}.

Hình 1. Bản đồ đường đi giữa các địa điểm tham quan

Đồ thị ở Hình 1 có:

• 7 đỉnh A, B, C, D, E, F, I .

• 8 cạnh là {I, A}, {I, B}, {A, C}, {C, D}, {D, B}, {D, E}, {E, F}, {B, F}.

Ví dụ

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

Hai đỉnh kề nhau

Hai đỉnh của đồ thị được gọi là kề nhau nếu chúng được kết nối bởi một cạnh.

Một đỉnh không kề với đỉnh nào gọi là đỉnh cô lập (đỉnh treo).

Hai đỉnh A và C ở Hình 1 được gọi là hai đỉnh kề nhau.

Ví dụ

Hình 1. Bản đồ đường đi giữa các địa điểm tham quan

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

Hai cạnh kề nhau

Hai cạnh của một đồ thị được gọi là kề nhau nếu chúng có chung một đỉnh.

Hai cạnh {A, C) và {C, D} ở Hình 1 có chung đỉnh C là hai cạnh kề nhau.

Ví dụ

Hình 1. Bản đồ đường đi giữa các địa điểm tham quan

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

Cạnh của đồ thị có hai đầu mút trùng nhau.

Khuyên

Khuyên trong đồ thị

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

Dãy các cạnh {A, C}, {C, D}, {D, E} ở Hình 1 là một đường đi từ đỉnh A đến đỉnh E, được kí hiệu là (A, C, D, E).

Ví dụ

Hình 1. Bản đồ đường đi giữa các địa điểm tham quan

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

Hình 2. Minh họa các khái niệm của đồ thị

Ví dụ

• Đỉnh A và B kề nhau.

• Đỉnh A và đỉnh C không kề nhau vì không có cạnh nào của đồ thị kết nối chúng.

• Cạnh {A, B} và cạnh {B, C} kề nhau do có chung đỉnh B.

Hình 2 biểu diễn một đồ thị có:

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

Hình 2. Minh họa các khái niệm của đồ thị

Ví dụ

• Tại đỉnh C có một khuyên.

• Dãy các cạnh {A, F}, {F, E}, {E, D} là một đường đi từ đỉnh A đến đỉnh D.

• Dãy các cạnh {A, F}, {F, E}, {E, B}, {B, A} không là đường đi.

Hình 2 biểu diễn một đồ thị có:

Hoạt động Làm SGK tr.50

Một mạng máy tính gồm có 7 máy tính được kết nối với một máy chủ thông qua một switch. Máy chủ được kết nối với mạng Internet thông qua modem. Ngoài ra, máy chủ còn được kết nối với 2 máy in. Em hãy:

a) Vẽ đồ thị biểu diễn mạng máy tính.

b) Cho biết đồ thị đó có bao nhiêu đỉnh, bao nhiêu cạnh?

Hoạt động Làm SGK tr.50

a) Đồ thị biểu diễn mạng máy tính.

Hoạt động Làm SGK tr.50

b)

• Nếu không tính mạng Internet và đường nối từ Modem ra mạng Internet, đồ thị có 12 đỉnh: PC1, PC2, PC3, PC4, PC5, PC6, PC7, Switch, Máy chủ, Máy in 1, Máy in 2, Modem và 11 cạnh tương ứng.

• Nếu tính mạng Internet là 1 đỉnh, đồ thị có: 13 đỉnh và 12 cạnh.

GHI NHỚ

Đồ thị G = (V, E) là một cấu trúc gồm hai tập hợp: tập hợp đỉnh V bao gồm các đỉnh và tập hợp cạnh E bao gồm các cạnh nối các đỉnh.

2. MỘT SỐ

DẠNG ĐỒ THỊ

2. Một số dạng đồ thị

Nghiên cứu thông tin trong SGK tr.50-51 và trình bày các khái niệm:

• Đơn đồ thị.
• Đồ thị có hướng.
• Đồ thị vô hướng.

2. Một số dạng đồ thị

Hình 3. Minh họa đơn đồ thị

Đơn đồ thị

Đồ thị không chứa khuyên và giữa hai đỉnh bất kì có nhiều nhất một cạnh.

2. Một số dạng đồ thị

Hình 4. Minh họa đồ thị có hướng

• Là đồ thị mà mỗi cạnh có chiều, cạnh còn được gọi là cung.
• Cạnh kết nối từ đỉnh u đến đỉnh v được kí hiệu (u, v) và được biểu diễn bằng mũi tên đi từ đỉnh u đến đỉnh v:

Đồ thị có hướng:

• u là đỉnh góc (đỉnh đầu) và v là đỉnh ngọn (đỉnh cuối).
• v là đỉnh kề của u, u không là đỉnh kề của v.
• Cạnh (u, v) và (v, u) là hai cạnh khác nhau.

2. Một số dạng đồ thị

Minh họa đồ thị vô hướng

• Là đồ thị mà tất cả các cạnh đều không có chiều.
• Cạnh {u, v} và cạnh {v, u} là giống nhau.

Đồ thị vô hướng:

Hoạt động Làm SGK tr.51

Em hãy cho biết trong các đồ thị ở Hình 5, đồ thị nào là đơn đô thị, đồ thị vô hướng, đồ thị có hướng.

Đơn đồ thị.

Đồ thị

vô hướng.

Đồ thị

có hướng.

Đồ thị

vô hướng.

Đồ thị

vô hướng.

Đồ thị

có hướng.

Đơn đồ thị.

GHI NHỚ

Có nhiều loại đồ thị để biểu diễn các đối tượng với các mục đích khác nhau như đơn đồ thị, đồ thị có hướng, đồ thị vô hướng,…

THỰC HÀNH

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