Izpitno vprašanje RAČ2PRA 18300

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Vprašanje


|Vpr. 18300|

Navedi vse krožne poti vozlišč označenih od 1 do 7, ki vsebujejo:

  • a. Povezavo med vozlišči 1 in 3 ter 5 in 1.
  • b. Pot 1 - 2 - 6 - 4 - 3
  • c. Pot 2 - 6 - 4 - 3
  • d. Povezave 1 - 2, 3 - 5, 7 - 4


Kako bi predstavil ustrezno matriko omrežja, ki bi predstavljala zgoraj navedena stanja?


Odgovor


a.

Imamo dve povezavi: 1 - 3 in 5 - 1, iz tega lahko predpostavljamo, da dobimo povezavo 5 - 1 - 3.
Naloga od nas zahteva, da zapišemo vse krožne poti vozlišč označenih od 1 do 7, ki vsebujemo našo povezavo: 5 - 1 - 3.

5 - 1 - 3 - 2 - 4 - 6 - 7 - 5
5 - 1 - 3 - 2 - 4 - 7 - 6 - 5
5 - 1 - 3 - 2 - 6 - 4 - 7 - 5
5 - 1 - 3 - 2 - 6 - 7 - 4 - 5
5 - 1 - 3 - 2 - 7 - 4 - 6 - 5
5 - 1 - 3 - 2 - 7 - 6 - 4 - 5
5 - 1 - 3 - 4 - 2 - 6 - 7 - 5
5 - 1 - 3 - 4 - 2 - 7 - 6 - 5
5 - 1 - 3 - 4 - 6 - 2 - 7 - 5
5 - 1 - 3 - 4 - 6 - 7 - 2 - 5
5 - 1 - 3 - 4 - 7 - 2 - 6 - 5
5 - 1 - 3 - 4 - 7 - 6 - 2 - 5
5 - 1 - 3 - 6 - 2 - 4 - 7 - 5
5 - 1 - 3 - 6 - 2 - 7 - 4 - 5
5 - 1 - 3 - 6 - 4 - 2 - 7 - 5
5 - 1 - 3 - 6 - 4 - 7 - 2 - 5
5 - 1 - 3 - 6 - 7 - 2 - 4 - 5
5 - 1 - 3 - 6 - 7 - 4 - 2 - 5
5 - 1 - 3 - 7 - 2 - 4 - 6 - 5
5 - 1 - 3 - 7 - 2 - 6 - 4 - 5
5 - 1 - 3 - 7 - 4 - 2 - 6 - 5
5 - 1 - 3 - 7 - 4 - 6 - 2 - 5
5 - 1 - 3 - 7 - 6 - 2 - 4 - 5
5 - 1 - 3 - 7 - 6 - 4 - 2 - 5


b.

Vse krožne poti vozlišč, ki vsebujemo pot 1 - 2 - 6 - 4 - 3:

1 - 2 - 6 - 4 - 3 - 5 - 7 - 1
1 - 2 - 6 - 4 - 3 - 7 - 5 - 1


c.

Podobno koz zgoraj, samo da imamo tu "krajšo" pot, 2- 6 - 4 - 3.
Vse krožne poti vozlišč, ki vsebujemo pot 2 - 6 - 4 - 3:

2 - 6 - 4 - 3 - 1 - 5 - 7 - 2
2 - 6 - 4 - 3 - 1 - 7 - 5 - 2
2 - 6 - 4 - 3 - 5 - 1 - 7 - 2
2 - 6 - 4 - 3 - 5 - 7 - 1 - 2
2 - 6 - 4 - 3 - 7 - 1 - 5 - 2
2 - 6 - 4 - 3 - 7 - 5 - 1 - 2


d.

Sedaj imamo povezave: 1 - 2, 3 - 5, 7 - 4.
Vse krožne poti z zgornjimi povezavi:

1 - 2 - 6 - 3 - 5 - 7 - 4 - 1
1 - 2 - 3 - 5 - 6 - 7 - 4 - 1
1 - 2 - 3 - 5 - 7 - 4 - 6 - 1.

Matrike, ki predstavljajo zgoraj navedena stanja:

ad a) Imamo dve povezavi: 1 - 3 in 5 - 1, iz tega lahko predpostavljamo, da dobimo povezavo 5 - 1 - 3.

x x x x
x x x x x
x x x x
x x x x
x x x x
  • iz vozlišča 5 ne smemo več v nobeno vozlišče --> 5. vrstico damo na ∞
  • iz vozlišča 1 ne smemo več v nobeno vozlišče --> 1. vrstico damo na ∞
  • v 1. vozlišče ne smemo več priti --> 1. stolpec damo na ∞
  • v 3. vozlišče ne smemo več priti --> 3. stolpec damo na ∞

ad b)

ad c)

ad d)

Kratka razlaga reševanja naloge na krajšem primeru


