Chào mừng các em học sinh đến với bài học số 8 trong chuyên đề 2 của chương trình Toán 11 Kết nối tri thức. Bài học này sẽ giới thiệu những khái niệm cơ bản nhất về lí thuyết đồ thị, nền tảng quan trọng cho các kiến thức nâng cao hơn.
Chúng ta sẽ cùng nhau tìm hiểu về định nghĩa đồ thị, các khái niệm liên quan như đỉnh, cạnh, bậc của đỉnh, cũng như các loại đường đi và đường dẫn trong đồ thị.
Lí thuyết đồ thị là một lĩnh vực quan trọng trong 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à các bài toán tối ưu hóa.
Một đồ thị (graph) G là một cặp (V, E), trong đó:
Cạnh có thể là cạnh có hướng (directed edge) hoặc cạnh vô hướng (undirected edge). Đồ thị có cạnh có hướng được gọi là đồ thị có hướng (directed graph), còn đồ thị có cạnh vô hướng được gọi là đồ thị vô hướng (undirected graph).
Bậc của một đỉnh (degree of a vertex) trong đồ thị vô hướng là số lượng cạnh nối với đỉnh đó. Kí hiệu bậc của đỉnh v là deg(v).
Trong đồ thị có hướng, ta phân biệt:
Một đường đi (path) trong đồ thị là một dãy các đỉnh liên tiếp nhau bởi các cạnh. Một đường dẫn (trail) là một đường đi mà các cạnh không lặp lại.
Một chu trình (cycle) là một đường đi bắt đầu và kết thúc tại cùng một đỉnh.
Xét đồ thị vô hướng G với tập đỉnh V = {A, B, C, D} và tập cạnh E = {{A, B}, {B, C}, {C, D}, {D, A}, {A, C}}.
Trong đồ thị này:
Một đường đi từ A đến C có thể là A -> B -> C.
Một chu trình có thể là A -> B -> C -> D -> A.
Bài học hôm nay đã giới thiệu những khái niệm cơ bản nhất về lí thuyết đồ thị. Việc nắm vững những khái niệm này là rất quan trọng để hiểu và giải quyết các bài toán phức tạp hơn trong lĩnh vực này. Hãy luyện tập thêm các bài tập để củng cố kiến thức đã học.
| Khái niệm | Định nghĩa |
|---|---|
| Đồ thị | Cặp (V, E) với V là tập đỉnh và E là tập cạnh. |
| Đỉnh | Một phần tử trong tập V. |
| Cạnh | Nối hai đỉnh. |
| Bậc của đỉnh | Số lượng cạnh nối với đỉnh đó. |
