Bài giảng Toán rời rạc: Đồ thị có hướng - Trần Vĩnh Đức

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

24
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc: Đồ thị có hướng cung cấp cho người học những nội dung kiến thức như: Định nghĩa và ví dụ, đồ thị định hướng, đồ thị thi đấu, đường đi Hamilton. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Đồ thị có hướng - Trần Vĩnh Đức

Đồ thị có hướng Trần Vĩnh Đức Ngày 24 tháng 7 năm 2018 CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 34
Tài liệu tham khảo ▶ Eric Lehman, F Thomson Leighton & Albert R Meyer, Mathematics for Computer Science, 2013 (Miễn phí) ▶ Ngô Đắc Tân, Lý thuyết Tổ hợp và Đồ thị, NXB ĐHQG Hà Nội, 2004. ▶ Douglas B. West. Introduction to Graph Theory. 2nd Edition, 2000. CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 34
Nội dung Định nghĩa và ví dụ Đồ thị thi đấu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Định nghĩa Một đồ thị có hướng là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là một tập con của tích đề các V × V, tức E là một quan hệ hai ngôi trên V. ▶ Các phần tử của V thường được gọi là các đỉnh. ▶ Các phần của E gọi là các cung. ▶ Cụ thể hơn, nếu (a, b) ∈ E thì (a, b) được gọi là cung của G với đỉnh đầu là a và đỉnh cuối là b, ▶ và ta viết a → b CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 34
Đồ thị có hướng v2 Đồ thị có hướng G = (V, E): V = {v1 , v2 , v3 } v1 E = {v1 → v1 , v1 → v2 , v1 → v3 , v2 → v3 , v3 → v2 } v3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 34
Bậc vào & bậc ra v2 Đỉnh indeg outdeg v1 1 3 v1 v2 2 1 v3 2 1 5 5 v3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 34
v2 Mệnh đề ∑ ∑ v1 indeg(v) = outdeg(v) = |E| v∈V v∈V v3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 34
Hành trình có hướng và đường đi có hướng Hành trình Hành trình đơn Đường đi Lặp cạnh 3 7 7 Lặp đỉnh 3 3 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 34
Định nghĩa Xét G = (V, E) là đồ thị có hướng với V = {v1 , v2 , . . . , vn }. Ma trận kề A = (aij ) của G định nghĩa bởi { 1 nếu vi → vj aij = 0 ngược lại. Ví dụ v2   1 1 1 v1 A = 0 0 1 0 1 0 v3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 / 34
Định lý Xét G = (V, E) là đồ thị có hướng với n đỉnh V = {v1 , v2 , . . . , vn }. (k) và A = (aij ) là ma trận kề của G. Xét (pij ) là số hành trình có hướng từ vi tới vj . Khi đó (k) Ak = (pij ). CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 34
Ví dụ v2   1 1 1 A= 0 0 1 v1 0 1 0     1 2 2 1 3 3 A2 = 0 1 0 A3 = 0 0 1  v3 0 0 1 0 1 0 CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 34
Chứng minh ▶ Bằng quy nạp theo độ dài hành trình. ▶ Ta ký hiệu aij(k) là phần tử ở hàng i cột j của ma trận Ak . ▶ Ta đặt (k) (k) P(k) := ∀i, j aij = pij ▶ Bước cơ sở: k = 1. 3 Tại sao? CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 34
Chứng minh: Bước quy nạp ▶ Giả sử P(k) 3 ▶ Hành trình độ dài k + 1 từ vi đến vj có thể tách thành k vi ; vh → vj k ▶ với vi ; vh là một hành trình độ dài k từ vi tới vh ▶ và h : vh → vj là một cạnh trong G. CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 34
Chứng minh: Bước quy nạp (tiếp) (k+1) ∑ (k) ∑ n (k) pij = pih = pih · ahj h: vh →vj h=1 ∑ n (k) = aih · ahj (giả thiết quy nạp) h=1 (k+1) = aij (quy tắc nhân ma trận) 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 14 / 34
Định nghĩa Một đồ thị có hướng G = (V, E) là liên thông mạnh nếu với mọi u, v ∈ V, tồn tại một đường đi có hướng từ u tới v trong G. CuuDuongThanCong.com https://fb.com/tailieudientucntt 15 / 34
Định nghĩa Một đồ thị có hướng được là phi chu trình (DAG) nếu nó không chứa chu trình có hướng. v2 v1 v4 v5 v3 CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 34
Nội dung Định nghĩa và ví dụ Đồ thị thi đấu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Định nghĩa ▶ Một đồ thị định hướng của một đồ thị (vô hướng) G = (V, E) là một đồ thị có hướng thu được từ G bằng cách chọn một hướng x→y hoặc y → x cho mỗi cạnh xy ∈ E. ▶ Đồ thị thi đấu là một đồ thị định hướng của một đồ thị đầy đủ nào đó. CuuDuongThanCong.com https://fb.com/tailieudientucntt 18 / 34
Ví dụ ▶ Đồ thị định hướng của đồ thị đầy đủ cho phép mô hình hóa các giải đấu thể thao kiểu “round-robin”. ▶ Giải đấu gồm n đội và mỗi đội thi đấu với tất cả các đội khác. ▶ Với mỗi cặp u, v, ta có cạnh u → v nếu u thắng v. ▶ Cuối giải ta có một đồ thị định hướng của Kn . ▶ “Điểm số” của mỗi đội chính là bậc ra của đội đó, là số lần thắng. CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 34
Đội nào vô địch? CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 34