Nalogo rešujemo s pomočjo "PROBLEM TRGOVSKEGA POTNIKA" oziroma s pomočjo redukcije matrike po vrsticah in stolpcih.
Iz vozlišča 1 lahko gremo v vozlišča 2, 3, 4 in 5.

  • Kaj pomeni, da gremo iz vozlišča 3 v vozlišče 5?
    • pot nas bo stala C35 - povečamo spodnjo mejo,
    • iz 3 ne smemo v nobeno drugo vozlišče; vse ostale vrednosti v 3. vrstici postavimo na ∞,
    • v 5 ne smemo priti iz nobenega drugega vozlišča; vse ostale vrednosti v 5. stolpcu postavimo na ∞.


Imamo matriko omrežja:

20 30 10 11
15 16 4 2
3 5 2 4
19 6 18 3
16 4 7 16


  • Vozlišče 1 bomo zapustili na vsaki krožni poti.
  • Tega ne moremo storiti, če nimamo vsaj 10 enot sredstev.
  • Prav tako moramo zapustiti ostala vozlišča.
    • Da zapustimo vozlišče 2, potrebujemo vsaj 2 enoti sredstev, da zapustimo vozlišče 3 potrebujemo 2 enoti, da zapustimo vozlišče 4 potrebujemo 3 enote in da zapustimo vozlišče 5 potrebujemo 4 enote sredstev.

Po domače povedano: v vsaki vrstici odštejemo najmanjše število; v prvi vrstici odštejemo 10, v drugi vrstici odštejemo 2, v tretji vrstici odštejemo 2, v četrti vrstici odštejemo 3 in zadnji odštejemo 4.

  • Matrika krožne poti po redukciji po vrsticah:
20 30 10 11
15 16 4 2
3 5 2 4
19 6 18 3
16 4 7 16


  • Matrika krožne poti po redukciji po stolpcih:
10 20 0 1
13 14 2 0
1 3 0 2
16 3 15 0
12 0 3 12


  • Sedaj v vsakem stolpcu odštejemo najmanjše število.
  • Prvemu stolpcu odštejemo 1, drugemu 0, tretjemu 3, četrtemu 0 in zadnjemu stolpcu

odštejemo 0.

10 17 0 1
12 11 2 0
0 3 0 2
15 3 12 0
11 0 0 12


  • Tako dobimo novo matriko s spodnjo mejo: sm1 = 10 + 2 + 2 + 2 + 3 + 4 + 1 + 0 + 3 + 0 + 0 = 25


2. Vozlišče:

  • Iz prvega vozlišča gremo v drugo vozlišče. Ker iz prvega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v prvi vrstici postavimo na neskončno; in ker ne smemo priti v drugo vozlišče iz nobenega drugega vozlišča, vse vrednosti v drugem stolpcu postavimo na neskončno.
  • (2,1) smo postavili na ∞, da smo preprečili cikel.
  • Dobimo spodnjo matriko:
11 2 0
0 0 2
15 12 0
11 0 12


  • Dobimo novo matriko s spodnjo mejo: sm12 = 25 + 10 = 35.
  • 10 smo dobili iz prvotne vrstice, povezava (1,2).


3. Vozlišče:

  • Iz prvega vozlišča gremo v tretje vozlišče. Ker iz prvega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v prvi vrstici postavimo na neskončno; in ker ne smemo priti v tretje vozlišče iz nobenega drugega vozlišča, vse vrednosti v tretjem stolpcu postavimo na neskončno.
  • (3,1) smo postavili na ∞, da smo preprečili cikel.
  • Dobimo spodnjo matriko:
12 2 0
3 0 2
15 3 0
11 0 12


  • Uporabimo redukcijo na prvem stolpcu: odštejemo 11.
1 2 0
3 0 2
4 3 0
0 0 12


  • Dobimo novo matriko s spodnjo mejo:
  • sm13 = 25 + 17 + 11 = 53.
  • 17 smo dobili iz prvotne vrstice, povezava (1,3); 11 pa smo dobili z redukcijo.


4. Vozlišče:

  • Iz prvega vozlišča gremo v četrto vozlišče. Ker iz prvega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v prvi vrstici postavimo na neskončno.
  • In ker ne smemo priti v četrto vozlišče iz nobenega drugega vozlišča, vse vrednosti v drugem stolpcu postavimo na neskončno.
  • (4,1) smo postavili na ∞, da smo preprečili cikel.
  • Dobimo spodnjo matriko:
12 11 0
0 3 2
3 12 0
11 0 0


  • Dobimo novo matriko s spodnjo mejo: sm14 = 25 + 0 = 25.
  • 0 je povezava (1,4); povezave jemljemo iz prvotne reducirane matrike.


5. Vozlišče:

  • Iz prvega vozlišča gremo v peto vozlišče. Ker iz prvega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v prvi vrstici postavimo na neskončno.
  • In ker ne smemo priti v peto vozlišče iz nobenega drugega vozlišča, vse vrednosti v drugem stolpcu postavimo na neskončno.
  • (5,1) smo postavili na ∞, da smo preprečili cikel.
  • Dobimo spodnjo matriko:
12 11 2
0 3 0
15 3 12
0 0 12


  • Zopet uporabimo redukcijo na matriki.
  • Najprej jo uporabimo na vrsticah.
    • Drugi vrstici odštejemo 2, četrti vrstici odštejemo 3.
  • Nato pogledamo še vrstice.
