Bài Giảng Toán Rời Rạc - Chương 4: Lý Thuyết đồ Thị - TaiLieu.VN

Trang chủ » Toán Rời Rạc Và Lý Thuyết đồ Thị » Bài Giảng Toán Rời Rạc - Chương 4: Lý Thuyết đồ Thị - TaiLieu.VN

Có thể bạn quan tâm

OPTADS360 intTypePromotion=1 zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn tailieu.vn NÂNG CẤP Đăng Nhập | Đăng Ký Chủ đề »
  • Đề thi toán cao cấp 2
  • Đại số tuyến tính
  • Toán rời rạc
  • Xác suất thống kê
  • Phương trình vi phân
    • Toán cao cấp
    • Toán kinh tế
  • HOT
    • CMO.03: Bộ Tài Liệu Hệ Thống Quản Trị...
    • CEO.29: Bộ Tài Liệu Hệ Thống Quản Trị...
    • FORM.04: Bộ 240+ Biểu Mẫu Chứng Từ Kế...
    • CEO.27: Bộ Tài Liệu Dành Cho StartUp...
    • FORM.08: Bộ 130+ Biểu Mẫu Thống Kê...
    • LV.26: Bộ 320 Luận Văn Thạc Sĩ Y...
    • LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên...
    • TL.01: Bộ Tiểu Luận Triết Học
    • FORM.07: Bộ 125+ Biểu Mẫu Báo Cáo...
    CEO.24: Bộ 240+ Tài Liệu Quản Trị Rủi Ro Doanh...
TUYỂN SINH YOMEDIA ADSENSE Trang Chủ » Khoa Học Tự Nhiên » Toán học Bài giảng Toán rời rạc - Chương 4: Lý thuyết đồ thị

Chia sẻ: Nguyễn Hà | Ngày: | Loại File: PDF | Số trang:91

Thêm vào BST Báo xấu 752 lượt xem 58 download Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với "Bài giảng Toán rời rạc - Chương 4: Lý thuyết đồ thị" sẽ giúp bạn nắm vững kiến thức toán học gồm các khái niệm cơ bản về đồ thị EULER và đồ thị HAMILTON.

AMBIENT/ Chủ đề:
  • Toán kinh tế
  • Toán cao cấp
  • Đại số đại cương
  • Toán rời rạc
  • Bài giảng toán rời rạc
  • Toán thống kê
  • Toán học cơ bản
  • Lý thuyết đồ thị

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

