Bậc của đỉnh: số cạnh liên thuộc với v gọi là bậc của đỉnh v, kí hiệu là d(v). Bậc của đỉnh có khuyên được cộng thêm 2 cho mỗi khuyên. | GIỚI THIỆU MÔN HỌC Tên môn học: Lý thuyết đồ thị Số tiết: 30 LT Hình thức đánh giá: Thi giữa kỳ: 20% Bài tập lớn: 30% Thi cuối kỳ: 50% Giáo viên: Nguyễn Văn Lễ Nội dung CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CHƯƠNG 2: BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH CHƯƠNG 3: CÁC THUẬT TOÁN DUYỆT ĐỒ THỊ CHƯƠNG 4: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON CHƯƠNG 5: CÂY CHƯƠNG 6: BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT CHUƠNG 1: CÁC KHÁI NIỆM CƠ BẢN Định nghĩạ đồ thị: Một đồ thị ký hiệu là G=(V,E), trong đó V: tập đỉnh E={(u,v) | u,v V}: tập cạnh n=|V| gọi là cấp của đồ thị Đồ thị vô hướng: Là đồ thị gồm các cạnh vô hướng (không thứ tự): (u,v) E; (v,u) E 2 1 3 4 V={1,2,3,4} E={(1,2), (1,3), (2,3), (3,4)} Định nghĩa đồ thị Đồ thị có hướng: là đồ thị gồm các cạnh có thứ tự được gọi là cung. Đơn đồ thị: Mỗi cặp đỉnh chỉ có duy nhất một cạnh (cung) V={1,2,3,4} E={(1,2),(2,3),(3,1),(5,3)} 2 1 3 4 5 2 1 3 4 5 2 1 3 4 5 Đa đồ thị: mỗi cặp đỉnh có thể có một hay nhiều cạnh (cung) Đồ thị có trọng số: trên mỗi cạnh (cung) được gắn một giá trị gọi là trọng số 2 1 3 4 5 2 1 3 4 5 2 1 3 4 5 3 1 -2 5 2 3 2 1 3 4 5 1 2 1 3 Định nghĩa đồ thị Một số khái niệm Một số khái niệm: Khuyên: cạnh (cung) gọi là khuyên nếu đỉnh đầu trùng với đỉnh cuối. Cạnh (cung) lặp: là hai cạnh (cung) cùng tương ứng với một cặp đỉnh. 1 1 2 1 2 Đỉnh kề: nếu (u,v) là cạnh (cung) của đồ thị thì v gọi là kề của u. Trong đồ thị vô hướng nếu v kề u thì u cũng kề v. Cạnh liên thuộc: cạnh e=(u,v) gọi là cạnh liên thuộc với hai đỉnh u, v. Bậc của đỉnh: số cạnh liên thuộc với v gọi là bậc của đỉnh v, kí hiệu là d(v). Bậc của đỉnh có khuyên được cộng thêm 2 cho mỗi khuyên. 2 1 3 4 5 d(1)=1 d(2)=3 d(3)=2 d(4)=3 d(5)=3 Một số khái niệm Đỉnh cô lập, đỉnh treo: Đỉnh bậc 0 gọi là đỉnh cô lập, đỉnh bậc 1 gọi là đỉnh treo. 2 1 3 4 5 . | GIỚI THIỆU MÔN HỌC Tên môn học: Lý thuyết đồ thị Số tiết: 30 LT Hình thức đánh giá: Thi giữa kỳ: 20% Bài tập lớn: 30% Thi cuối kỳ: 50% Giáo viên: Nguyễn Văn Lễ Nội dung CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CHƯƠNG 2: BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH CHƯƠNG 3: CÁC THUẬT TOÁN DUYỆT ĐỒ THỊ CHƯƠNG 4: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON CHƯƠNG 5: CÂY CHƯƠNG 6: BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT CHUƠNG 1: CÁC KHÁI NIỆM CƠ BẢN Định nghĩạ đồ thị: Một đồ thị ký hiệu là G=(V,E), trong đó V: tập đỉnh E={(u,v) | u,v V}: tập cạnh n=|V| gọi là cấp của đồ thị Đồ thị vô hướng: Là đồ thị gồm các cạnh vô hướng (không thứ tự): (u,v) E; (v,u) E 2 1 3 4 V={1,2,3,4} E={(1,2), (1,3), (2,3), (3,4)} Định nghĩa đồ thị Đồ thị có hướng: là đồ thị gồm các cạnh có thứ tự được gọi là cung. Đơn đồ thị: Mỗi cặp đỉnh chỉ có duy nhất một cạnh (cung) V={1,2,3,4} .
