Bài giảng Lý thuyết đồ thị: Chương 1 - Tôn Quang Toại

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

Thêm vào BST

Báo xấu

21
lượt xem 4
download

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

Bài giảng Lý thuyết đồ thị: Chương 1 Một số khái niệm cơ bản về đồ thị, cung cấp cho người đọc những kiến thức như: Một số bài toán dẫn đến khái niệm đồ thị; Định nghĩa đồ thị và phân loại đồ thị; Các thuật ngữ cơ bản; Một số dạng đồ thị. Mời các bạn cùng tham khảo!

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 Lý thuyết đồ thị: Chương 1 - Tôn Quang Toại

CHƯƠNG 1 MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ Tôn Quang Toại Khoa CNTT, Đại học Ngoại ngữ - Tin học TP.HCM
Nội dung Một số bài toán dẫn đến khái niệm đồ thị Định nghĩa đồ thị và Phân loại đồ thị Các thuật ngữ cơ bản Một số dạng đồ thị
MỘT SỐ BÀI TOÁN DẪN ĐẾN KHÁI NIỆM ĐỒ THỊ
Một số bài toán dẫn đến khái niệm đồ thị Bài toán 1. Có cách nào xuất phát từ một vị trí, sau đó đi qua 7 cây cầu (mỗi cây cầu chỉ đi qua một lần) và trở về vị trí xuất phát?
Một số bài toán dẫn đến khái niệm đồ thị Bài toán 2. Có thể vẽ hình phong bì thư sau bởi một nét bút hay không? 1 2 3 4 5
Một số bài toán dẫn đến khái niệm đồ thị Bài toán 3. Một Sinh viên muốn đi từ nhà đến trường thì phải đi như thế nào? Cách đi nào là nhanh nhất?
ĐỊNH NGHĨA ĐỒ THỊ VÀ PHÂN LOẠI ĐỒ THỊ
Định nghĩa và phân loại đồ thị Định nghĩa Đồ thị Đồ thị là một mô hình toán học để biểu diễn tập các đối tượng (V) và mối quan hệ giữa các đối tượng đó (E). Đồ thị được định nghĩa bởi bộ (V, E) với: • V là tập các đỉnh (Vertices): V = {v1, v2, v3, …, vn} và n = |V| gọi là bậc/cấp của đồ thị • E là tập cạnh (Edges): E = {e1, e2, e3,… em} gồm một số cặp phần tử không có thứ tự (hay có thứ tự) của tập V và m = |E| gọi là kích thước của đồ thị.
Định nghĩa và phân loại đồ thị Ký hiệu đồ thị: G = (V, E) Ký hiệu cạnh: Cạnh ek nối 2 đỉnh vi và vj được ký hiệu là: ek = (vi, vj)
Định nghĩa và phân loại đồ thị Phân loại đồ thị: dựa vào 2 tiêu chuẩn Hướng của cạnh: • Đồ thị vô hướng • Đồ thị có hướng Số cạnh nối 2 đỉnh: • Đơn đồ thị • Đa đồ thị
Định nghĩa và phân loại đồ thị Đồ thị vô hướng: G=(V, E) là đồ thị vô hướng nếu tập cạnh E là tập các cặp không có thứ tự (các cạnh không có chiều).
Định nghĩa và phân loại đồ thị Đồ thị có hướng: G=(V, A) là đồ thị có hướng nếu tập cung A là tập các cặp có thứ tự (các cạnh có chiều).
Biểu diễn đồ thị bằng hình học Biểu diễn đỉnh: Mỗi đỉnh: là 1 điểm, 1 vòng tròn nhỏ hay 1 biểu tượng nào đó trong mặt phẳng hay không gian. Dùng ký hiệu, tên hoặc số hiệu của đỉnh ghi bên điểm tương ứng Biểu diễn cạnh (cung): Nếu e=(u, v) là một cạnh thì nối điểm u đến điểm v bằng một đoạn thẳng hay đoạn cong không đi qua các điểm biểu diễn các đỉnh khác. Nếu e=(u, v) là một cung thì nối điểm u đến điểm v bằng một đoạn thẳng định hướng hay đoạn cong định hướng không đi qua các điểm biểu diễn các đỉnh khác
Biểu diễn đồ thị bằng hình học x1 1 x2 x10 7 x1 x x12 x3 59 1 6 x15 3 2 x8 x1 x4 x14 3 4 8 x7 x5 x6
CÁC THUẬT NGỮ CƠ BẢN
Kề và Liên thuộc Cho cạnh e=(u, v) u kề (adjacent) với v. u có cạnh liên thuộc (incident) là e v e u
Đỉnh đầu và Đỉnh cuối Cho cung e=(u, v) u là đỉnh đầu (start-vertex) v là đỉnh cuối (end-vertex) Cung e đi ra khỏi đỉnh u và đi vào đỉnh v v e u
Khuyên, Đỉnh treo, Đỉnh cô lập Khuyên/Vòng (self-loop): Là cạnh (hoặc cung) có 2 đỉnh đầu trùng nhau. Đỉnh treo (pendant): Là đỉnh thuộc duy nhất một cạnh (hoặc cung). Đỉnh cô lập (isolated): Là đỉnh không thuộc cạnh (hoặc cung) nào.
Bậc của đỉnh Định nghĩa Bậc của đỉnh Cho đồ thị vô hướng G=(V, E) và đỉnh v ∈ V. Ta gọi bậc của v là số cạnh liên thuộc với đỉnh v (mỗi khuyên được tính 2 lần) 𝒅𝒅𝒅𝒅𝒅𝒅(𝒗𝒗) Ký hiệu: • Đỉnh cô lập (isolated) v có deg 𝑣𝑣 = 0 Chú ý: • Đỉnh treo (pendant) v có deg 𝑣𝑣 = 1
Bậc của đỉnh Ví dụ: 1 7 6 5 3 2 4 8 i 1 2 3 4 5 6 7 8 deg(i)