Đă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 - Chương 4: Lý thuyết đồ thị

  1. Chương 4: LÝ THUYẾT ĐỒ THỊ
  2. Chương 4 4.1 MỞ ĐẦU 4.2 CÁC KHÁI NIỆM CƠ BẢN 4.3 ĐỒ THỊ EULER 4.4 ĐỒ THỊ HAMILTON BÀI TOÁN TÌM ĐƯỜNG ĐI 4.5 NGẮN NHẤT 4.6 CÂY
  3. 4.I MỞ ĐẦU Bài toán về những cây cầu ở Konigsber Năm 1736 Euler, cha đẻ của lý thuyết đồ thị, đã giải được bài toán hóc búa nổi tiếng thời đó về những cây cầu ở Konigberg. Thành phố Konigberg có hai hòn đảo nối với nhau và với 2 bờ sông bằng 7 chiếc cầu như hình vẽ.
  4. Tìm đường đi qua tất cả 7 cây cầu, mỗi cây cầu chỉ được đi qua một lần, sau đó quay về nơi xuất phát
  5. 4.2 CÁC KHÁI NIỆM CƠ BẢN 4.2.1 Đồ thị, đỉnh, cạnh, cung:  Đồ thị vô hướng G = (V, E) gồm tập V các đỉnh và tập E các cạnh. nh v w e Ví dụ:
  6. 4.2 CÁC KHÁI NIỆM CƠ BẢN  Đồ thị có hướng G = (V, E) gồm tập V các đỉnh và tập E các cạnh có hướng gọi là cung. cung v w e Mỗi cạnh e được liên kết với một cặp đỉnh (v, w) có thứ tự Ví dụ:
  7. 4.2 CÁC KHÁI NIỆM CƠ BẢN  Cho đồ thị G = (V, E). Cạnh e  E liên kết đỉnh v và w, ta nói e liên thuộc đỉnh v, w; đỉnh v và w gọi là kề nhau.  Cạnh song song:  Khuyên:  Đỉnh cô lập:
  8. 4.2 CÁC KHÁI NIỆM CƠ BẢN  Đồ thị hữu hạn: là đồ thị có số cạnh (cung) hữu hạn.  Đồ thị đơn: là đồ thị không có khuyên và không có cạnh song song.  Đồ thị đầy đủ: là đồ thị mà mọi cặp đỉnh đều kề nhau.  Bậc của đỉnh vV là tổng số cạnh liên thuộc với nó, kí hiệu d(v). Mỗi khuyên được tính cho 2 bậc. d(v) := Số cạnh + 2* Số khuyên
  9. 4.2 CÁC KHÁI NIỆM CƠ BẢN Đỉnh cô lập có bậc bằng 0  Đỉnh treo: là đỉnh có bậc bằng 1. Nửa bậc: Cho đồ thị có hướng G = (V, E). + Nửa bậc ra của đỉnh vV, kí hiệu dr(v) là số cung đi ra từ đỉnh v. + Nửa bậc vào của đỉnh vV, kí hiệu dv(v) là số cung đi vào đỉnh v
  10. MỘT SỐ TÍNH CHẤT * Tính chất 1: Cho đồ thị G = (V, E). Khi đó: i. Tổng bậc các đỉnh của đồ thị là số chẵn và d(v) = 2|E| ii. Nếu G là đồ thị có hướng thì: dv(v) = dr(v) = |E| * Tính chất 2: Cho đồ thị G(V, E). Khi đó số đỉnh bậc lẻ là số chẵn
  11. * Tính chất 3: Cho đồ thị đơn G = (V, E) có n đỉnh (n  2) có ít nhất hai đỉnh cùng bậc. * Tính chất 4: Cho đồ thị đơn G = (V, E) có n đỉnh (n > 2) có đúng 2 đỉnh cùng bậc thì 2 đỉnh này không thể đồng thời có bậc bằng 0 hoặc bằng n – 1.
  12. 4.2.2 Đường đi, chu trình, tính liên thông  Đường đi  từ đỉnh v đến đỉnh w là dãy các cạnh nối tiếp nhau bắt đầu từ đỉnh v và kết thúc tại đỉnh w. Số cạnh trên đường đi  là độ dài của đường đi . Đường đi  có độ dài n từ đỉnh v đến đỉnh w được biểu diễn như sau:  = (v, e1, v1, e2, v2, …, vn-1, en, w) Trong đó: vi (i = 1, …, n-1) là các đỉnh trên đường đi và ei (i = 1, …, n) là các cạnh trên đường đi liên thuộc các cạnh kề trước và sau nó.
  13.  Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau.  Đường đi đơn là đường đi không đi qua một cạnh quá một lần.  Chu trình đơn là chu trình không đi qua một cạnh quá một lần.  Đường đi sơ cấp là đường đi không đi qua một đỉnh quá một lần.  Chu trình sơ cấp là chu trình không đi qua một đỉnh quá một lần.
  14.  Đường đi có hướng trong đồ thị có hướng là dãy các cung nối tiếp nhau (e1, e2, …, en) thỏa mãn đỉnh cuối của cung ei là đỉnh đầu của cung ei+1, i = 1, …, n-1.  Chu trình có hướng là đường đi có hướng có đỉnh đầu và đỉnh cuối trùng nhau.  Đường đi đơn (chu trình đơn) có hướng là đường đi (chu trình) có hướng không đi qua một cung quá một lần.  Đường đi (chu trình) có hướng sơ cấp là đường đi (chu trình) có hướng không đi qua một đỉnh quá một lần.
  15. Ví dụ v1 e1 v2 e4 v3 e2 e9 e3 e8 e7 v4 e5 v5 e6 v6 a b c d e
  16.  Đồ thị liên thông là đồ thị mà mọi cặp đỉnh của nó đều có đường đi nối chúng với nhau.  Đồ thị con: Cho đồ thị G = (V, E). Đồ thị G’ = (G’, E’) là đồ thị con của G nếu: (i) V’ V và E’ E và (ii) e = (v,w)  E: e  E’  v, w  V’  Thành phần liên thông: Là đồ thị con liên thông tối đại của G.
  17. 4.2.3 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY a. Ma trận kề  Đồ thị vô hướng Cho đồ thị vô hướng G = (V, E) có n đỉnh theo thứ tự v1, v2, …, vn. Ma trận kề của đồ thị G là ma trận vuông A = (aij)n, trong đó aij là số cạnh nối vi với vj. Lưu ý mỗi khuyên được tính là 2 cạnh. Ma trận kề của đồ thị vô hướng luôn đối xứng qua đường chéo chính.
  18. v1 v2 Ví dụ: v3 Có ma trận kề là: v5 v4 v1 v2 v3 v4 v5 Tổng bậc v1 0 1 0 1 0 của v1 v2 1 0 1 1 0 v3 0 1 2 1 0 v4 1 1 1 0 1 v5 0 0n 0 n 1 0 d ( v i )   a ij   a ji , v i  V j1 j1
  19.  Đồ thị có hướng Cho đồ thị có hướng G = (V, E) có n đỉnh theo thứ tự v1, v2, …, vn. Ma trận kề của đồ thị G là ma trận vuông A = (aij)n, trong đó aij là số cung đi từ đỉnh vi đến vj. Ví dụ: v2 v6 e1 e4 e6 e3 e8 v1 v4 e5 e7 e2 v3 v5
  20. v1 v2 v3 v4 v5 v6 tổng bậc ra v1 0 1 1 0 0 0 của v1 v2 0 0 1 1 0 0 v3 0 0 0 1 0 0 v4 0 0 0 0 1 1 v5 0 0 0 0 0 1 v6 0 0 0 0 0 0 tổng bậc vào của v1
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

  • Bài giảng Toán rời rạc - Chương 2: Quan hệ hai ngôi

    pdf 21 p | 2672 | 171

  • Bài giảng Toán rời rạc - Chương 1: Quan hệ

    ppt 37 p | 828 | 142

  • Bài giảng Toán rời rạc: Phần V & VI - GVC ThS.Võ Minh Đức

    ppt 26 p | 587 | 63

  • Bài giảng Toán rời rạc - Chương 3: Đại số Bool

    ppt 68 p | 247 | 37

  • Bài giảng Toán rời rạc - Nguyễn Đức Nghĩa

    pdf 33 p | 329 | 31

  • Bài giảng Toán rời rạc: Bài 10 - TS. Nguyễn Văn Hiệu

    pdf 32 p | 152 | 26

  • Bài giảng Toán rời rạc: Bài 9 - TS. Nguyễn Văn Hiệu

    pdf 21 p | 118 | 24

  • Bài giảng Toán rời rạc: Bài 1 - TS. Nguyễn Văn Hiệu

    pdf 31 p | 225 | 20

  • Bài giảng Toán rời rạc: Bài 2 - TS. Nguyễn Văn Hiệu

    pdf 37 p | 164 | 20

  • Bài giảng Toán rời rạc 2 - Bài toán tìm đường đi ngắn nhất

    pdf 28 p | 366 | 16

  • Bài giảng Toán rời rạc: Bài 7 - TS. Nguyễn Văn Hiệu

    pdf 24 p | 129 | 16

  • Bài giảng Toán rời rạc: Bài 4 - TS. Nguyễn Văn Hiệu

    pdf 16 p | 141 | 14

  • Bài giảng Toán rời rạc: Bài 6 - TS. Nguyễn Văn Hiệu

    pdf 46 p | 108 | 11

  • Bài giảng Toán rời rạc: Bài 5 - TS. Nguyễn Văn Hiệu

    pdf 61 p | 113 | 11

  • Bài giảng Toán rời rạc: Bài 8 - TS. Nguyễn Văn Hiệu

    pdf 40 p | 104 | 10

  • Bài giảng Toán rời rạc: Bài 11 - TS. Nguyễn Văn Hiệu

    pdf 39 p | 104 | 8

  • Bài giảng Toán rời rạc: Chương 5 - Nguyễn Quỳnh Diệp

    pdf 84 p | 39 | 4

  • Bài giảng Toán rời rạc: Bài 2 - Vũ Thương Huyền

    pdf 42 p | 43 | 3

