Đang chuẩn bị liên kết để tải về tài liệu:
lý thuyết đồ thị phần 1

Tham khảo tài liệu 'lý thuyết đồ thị phần 1', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | LýuiuyẾĩ DOTH Sách dùng cho Sinh iên các trường Ị ại học NGANH TIN HỌC 0 Chương 2 Cac bài toơn vế chu trinh-30 0 Chương 3 Đò thi phong--------------57 0 Chường 4 Cày-. 76 0 Chương 5 Boi toàn vế con đương ngớn nhát-------116 0 Chương 6 Một sô ap dụng------------141 0 PHỤ LỤC Hường dồn vo đop sò -.201 1.2 BIỂU Đồ Một đồ thị thường được biểu diễn bằng một biểu đồ như sau . Mổi đỉnh biểu diễn thành 1 điểm và mỗi cạnh biểu diễn thành 1 đoạn nối 2 đỉnh tương ứng với nó. THÍ DỤ 1 Dưới đây là biểu đồ của vài đồ thị. THÍ DỤ 2 Ta dùng ký hiệu Kn để chi đơn đổ thị đầy đú có n đinh. Biểu đồ cùa K với 1 n 5 như sau 6 1.3 BẬC CỦA MỘT ĐỈNH Xét một đỉnh V trong đồ thị G. Số cạnh tới V trong đó mỗi vòng tại V được kể là 2 cạnh tới V gọi là bậc degree của V và ký hiệu là d v . Đinh có bậc 0 gọi là đỉnh cô lập isolated vertex . Đinh có bậc 1 gọi là đỉnh treo pendant vertex cạnh tới đỉnh treo gọi là cạnh treo pendant edge . Đồ thị mà mọi đính đều là đinh cô lập gọi là đồ thị rồng null graph . 1.3.1 ĐỊNH Lý Với mọi dồ thi G V E ta có d v 2 I EI V v