tailieunhanh - Giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p4

Tham khảo tài liệu 'giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p4', công nghệ thông tin, tin học văn phòng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chương 4 Định tuyến trong mạng thông tin . Yêu câu về định tuyên trong mạng thông tin . Vai trò của định tuyên trong mạng thông tin . Các khái niệm trong lý thuyêt graph Phần này giới thiệu các thuật ngữ và các khái niệm cơ bản nhằm mô tả các mạng graph và các thuộc tính của nó. Lý thuyết graph là một môn học xuất hiện từ lâu nhưng lý thuyết này có một số thuật ngữ được chấp nhận khác nhau dùng cho các khái niệm cơ bản. Vì thế có thể sử dụng một số thuật ngữ khác nhau để lập mô hình graph cho mạng. Các thuật ngữ được trình bày dưới đây này là các thuật ngữ đã được công nhận và được sử dụng thường xuyên chương này. Một graph G được định nghiã bởi tập hợp các đỉnh V và tập hợp các cạnh E. Các đỉnh thường được gọi là các nút và chúng biểu diễn vị trí ví dụ một điểm chứa lưu lượng hoặc một khu vực chứa thiết bị truyền thông . Các cạnh được gọi là các liên kết và chúng biểu diễn phương tiện truyền thông. Graph có thể được biểu diễn như sau G V E Hình là một ví dụ của một graph. Hình . Một graph đơn giản Mặc dù theo lý thuyết V có thể là tập hợp rỗng hoặc không xác định nhưng thông thường V là tập hợp xác định khác rỗng nghĩa là có thể biểu diễn V v I i 1 2 .N T rong đó N là số lượng nút. T ương tự E được biểu diễn E e I i 1 2 .M Một liên kết ej tương ứng một kết nối giữa một cặp nút. Có thể biểu diễn một liên kết ej giữa nút i và k bởi 37 ej Vi Vk hoặc bởi ej i k Một liên kết gọi là đi tới một nút nếu nút đó là một trong hai điểm cuối của liên kết. Nút i và k gọi là kề nhau nếu tồn tại một liên kết i k giữa chúng. Những nút như vậy được xem là các nút láng giềng. Bậc của nút là số lượng liên kết đi tới nút hay là số lượng nút láng giềng. Hai khái niệm trên là tương đương nhau trong các graph thông thường. Tuy nhiên với các graph có nhiều hơn một liên kết giữa cùng một cặp nút thì hai khái niệm trên là không tương đương. Trong trường hợp đó bậc của một nút được định nghĩa là số lượng liên kết đi tới nút đó. Một liên kết có thể có hai hướng. Khi đó thứ