Bài giảng Toán rời rạc 2 - Đồ thị Euler, đồ thị Hamilton cung cấp cho người học các khái niệm, chứng minh đồ thị là Euler, thuật toán tìm chu trình Euler, kiểm nghiệm thuật toán, chứng minh đồ thị là nửa Euler, . Mời các bạn cùng tham khảo. | Bài giảng Toán rời rạc 2 - Đồ thị Euler đồ thị Hamilton ĐỒ THỊ EULER ĐỒ THỊ HAMILTON Toán rời rạc 2 Nội dung Đồ thị Euler Đồ thị Hamilton 2 Đồ thị Euler Khái niệm đồ thị Euler 1 2 Định nghĩa. Chu trình đơn trong đồ thị G đi qua mỗi cạnh của đồ thị đúng một lần được gọi là chu trình Euler. Đường đi đơn trong G đi qua mỗi cạnh của nó đúng một lần được gọi là đường đi Euler. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler. Đồ thị có đường đi Euler được gọi là nửa Euler. Ví dụ 1 4 Khái niệm đồ thị Euler 2 2 Ví dụ 2 5 Điều kiện cần và đủ để đồ thị là Euler Đồ thị vô hướng Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Đồ thị có hướng Đồ thị có hướng liên thông yếu G là đồ thị Euler khi và chỉ khi tất cả các đỉnh của nó đều có bán đỉnh bậc ra bằng bán đỉnh bậc vào điều này làm cho đồ thị là liên thông mạnh 6 Chứng minh đồ thị là Euler Với đồ thị vô hướng Kiểm tra đồ thị có liên thông hay không Kiểm tra DFS u V hoặc BFS u V l iên thông Kiểm tra bậc của tất cả cả đỉnh có phải số chẵn hay không Với ma trận kề tổng các phần tử của hàng u cột u là bậc của đỉnh u. Với đồ thị có hướng Kiểm tra đồ thị có liên thông yếu hay không Kiểm tra đồ thị vô hướng tương ứng là liên thông hoặc Kiểm tra nếu tồn tại đỉnh u V để DFS u V hoặc BFS u V Kiểm tra tất cả các đỉnh có thỏa mãn bán bậc ra bằng bán bậc vào hay không Với ma trận kề bán bậc ra của đỉnh u là deg u là số các số 1 của hàng u bán bậc vào của đỉnh u là deg- u là số các số 1 của cột u. 7 Ví dụ với đồ thị vô hướng Cho đồ thị vô hướng được biểu diễn dưới dạng ma trận kề như hình dưới. Chứng minh là đồ thị Euler . Vì BFS 1 1 2 6 3 5 7 4 11 8 10 12 9 13 V. Do vậy G liên thông. Ta lại có deg 1 deg 13 2. deg 2 deg 3 4 deg 4 deg 5 4 deg 6 deg 7 4 deg 8 deg 9 4 deg 10 deg 11 deg 12 4 8 Ví dụ với đồ thị có hướng Cho đồ thị có hướng được biểu diễn dưới dạng ma trận kề như hình dưới. Chứng minh là đồ thị Euler . 9 Thuật toán tìm chu trình Euler 10 Kiểm nghiệm thuật toán 1 3 Tìm chu