Thêm tài liệu vào bộ sưu tập có sẵn: Đồng ý Thêm vào bộ sưu tập mới: *Tên bộ sưu tập Mô Tả: *Từ Khóa: Tạo mới Báo xấu
  • Hãy cho chúng tôi biết lý do bạn muốn thông báo. Chúng tôi sẽ khắc phục vấn đề này trong thời gian ngắn nhất.
  • Không hoạt động
  • Có nội dung khiêu dâm
  • Có nội dung chính trị, phản động.
  • Spam
  • Vi phạm bản quyền.
  • Nội dung không đúng tiêu đề.
Hoặc bạn có thể nhập những lý do khác vào ô bên dưới (100 ký tự): Vui lòng nhập mã xác nhận vào ô bên dưới. Nếu bạn không đọc được, hãy Chọn mã xác nhận khác.. Đồng ý LAVA AANETWORK THÔNG TIN
  • Về chúng tôi
  • Quy định bảo mật
  • Thỏa thuận sử dụng
  • Quy chế hoạt động
TRỢ GIÚP
  • Hướng dẫn sử dụng
  • Upload tài liệu
  • Hỏi và đáp
HỖ TRỢ KHÁCH HÀNG
  • Liên hệ
  • Hỗ trợ trực tuyến
  • Liên hệ quảng cáo
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

Đang xử lý... Đồng bộ tài khoản Login thành công! AMBIENT

Từ khóa » Toán Rời Rạc Và Lý Thuyết đồ Thị