Chào mừng các em học sinh đến với bài học số 1 của chuyên đề Lí thuyết đồ thị trong chương trình Toán 11 - Cánh Diều Chuyên đề II. Bài học này sẽ giới thiệu những khái niệm cơ bản về đồ thị, các yếu tố cấu thành và đặc biệt là hai khái niệm quan trọng: đường đi Euler và đường đi Hamilton.
Chúng ta sẽ cùng nhau khám phá cách xác định, phân loại đồ thị, cũng như tìm hiểu điều kiện để một đồ thị có đường đi Euler hoặc đường đi Hamilton. Đây là nền tảng quan trọng để giải quyết các bài toán thực tế liên quan đến mạng lưới, giao thông, và nhiều lĩnh vực khác.
1. Giới thiệu về Lí thuyết đồ thị
Lí thuyết đồ thị là một nhánh của toán học rời rạc, nghiên cứu về các đồ thị. Đồ thị là một cấu trúc toán học được sử dụng để mô hình hóa các mối quan hệ giữa các đối tượng. Nó bao gồm các đỉnh (vertices) và các cạnh (edges) nối giữa các đỉnh.
Định nghĩa: Đồ thị G = (V, E) là một cặp (V, E), trong đó V là tập hợp các đỉnh và E là tập hợp các cạnh.
Ví dụ: Một bản đồ giao thông có thể được mô hình hóa bằng một đồ thị, trong đó các thành phố là các đỉnh và các con đường là các cạnh.
2. Các loại đồ thị
3. Bậc của đỉnh
Bậc của một đỉnh là số lượng cạnh nối với đỉnh đó. Trong đồ thị vô hướng, bậc của đỉnh A được ký hiệu là deg(A). Trong đồ thị có hướng, có bậc vào (in-degree) và bậc ra (out-degree). Bậc vào là số lượng cạnh hướng đến đỉnh đó, bậc ra là số lượng cạnh hướng ra khỏi đỉnh đó.
4. Đường đi Euler
Định nghĩa: Đường đi Euler là một đường đi trong đồ thị đi qua tất cả các cạnh đúng một lần.
Định lý: Một đồ thị vô hướng liên thông có đường đi Euler khi và chỉ khi số đỉnh có bậc lẻ là 0 hoặc 2. Nếu số đỉnh có bậc lẻ là 0, đường đi Euler là một chu trình Euler (bắt đầu và kết thúc tại cùng một đỉnh). Nếu số đỉnh có bậc lẻ là 2, đường đi Euler bắt đầu tại một trong hai đỉnh có bậc lẻ và kết thúc tại đỉnh còn lại.
Ví dụ: Xét đồ thị có các đỉnh A, B, C, D và các cạnh AB, BC, CD, DA. Đây là một chu trình Euler vì tất cả các đỉnh đều có bậc chẵn.
5. Đường đi Hamilton
Định nghĩa: Đường đi Hamilton là một đường đi trong đồ thị đi qua tất cả các đỉnh đúng một lần.
Không có định lý tổng quát nào để xác định một đồ thị có đường đi Hamilton hay không. Việc tìm đường đi Hamilton là một bài toán NP-complete, tức là không có thuật toán hiệu quả nào để giải quyết bài toán này trong mọi trường hợp.
Ví dụ: Xét đồ thị có các đỉnh A, B, C, D và các cạnh AB, BC, CD, DA. Đường đi A-B-C-D là một đường đi Hamilton.
6. Bài tập ví dụ
Bài 1: Cho đồ thị vô hướng có 5 đỉnh A, B, C, D, E và các cạnh AB, BC, CD, DE, EA. Đồ thị này có đường đi Euler không? Tại sao?
Giải: Các đỉnh A, B, C, D, E đều có bậc 2. Do đó, đồ thị này có đường đi Euler và là một chu trình Euler.
Bài 2: Cho đồ thị vô hướng có 4 đỉnh A, B, C, D và các cạnh AB, BC, CA, AD. Đồ thị này có đường đi Hamilton không?
Giải: Có, đường đi A-B-C-D là một đường đi Hamilton.
Kết luận: Bài học hôm nay đã giới thiệu những khái niệm cơ bản về lí thuyết đồ thị, bao gồm các loại đồ thị, bậc của đỉnh, đường đi Euler và đường đi Hamilton. Việc nắm vững những kiến thức này sẽ giúp các em giải quyết các bài toán liên quan đến đồ thị một cách hiệu quả.
