tailieunhanh - Bài giảng Lý thuyết đồ thị - Phần 1

Đồ thị là một cấu trúc rời rạc gồm các định và các cạnh nối các đỉnh đó | Chương II. Lý thuyết đồ thị I. Các khái niệm cơ bản II. Biểu diễn đồ thị III. Tính liên thông IV. Chu trình Euler V. Bài toán tìm đường đi ngắn nhất VI. Đồ thị phẳng màu đồ thị I. Các khái niệm cơ bản 1. ĐỊNH NGHĨA ĐỒ THỊ (GRAPH) Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức: G = (V, E) V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh thuộc V. Ví dụ: Đường phố Mạng máy tính 2. Phân loại đồ thị G được gọi là đơn đồ thị nếu giữa hai đỉnh phân biệt u, v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v. G được gọi là đa đồ thị nếu giữa hai đỉnh phân biệt u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v G được gọi là giả đồ thị nếu G là đa đồ thị và có thể có cạnh nối từ một đỉnh đến chính nó. Cạnh đó được gọi là khuyên G được gọi là đồ thị vô hướng nếu các cạnh trong E không có sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là đỉnh cuối. G được gọi là đồ | Chương II. Lý thuyết đồ thị I. Các khái niệm cơ bản II. Biểu diễn đồ thị III. Tính liên thông IV. Chu trình Euler V. Bài toán tìm đường đi ngắn nhất VI. Đồ thị phẳng màu đồ thị I. Các khái niệm cơ bản 1. ĐỊNH NGHĨA ĐỒ THỊ (GRAPH) Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức: G = (V, E) V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh thuộc V. Ví dụ: Đường phố Mạng máy tính 2. Phân loại đồ thị G được gọi là đơn đồ thị nếu giữa hai đỉnh phân biệt u, v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v. G được gọi là đa đồ thị nếu giữa hai đỉnh phân biệt u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v G được gọi là giả đồ thị nếu G là đa đồ thị và có thể có cạnh nối từ một đỉnh đến chính nó. Cạnh đó được gọi là khuyên G được gọi là đồ thị vô hướng nếu các cạnh trong E không có sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là đỉnh cuối. G được gọi là đồ thị có hướng nếu các cạnh trong E có sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là đỉnh cuối. Ví dụ Đơn đồ thị vô hướng Đơn đồ thị có hướng Đa đồ thị vô hướng Đa đồ thị có hướng 3. Cạnh liên thuộc, đỉnh kề, bậc Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e E, nếu e = (u, v) thì ta nói hai đỉnh u và v là kề nhau (adjacent) và cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v. Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v, ký hiệu deg(v) là số cạnh liên thuộc với v. Định lý: Giả sử G = (V, E) là đồ thị vô hướng với m cạnh, khi đó tổng tất cả các bậc đỉnh trong V sẽ bằng 2m: Chứng minh: Khi lấy tổng tất cả các bậc đỉnh tức là mỗi cạnh e = (u, v) bất kỳ sẽ được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra kết quả. Hệ quả: Trong đồ thị vô hướng, số đỉnh bậc lẻ là số chẵn Đối với đồ thị có hướng G = (V, E). Xét một cung e E, nếu e = (u, v) thì đỉnh u khi đó được gọi là đỉnh đầu,đỉnh v được gọi là đỉnh cuối của cung e. Với mỗi đỉnh v trong đồ