Giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình Poisson với tham số p4

Tham khảo tài liệu giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình poisson với tham số p4, 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ả
Nội dung trích xuất từ tài liệu:
Giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình Poisson với tham số p4Chương 4 Định tuyến trongmạng thông tin4.1. Yêu cầu về định tuyến trong mạng thông tin 4.1.1. Vai trò của định tuyến trong mạng thông tin 4.1.2. 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 4.1 là một ví dụ của một graph. Hình 4.1. 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={vi | i=1,2,......N} Trong đó N là số lượng nút. Tương tự E được biểu diễn: E={ei | 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ểmcuố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ánggiềng. Hai khái niệm trên là tương đương nhau trong các graph thôngthường. Tuy nhiên với các graph có nhiều hơn một liên kết giữa cùngmột cặp nút, thì hai khái niệm trên là không tương đương. Trongtrườ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ứ tự của các nút là không cóý nghiă. Ngược lại thứ tự các nút có ý nghĩa. Trong trường hợp thứ tựcác nút có ý nghĩa, một liên kết có thể được xem như là một cung vàđược định nghĩa aj=[vi,vk]hoặc đơn giản hơn aj=[i,k]k được gọi là cận kề hướng ra đối với i nếu một cung [i,k] tồn tại vàbậc hướng ra của i là số lượng các cung như vậy. Khái niệm cận kềhướng vào và bậc cận kề hướng vào cũng được định nghĩa tươngtự.Một graph gọi là một mạng nếu các liên kết và các nút có mặt trongliên kết có các thuộc tính (chẳng hạn như độ dài, dung lượng, loại...).Các mạng được sử dụng để mô hình các vấn đề cần quan tâm trongtruyền thông, các thuộc tính riêng biệt của nút và liên kết thì liên quanđến các vấn đề cụ thể trong truyền thông.Sự khác nhau giữa các liên kết và các cung là rất quan trọng cả vềviệc lập mô hình cho mạng lẫn quá trình hoạt động bên trong của cácthuật toán, vì vậy sự khác nhau cần phải luôn được phân biệt rõ ràng.Về mặt hình học các liên kết là các đường thẳng kết nối các cặp nútcòn các cung là các đường thẳng có mũi tên ở một đầu, biểu diễnchiều của cung.Một graph có các liên kết gọi là graph vô hướng, tuy nhiên mộtgraph có các cung gọi là graph hữu hướng. Một graph hữu hướngcó thể có cả các liên kết vô hướng. Thông thường , các graph đượcgiả sử là vô hướng, hoặc sự phân biệt đó là không có ý nghĩa.Có thể có khả năng xảy ra hiện tượng xuất hiện nhiều hơn một liên kếtgiữa cùng một cặp nút (điều này tương ứng với việc có nhiều kênhthông tin giữa hai chuyển mạch). Những liên kết như v ậy được gọi làcác liên kết song song. Một graph có liên kết song song gọi là mộtmultigraph. 38 Cũng có khả năng xuất hiện các liên kết giữa một nút nào đó và chính nút đó. Những liên kết đó được gọi là các self loop. Chúng ít khi xuất hiện và thường xuất hiện do việc xem hai nút như là một nút trong quá trình lập mô hình graph cho một mạng hoặc phát sinh trong quá trình thực hiện một thuật toán có việc hợp nhất các nút. Hình 4.2 minh hoạ một graph có các liên kết song song và các self loop. Một graph không có các liên kết song song hoặc các self loop gọi là một graph đơn giản. Việc biểu diễn và vận dụng các graph đơn giản là tương đối dễ dàng, vì vậy giả thiết rằng các graph được xem xét là các graph đơn giản. Nếu có sự khác biệt với giả thiết này, chúng sẽ được chỉ ra.4.2. Các mô hình đ ...