10 9 0
0 3 0
12 0 9
0 0 12


  • Dobimo novo matriko s spodnjo mejo: sm15 = 25 + 2 + 3 + 1 = 31
  • 1 je povezava (1,5). Povezave jemljemo iz prvotne reducirane matrike.
  • 2 in 3 pa dobimo s pomočjo redukcije matrike.


  • Ko smo izračunali vse povezave s prvim vozliščem, jih med seboj primerjamo. Opazimo, da je najbolj optimalna povezava do četrtega vozlišča.
  • Na spodnji matriki nadaljujemo zgornji postopek.


2. Vozlišče:

  • Iz četrtega vozlišča gremo v drugo vozlišče. Ker iz četrtega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v čertri vrstici postavimo na neskončno.
  • In ker ne smemo priti v drugo vozlišče iz nobenega drugega vozlišča, vse vrednosti v drugem stolpcu postavimo na neskončno.
  • (2,1) smo postavili na ∞, da smo preprečili cikel.
11 0
0 2
11 0


  • Dobimo novo matriko s spodnjo mejo: sm142 = 25 + 3 = 28.
  • 3 je povezava (4,2). Povezave jemljemo iz prvotne reducirane matrike.


3. Vozlišče:

  • Iz četrtega vozlišča gremo v tretje vozlišče. Ker iz četrtega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v četrti vrstici postavimo na neskončno.
  • In ker ne smemo priti v tretje vozlišče iz nobenega drugega vozlišča, vse vrednosti v tretjem stolpcu postavimo na neskončno.
  • (3,4) smo postavili na ∞, da smo preprečili cikel.
  • Dobimo spodnjo matriko:
12 0
3 2
11 0


  • Dobimo novo matriko s spodnjo mejo: sm143 = 25 + 11 + 2 + 12 = 50.
  • 12 je povezava (4,3). Povezave jemljemo iz prvotne reducirane matrike.


5. Vozlišče:

  • Iz četrtega vozlišča gremo v peto vozlišče. Ker iz četrtega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v četrti vrstici postavimo na neskončno.
  • In ker ne smemo priti v peto vozlišče iz nobenega drugega vozlišča, vse vrednosti v petem stolpcu postavimo na neskončno.
  • (5,4) smo postavili na ∞, da smo preprečili cikel.
  • Dobimo spodnjo matriko:
12 11
0 3
0 0


  • Dobimo novo matriko s spodnjo mejo: sm145 = 25 + 11 + 0 = 50.
  • 0 je povezava (4,5). Povezave jemljemo iz prvotne reducirane matrike.
  • Ko smo izračunali vse povezave s četrtim vozliščem, jih med seboj primerjamo. Opazimo, da je najbolj optimalna povezava do drugega vozlišča.
  • Na spodnji matriki nadaljujemo zgornji postopek.


3. Vozlišče:

  • Iz drugega vozlišča gremo v tretje vozlišče. Ker iz drugega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v drugi vrstici postavimo na neskončno.
  • In ker ne smemo priti v tretje vozlišče iz nobenega drugega vozlišča, vse vrednosti v tretjem stolpcu postavimo na neskončno.
  • (2,1) smo postavili na ∞, da smo preprečili cikel
2
11


Matrika s spodnjo mejo: sm1423 = 28 + 2 + 11 + 11 = 52.

  • 11 je povezava (2,3). Povezave jemljemo iz prvotne reducirane matrike


5. Vozlišče:

  • Iz drugega vozlišča gremo v peto vozlišče. Ker iz drugega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v drugi vrstici postavimo na neskončno.
  • In ker ne smemo priti v peto vozlišče iz nobenega drugega vozlišča, vse vrednosti v petem stolpcu postavimo na neskončno.
  • (5,2) smo postavili na ∞, da smo preprečili cikel.
  • Dobimo spodnjo matriko:
0
0


  • Matrika s spodnjo mejo: sm1425 = 28 + 0 = 28.
  • 0 je povezava (2,5). Povezave jemljemo iz prvotne reducirane matrike.
  • Ko smo izračunali vse povezave z drugim vozliščem, jih med seboj primerjamo. Opazimo, da je najbolj optimalna povezava do petega vozlišča.
  • Na spodnji matriki nadaljujemo zgornji postopek.


3. Vozlišče:

Iz petega vozlišča gremo v tretje vozlišče. Ker iz petega vozlišča ne smemo iti v nobeno drugo vozlišče, vse ostale vrednosti v peti vrstici postavimo na neskončno. In ker ne smemo priti v tretje vozlišče iz nobenega drugega vozlišča, vse vrednosti v tretjem stolpcu postavimo na neskončno. (3,1) smo postavili na ∞, da smo preprečili cikel.


  • Matrika s spodnjo mejo: sm14253 = 28 + 0 = 28.
  • 0 je povezava (5,3). Povezave jemljemo iz prvotne reducirane matrike
  • Končna optimalna rešitev je 28.
  • Možna povezava pa je : 1 – 4 – 2 – 5 – 3 – 1.
  • Končna matrika krožne poti:
Osebna orodja