Optymalizacja wykorzystania połączeń na bazie grafu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
VxHZaX
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 11 maja 2021, o 08:53
Płeć: Mężczyzna
wiek: 26

Optymalizacja wykorzystania połączeń na bazie grafu

Post autor: VxHZaX » 11 maja 2021, o 10:09

Mam taki oto problem do rozważenia: sieć składająca się z 6 węzłów, odwzorowana do postaci grafu skierowanego jak poniżej. Każda krawędź (połączenie) posiada określoną przepustowość w Mb/s (wagę).

https://www.linkpicture.com/q/firstgrapth.jpg


Mam zatem dostępne ścieżki:

0 --> 1 --> 3 --> 5
0 --> 1 --> 4 --> 5
0 --> 2 --> 4 --> 5
0 --> 1 --> 2 --> 4 --> 5
0 --> 1 --> 3 --> 4 --> 5
0 --> 2 --> 1 --> 3 --> 5
0 --> 2 --> 1 --> 4 --> 5
0 --> 2 --> 1 --> 3 --> 4 --> 5

Jak zaplanować rozłożenie 3 rodzajów stałej transmisji IP (np. 0.5, 1 oraz 2 Mb/s) tak aby połączenia pomiędzy węzłami były możliwie równomiernie wykorzystane? Czy jest możliwe sprowadzenie tego problemu np. do zadania programowania liniowego? Będę wdzięczny za podpowiedzi.
ps. Próbowałem osadzić obraz w poście na wiele sposobów, ale niestety nie udało się :(
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

ODPOWIEDZ