Bài 8. Một vài khái niệm cơ bản

Bài 8. Một vài khái niệm cơ bản - Chuyên đề học tập Toán 11 - Kết nối tri thức Chuyên đề 2: Làm quen với một vài khái niệm của lí thuyết đồ thị

Lí thuyết đồ thị là một nhánh quan trọng của toán học ứng dụng, có nhiều ứng dụng thực tế trong các lĩnh vực như khoa học máy tính, mạng lưới giao thông, và thậm chí cả sinh học. Bài 8 này sẽ giới thiệu những khái niệm cơ bản nhất để các em bắt đầu làm quen với lĩnh vực thú vị này.

1. Đồ thị là gì?

Một đồ thị (graph) G = (V, E) bao gồm một tập hợp hữu hạn các đỉnh (vertices) V và một tập hợp các cạnh (edges) E, mỗi cạnh nối hai đỉnh trong V. Đỉnh có thể đại diện cho các đối tượng, và cạnh có thể đại diện cho mối quan hệ giữa các đối tượng đó.

2. Các loại đồ thị

• Đồ thị vô hướng (Undirected graph): Các cạnh không có hướng, tức là nếu có cạnh nối đỉnh A và B, thì ta có thể đi từ A đến B và ngược lại.
• Đồ thị có hướng (Directed graph): Các cạnh có hướng, tức là nếu có cạnh nối đỉnh A và B, thì ta chỉ có thể đi từ A đến B, không thể đi ngược lại.
• Đồ thị đơn (Simple graph): Không có cạnh lặp (hai cạnh nối cùng hai đỉnh) và không có vòng lặp (cạnh nối một đỉnh với chính nó).
• Đồ thị đa (Multigraph): Cho phép có cạnh lặp.
• Đồ thị có trọng số (Weighted graph): Mỗi cạnh được gán một trọng số, thường là một số thực, biểu thị chi phí hoặc khoảng cách giữa hai đỉnh.

3. Các khái niệm liên quan đến đỉnh và cạnh

• Bậc của một đỉnh (Degree of a vertex): Số lượng cạnh kề với đỉnh đó. Trong đồ thị vô hướng, bậc của một đỉnh là số cạnh nối với đỉnh đó. Trong đồ thị có hướng, bậc vào (in-degree) là số cạnh đến đỉnh đó, và bậc ra (out-degree) là số cạnh đi từ đỉnh đó.
• Hai đỉnh kề nhau (Adjacent vertices): Hai đỉnh được nối với nhau bởi một cạnh.
• Đường đi (Path): Một dãy các đỉnh liên tiếp được nối với nhau bởi các cạnh.
• Chu trình (Cycle): Một đường đi bắt đầu và kết thúc tại cùng một đỉnh.
• Liên thông (Connected): Một đồ thị được gọi là liên thông nếu có một đường đi giữa bất kỳ hai đỉnh nào trong đồ thị.

4. Ma trận kề (Adjacency Matrix)

Ma trận kề là một cách biểu diễn đồ thị bằng ma trận. Nếu đồ thị có n đỉnh, ma trận kề sẽ là một ma trận vuông n x n. Phần tử a_ij của ma trận kề bằng 1 nếu có cạnh nối đỉnh i và đỉnh j, và bằng 0 nếu không có.

Ví dụ, xét đồ thị vô hướng có 4 đỉnh A, B, C, D và các cạnh AB, BC, CD, DA. Ma trận kề của đồ thị này sẽ là:

5. Bài tập vận dụng

1. Vẽ một đồ thị vô hướng có 5 đỉnh và 6 cạnh.
2. Xác định bậc của mỗi đỉnh trong đồ thị vừa vẽ.
3. Viết ma trận kề của đồ thị đó.

Hi vọng bài học này đã giúp các em có cái nhìn tổng quan về những khái niệm cơ bản của lí thuyết đồ thị. Hãy luyện tập thêm nhiều bài tập để nắm vững kiến thức nhé!