[macierz] narysuj graf i podaj koszty transp.

Przestrzenie wektorowe, bazy, liniowa niezależność, macierze.... Formy kwadratowe, twierdzenia o klasyfikacji...
AniaP.

[macierz] narysuj graf i podaj koszty transp.

Post autor: AniaP. »

Witam. Mam zadanie, które nie wiem jak rozwiązać. Może jest ktoś kto mi pomoże je rozwiązać. oto ono: Element (i,j) macieży podaje koszt transportu z miejsca i do j: (nie wiem jak zrobić macierz,więc napiszę jak wyglądają kolumny) kolumna A: 0 2 1 3 4 2, kolumna B: 2 0 4 5 3 4, C: 1 4 0 4 1 7, D: 3 5 4 0 8 5, E: 4 3 1 8 0 7, F: 2 4 7 5 7 0. Narysuj graf i podaj trasę dojazdu do wszystkich miejscowości, aby koszt transportu był najmniejszy. Pozdrawiam.

Edit by Maniek: Patrz na ogłoszenia : "Instrukcja TeX" wszystko jest napisane ..

\(\displaystyle{ \left[\begin{array}{ccc}0&2&1&3&4&2\\2&0&4&5&3&4\\1&4&0&4&1&7\\3&5&4&0&8&5\\4&3&1&8&0&7\\2&4&7&5&7&0\end{array}\right]}\) jesli się nie pomyliłem w przepisywaniu to chyba tak ma być ..
W_Zygmunt
Użytkownik
Użytkownik
Posty: 545
Rejestracja: 1 wrz 2004, o 22:47
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 53 razy

[macierz] narysuj graf i podaj koszty transp.

Post autor: W_Zygmunt »

Jeśli dobrze rozumiem, to chodzi o przejazd przez wszystkie miejscowości, tak aby koszt był najmniejszy.
Jest to zagadnienie, które w Teorii grafów nazywa się "Problemem komiwojażera". Opisany graf

jest grafem zupełnym, zatem istnieje w nim "cykl Hamiltona" i problem komiwojażera jest
jednoznacznie rozwiązywalny. (Proponuje w google wpisać "Problem komiwojażera").
Ja rozwiązałem poprzez eliminację krawędzi o najwyższych wagach, lecz tak by każdy wierzchołek pozostał
wierzchołkiem stopnia 2. W ten sposób otrzymałem cykl.

Usuwając z niego krawędź o najwyższej wadze otrzymamy szukaną ścieżkę.


PS. W _TEX_iarz-u macierz wpisuje się w odpowiednie rubryki

Traz kolejno klikając na : "Zatwierdź", "Przetwórz + TEX" oraz "Dodaj" i wklejając zawartość schowka
do postu otrzymamy
\(\displaystyle{ \left\[\begin{array}{cccccc}0&2&1&3&4&2\\ 2&0&4&5&3&4\\ 1&4&0&4&1&7\\ 3&5&4&0&8&5\\ 4&3&1&8&0&7\\ 2&4&7&5&7&0\end{array}\right\]}\)
ODPOWIEDZ