Báo cáo tài liệu vi phạm
Giới thiệu
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
THỊ TRƯỜNG NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Thông tin
Tài liệu Xanh là gì
Điều khoản sử dụng
Chính sách bảo mật
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CHƯƠNG 2
Đang chuẩn bị liên kết để tải về tài liệu:
GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CHƯƠNG 2
Xuân Hương
92
11
pdf
Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG
Tải xuống
BIỂU DIỄN ĐỒ THỊ TRÊN MÁY VI TÍNH Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. | CHƯƠNG 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY VI TÍNH Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Vì vậy việc chọn lựa cấu trúc dữ liệu để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ thể bài toán và thuật toán cụ thể . Trong mục này chúng ta sẽ xét một số phương pháp cơ bản được sử dụng để biểu diễn đồ thị trên máy tính đồng thời cũng phân tích một cách ngắn gọn những ưu điểm cũng như những nhược điểm của chúng. 1. MA TRẬN KỀ. MA TRẬN TRỌNG SỐ Xét đơn đồ thị vô hướng G V E với tập đỉnh V 1 2 . . . n tập cạnh E ei e2 . . . em . Ta gọi ma trận kề của đồ thị G là ma trận. A ai j i j 1 2 . . . n Với các phần tử được xác định theo qui tắc sau đây ai j 0 nếu i j I E và ai j 1 nếu i j ĩ E i j 1 2 . . . n. JThí dụ 1. Ma trận trận kề của đồ thị vô hướng cho trong hình 1 là 1 2 3 4 5 6 1 0 110 10 2 10 10 10 3 110 10 0 4 0 0 10 11 5 110 10 1 6 0 0 0 1 1 0 Hình 1. Đồ thị vô hướng G và Đồ thị có hướng G1 --Các tính chất của ma trận kề 1 Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng tức là a i j a j i i j 1 2 . . . n. ngược lại mỗi 0 1 -ma trận đối xứng cấp n sẽ tương ứng chính xác đến cách đánh số đỉnh còn nói là chính xác đến đẳng cấu với một đơn đồ thị vô hướng n đỉnh. 2 Tổng các phần từ trên dòng i cột j của ma trận kề chính bằng bậc của đỉnh i đỉnh j . 3 nếu ký hiệu aịjp i j 1 2 . . . n là phần tử của ma trận Ap A.A. . .A p thừa số Khi đó aịjp i j 1 2 . . . n cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung gian. Ma trận kề của đồ thị có hướng được định nghĩa một cách hoàn toàn tương tự. JThí dụ 2. Đồ thị có hướng G1 cho trong hình 1 có ma trận kề là ma trận sau 1 2 3 4 5 6 1 0 110 0 0 2 0 0 0 0 0 0 3 0 10 10
TÀI LIỆU LIÊN QUAN
Giáo trình Lý thuyết đồ thị: Phần 1 - PGS. Nguyễn Cam, PTS. Chu Đức Khánh
Giáo trình Lý thuyết đồ thị: Phần 2 - PGS. Nguyễn Cam, PTS. Chu Đức Khánh
Đề thi LÝ THUYẾT ĐỒ HỌA K27 (lần 2)
Giáo trình Lý thuyết tài chính - tiền tệ (Nghề Kế toán doanh nghiệp - Trình độ Trung cấp) - CĐ GTVT Trung ương I
Quản lý môi trường đô thị và khu công nghiệp
Giáo trình Toán rời rạc và lý thuyết đô thị
Giáo trình Mô hình toán ứng dụng (Có hướng dẫn sử dụng phần mềm): Phần 1
Kiến trúc sư làm gì để biến đổi đô thị?
Giáo án môn lý thuyết đồ thị
Bài tập về lý thuyết đồ thị
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.