zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 1: Đại cương về đồ thị

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:44

Báo xấu

215
lượt xem 42
download

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

Mời các bạn cùng tham khảo Bài giảng Toán rời rạc ứng dụng trong tin học - Chương 1: Đại cương về đồ thị sau đây để hiểu rõ hơn về khái niệm đồ thị, biểu diễn đồ thị, một số đồ thị đặc biệt, đồ thị có hướng,... Tham khảo nội dung bài giảng để nắm bắt 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 ứng dụng trong tin học - Chương 1: Đại cương về đồ thị

TOÁN RỜI RẠC ỨNG DỤNG TRONG TIN HỌC  Giảng viên:  Cao Thanh Tình (Email: tinhct@uit.edu.vn)  Bộ môn Toán Lý – ĐHCNTT – ĐHQGTPHCM 1
Nội dung môn học  Phần 1: Lý thuyết đồ thị  Đại cương về đồ thị  Các bài toán về đường đi  Đồ thị phẳng và bài toán tô màu đồ thị  Cây  Phần 2: Đại số Boole  Đại số Boole  Cổng logic  Cực tiểu hóa hàm Boole Chương 1. Đại cương về đồ thị 2
Các khái niệm cơ bản  Đồ thị (Graph)  G = (V, E) với V≠∅  V: tập các đỉnh  E: tập các cạnh  Cạnh e∈E  ứng với 2 đỉnh u, v∈V  v, w là 2 đỉnh kề (hay liên kết) với nhau, e liên thuộc với v và w  Ký hiệu: e = vw (…)  u ≡ v: e được gọi là vòng (khuyên) tại u Chương 1. Đại cương về đồ thị 3
Các khái niệm cơ bản  Đồ thị (Graph)  Cạnh bội (song song)  Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh B x  Đơn đồ thị A C  Đồ thị không có vòng và y z cạnh song song D  Đa đồ thị  Các đồ thị không phải là đơn đồ thị Chương 1. Đại cương về đồ thị 4
Các khái niệm cơ bản  Đồ thị (Graph)  Đồ thị đầy đủ  Đồ thị mà mọi cặp đỉnh đều kề nhau  K : đơn đồ thị đầy đủ n  Đồ thị con  Đồ thị G’ = (V’, E’)  V’ ⊆ V, E’ ⊆ E  Đồ thị hữu hạn  E và V hữu hạn  Đồ thị vô hạn Chương 1. Đại cương về đồ thị 5
Biểu diễn đồ thị  Biểu diễn hình học  Mỗi đỉnh ≡ một điểm  Mỗi cạnh ≡ một đường (cong hoặc thẳng) nối 2 đỉnh liên thuộc với nó  Biểu diễn bằng ma trận  Thường được dùng để biểu diễn trên máy tính  2 cách biểu diễn thường dùng  Ma trận kề  Ma trận liên thuộc Chương 1. Đại cương về đồ thị 6
Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ma trận vuông cấp n (số đỉnh của đồ thị)  Các phần tử aij được xác định bởi  aij = 1: Nếu vivj là một cạnh của G  aij = 0: Nếu vivj không là một cạnh của G  Tính chất  Phụ thuộc vào thứ tự liệt kê của các đỉnh  Ma trận là đối xứng  Một vòng được tính là một cạnh (akk = 1) Chương 1. Đại cương về đồ thị 7
Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ví dụ 1 Chương 1. Đại cương về đồ thị 8
Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận kề  Ví dụ 2 B D A B C D E A 0 1 1 0 0 B 1 0 1 1 1 A C D 1 1 0 1 2 0 1 1 1 2 C E E 0 1 2 2 0 Chương 1. Đại cương về đồ thị 9
Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma trận liên thuộc  Ma trận M = (mij)nxm  Các phần tử mij được xác định bởi  mij = 1: Nếu cạnh ej liên thuộc với vi của G  mij = 0: Nếu cạnh ej không liên thuộc với vi của G  Tính chất  Các cột tương ứng với các cạnh bội là giống nhau trong ma trân liên thuộc  Các vòng ứng với một cột có đúng một phần tử bằng 1 ứng với đỉnh nối với nó. Chương 1. Đại cương về đồ thị 10
Biểu diễn đồ thị  Biểu diễn bằng ma trận  Ma liên thuộc  Ví dụ Chương 1. Đại cương về đồ thị 11
Biểu diễn đồ thị  Biểu diễn bằng bảng (danh sách liền kề)  Lưu trữ các đỉnh liền kề với một đỉnh Đỉn Đỉnh liền kề  Ví dụ h b c a b, c, e a b a c a, c, d, e e d d c, e e a, c, d Chương 1. Đại cương về đồ thị 12
Các khái niệm cơ bản  Bậc của đỉnh  Đỉnh của đồ thị G có bậc là n nếu nó kề với n đỉnh khác. g f e  Ký hiệu: deg(v) hay d(v)  Mỗi vòng được kể là 2 cạnh tới một đỉnh  Đỉnh cô lập ⇔ deg(v)=0 a b c d  Đỉnh treo ⇔ deg(v)=1  Cạnh treo có đầu mút là một đỉnh treo  Đồ thị rỗng: deg(v)=0 ∀v Chương 1. Đại cương về đồ thị 13
Các khái niệm cơ bản  B ậc của đỉnh  Định lý 1.1  Trong mọi đồ thị G = (V, E), tổng số bậc của các đỉnh của G bằng 2 lần số cạnh của nó  Hệ quả  Trong mọi đồ thị G = (V, E) ta có  Số đỉnh bậc lẻ là một số chẵn  Tổng bậc của đỉnh bậc lẻ là một số chẵn Chương 1. Đại cương về đồ thị 14
Các khái niệm cơ bản  B ậc của đỉnh  Định lý 1.2  Trong mọi đồ thị G = (V, E), nếu số đỉnh nhiều hơn 1 thì tồn tại ít nhất hai đỉnh cùng bậc  Định lý 1.3  Trong mọi đồ thị G = (V, E), nếu số đỉnh nhiều hơn 2 và có đúng hai đỉnh cùng bậc thì hai đỉnh này không đồng thời bằng 0 hoặc n-1 Chương 1. Đại cương về đồ thị 15
Các khái niệm cơ bản  Chứng minh và giải toán bằng phương pháp đồ thị 1. Xây dựng đồ thị mô tả đầy đủ thông tin của bài toán  Mỗi đỉnh v∈V ≡ các đối tượng trong bài toán  Mỗi cạnh e∈E ≡ mối quan hệ giữa hai đối tượng  Vẽ đồ thị mô tả bài toán 1. Sử dụng các định nghĩa, tính chất, định lý, … suy ra điều cần phải chứng minh Chương 1. Đại cương về đồ thị 16
Các khái niệm cơ bản  Một số bài toán ví dụ Chứng minh rằng trong một cuộc họp tùy ý có ít nhất 2 đại biểu tham gia trở lên, luôn có ít nhất hai đại biểu mà họ có số người quen bằng nhau trong các đại biểu đến dự họp Chương 1. Đại cương về đồ thị 17
Các khái niệm cơ bản  Một số bài toán ví dụ Chứng minh rằng số người mà mỗi người đã có một số lẻ lần bắt tay nhau trên trái đất là một con số chẵn. Chương 1. Đại cương về đồ thị 18
Một số đồ thị đặc biệt  Đồ thị đầy đủ Kn  Đơn đồ thị  Số đỉnh: |V| = n  Bậc: deg(v) = n – 1 ∀v ∈V  Số cạnh: |E| = n(n - 1) / 2 K1 K2 K3 K4 K5 K6 Chương 1. Đại cương về đồ thị 19
Một số đồ thị đặc biệt  Đồ thị vòng Cn  Đơn đồ thị  Số đỉnh: |V| = n ≥ 3  Bậc: deg(v) = 2 ∀v ∈V  Số cạnh: |E| = n Chương 1. Đại cương về đồ thị 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

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.