Xem trước tài liệu

Đang tải tài liệu...

Thông tin chi tiết tài liệu

Định dạng: PDF
Số trang: 54 trang
Dung lượng: 527 KB

Giới thiệu nội dung

Tính liên thông đỉnh, liên thông cạnh và các tính chất về bậc của đồ thị vô hướng

Tác giả: Nguyễn Thị Phương

Lĩnh vực: Toán học

Nội dung tài liệu:
Luận văn này tập trung tìm hiểu và trình bày kiến thức cơ bản về đồ thị, bao gồm các khái niệm về tính liên thông đỉnh, liên thông cạnh, cùng với các tính chất về bậc của đồ thị vô hướng. Nội dung được chia thành ba chương chính. Chương 1 cung cấp kiến thức nền tảng về đồ thị, bao gồm định nghĩa, phép toán, các loại đồ thị đặc biệt. Chương 2 đi sâu vào khái niệm liên thông đỉnh và liên thông cạnh, cùng các định lý liên quan và ví dụ ứng dụng. Chương 3 khám phá các tính chất về bậc của đỉnh trong đồ thị, bao gồm các kết quả về bậc, bán nhân tử và chu trình Hamilton, tạo cơ sở cho thuật toán tìm tập hợp tương thích lớn nhất.

Mục lục chi tiết:

  • Danh mục các ký hiệu
  • Danh mục các hình vẽ
  • Mở đầu
  • Chương 1: Kiến thức chuẩn bị
    • 1.1. Khái niệm đồ thị
      • 1.1.1. Định nghĩa và các ký hiệu
      • 1.1.2. Phép toán trên đồ thị
      • 1.1.3. Đồ thị đẳng cấu
      • 1.1.4. Bậc của đỉnh trong đồ thị
    • 1.2. Đường đi và chu trình
    • 1.3. Tính liên thông của đồ thị
    • 1.4. Một số dạng đồ thị đặc biệt
      • 1.4.1. Đồ thị rỗng và đồ thị không
      • 1.4.2. Rừng và cây
      • 1.4.3. Đồ thị đầy đủ
      • 1.4.4. Đồ thị vòng, đồ thị đường và đồ thị bánh xe
      • 1.4.5. Đồ thị đều (đồ thị chính qui)
      • 1.4.6. Đồ thị hai phần
      • 1.4.7. Phần bù của đơn đồ thị
  • Chương 2: Liên thông đỉnh và liên thông cạnh của đồ thị
    • 2.1. Liên thông cấp k giữa hai đỉnh
    • 2.2. Đồ thị k – liên thông
    • 2.3. Đỉnh khớp
    • 2.4. Liên thông cạnh cấp ℓ giữa hai đỉnh
  • Chương 3: Các tính chất về bậc của đồ thị
    • 3.1. Di chuyển trên đồ thị
    • 3.2. Đồ thị đồng bậc
    • 3.3. Bán nhân tử
    • 3.4. Tập hợp tương thích lớn nhất
  • Kết luận
  • Tài liệu tham khảo