Wagi krawędzi w grafie

pytanie zadane 27 lipca 2022 w Matematyka, fizyka, logika przez maxkolanko1998 Gaduła (3,230 p.)

Uczę się grafów z matmy dyskretnej(wiem że to raczej nie to forum, ale na innym nie uzyskałem odpowiedzi wogóle) i poruszam kwestie grafów, a dokładniej jak ustalić wagi poszczególnych krawędzi w grafie. Męcze się już z tym trochę i szukam pomocy. Będę wdzięczny za pomoc.

komentarz 27 lipca 2022 przez jankustosz1 Nałogowiec (35,880 p.)

Nie rozumiem pytania. Podaj jakiś przykład o co Ci chodzi. W grafie ważonym każda krawędź ma wagę i możesz to np. zobaczyć na obrazku.

2 odpowiedzi

odpowiedź 27 lipca 2022 przez Wiciorny Ekspert (269,590 p.)

odpowiedź 27 lipca 2022 przez maxkolanko1998 Gaduła (3,230 p.)

To może podam przykład o co chodzi. Jest taki graf

I teraz pytanie jest takie. Wybrałem przypadkową krawędź. Dlaczego przy tej krawędzi waga wynosi 5. Jak coś takiego obliczyć?

komentarz 27 lipca 2022 przez jankustosz1 Nałogowiec (35,880 p.)

Waga wynosi 5 bo taki wzięliśmy sobie graf. Równie dobrze waga mogłaby być -20.

Graf reprezentuje jakiś problem np. może reprezentować drogi między miastami, a waga to np. długość tej drogi. Wagi będą taki jakie sobie wybierzemy.

komentarz 27 lipca 2022 przez Wiciorny Ekspert (269,590 p.)

wagi masz etykietowane od góry, tego się nie oblicza jeśli nie ma konkretnej ściezki która sumuje wagi i potrafisz na tej podstawie to obliczyc, dla grafu skierowanego.

Poświęc chociaż chwile czasu żeby się tego pouczyć https://courses.cs.vt.edu/~cs3114/Fall10/Notes/T22.WeightedGraphs.pdf
z definicji masz odpowiedź

komentarz 28 lipca 2022 przez radek024 Szeryf (77,160 p.)

Zakładam że maxkolanko ma na myśli sieci przepływowe - wówczas mówimy o przepustowości, a nie wadze. Przepustowość jak najbardziej można obliczyć - jeżeli mamy zdefiniowany ładunek, to przetaczając go przez graf możemy policzyć jego sieć resuidalną, ale to nie jest tożsame z wagą. Więcej powiedzieć nie mogę, nie znam aż tak dobrze tego tematu :D

komentarz 28 lipca 2022 przez jankustosz1 Nałogowiec (35,880 p.)

Nie napisał ani słowa o tym, że chodzi mu o przepływy, ani nawet nic co by to sugerowało.

Ale mogę na szybko streścić jak się robi ten graf na podstawie grafu przepływów, bo jest to bardzo proste. W grafie przepływów każda krawędź ma swoją maksymalną pojemność oraz obecne użycie. I na podstawie tego grafu można zrobić sieć resuidalną, czyli graf który na krawędziach ma wartość o jaką można "zwiększyć" przepływ w danym kierunku tak by nie wyjść poza limity, jeżeli kierunek jest zaporowy to zmniejszyć. Np. jak mamy krawędź z użyciem 3 i limitem 7 to powstanie nam krawędź w jedną stronę z wagą 4 i w drugą z wagą 3.