Hálózatok

5. Van itt néhány vektor, és végezzük el velük a következő műveleteket.

\( A=\begin{pmatrix} 1 & 3 & 1 \\ 2 & 0 & 4 \\ 3 & 1 & 7 \end{pmatrix}  \quad \underline{b}=\begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix}  \quad C=\begin{pmatrix} 2 & 1 & 7 \\ 3 & 1 & 8  \end{pmatrix} \)

\( \underline{d}=\begin{pmatrix} 1 \\ 1 \\ 4 \end{pmatrix} \quad E=< 2 \; 5 \; 7 > \)

a) \( A \cdot \underline{b} \)

b) \( A \cdot C \)

c) \( A \cdot C^* \)

d) \( \underline{b^*} \cdot \underline{d} \)

e) \( \underline{b} \cdot \underline{d^*} \)

f) \( A^2 \)

Megnézem, hogyan kell megoldani


4.  Legyen $\underline{a}$, $\underline{b}$, $\underline{c} \in R^n$ vektorok. Az alábbi állítások közül melyik igaz?

a) Ha $\underline{a}, \underline{b}, \underline{c}$ lineárisan független, akkor $\underline{a}+\underline{b}+\underline{c}$, $\underline{b}+\underline{c}$, $\underline{c}$ is lineárisan független.

b) Ha $\underline{a}+\underline{b}+\underline{c}$, $\underline{b}+\underline{c}$, $\underline{c}$ generátor-rendszer, akkor $\underline{a}$, $\underline{b}$, $\underline{c}$ is az.

c) Ha $\underline{a}, \underline{b}, \underline{c}$ lineárisan független, akkor $\underline{a}-\underline{b}$, $\underline{b}-\underline{c}$, $\underline{c}-\underline{a}$ is lineárisan független.

d) Ha $\underline{a}, \underline{b}, \underline{c}$ lineárisan független, akkor $\underline{a}-\underline{b}$, $\underline{b}-\underline{c}$ is lineárisan független.

e) Ha $\underline{a}-\underline{b}$, $\underline{b}-\underline{c}$ lineárisan független, akkor $\underline{a}$, $\underline{b}$, $\underline{c}$ is lineárisan független.

f) Ha $\underline{a}-\underline{b}$, $\underline{b}-\underline{c}$ generátor-rendszer, akkor $\underline{a}$, $\underline{b}$, $\underline{c}$ is az.

Megnézem, hogyan kell megoldani


10. Az $e$ egyenesről tudjuk, hogy merőlegesen döfi az $x+2y+3z=6$ egyenletű síkot az $(1;1;1)$ pontban, az $f$ egyenesről pedig, hogy átmegy az $(5;2;-1)$ ponton és a $(13;4;-5)$ ponton. Döntsük el, hogy $e$-nek és $f$-nek van-e közös pontja.

Megnézem, hogyan kell megoldani


3.  Ellenőrizzük, hogy az alábbi leképezések lineáris leképezések-e, ha igen adjuk meg a képteret, a magteret és a transzformáció mátrixát.

a) \( R^2 \to R^2 \qquad \varphi\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} a+1 \\ b \end{pmatrix} \qquad a,b \in R \)

b) \( R^2 \to R^2 \qquad \varphi\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} a-b \\ 0 \end{pmatrix} \qquad a,b \in R \)

c) \( R^3 \to R^3 \qquad \varphi\begin{pmatrix} a \\ b \\ c \end{pmatrix} = \begin{pmatrix} a+b \\ a\cdot b \\ c \end{pmatrix} \qquad a,b,c \in R \)

Megnézem, hogyan kell megoldani


12. Vannak itt ezek a mátrixok, döntsük el, hogy milyen definitek.

\( A=\begin{pmatrix} 2 & 3 & 1 \\ 1 & 2 & 2 \\ 2 & 1 & 4 \end{pmatrix} \quad B=\begin{pmatrix} -2 & 3 & 1 \\ 1 & -4 & 2 \\ 1 & -6 & 1 \end{pmatrix} \)

\( C=\begin{pmatrix} 2 & 3 & 1 \\ 1 & 1 & 2 \\ 1 & 1 & 1 \end{pmatrix} \quad D=\begin{pmatrix} 1 & 1 & 1 \\ 2 & 1 & 2 \\ 1 & 0 & 1 \end{pmatrix} \quad \)

Megnézem, hogyan kell megoldani


22. Döntsük el, hogy konvergensek-e a következő végtelen sorok.

$$ \sum_{n=2}^{\infty} (-1)^n \frac{\ln{n}}{n-\ln{n}} \qquad \sum_{n=1}^{\infty} \frac{ (-100)^n}{n!} \qquad \sum_{n=1}^{\infty} (-1)^n \left(\frac{\ln{n}}{\ln{n^2}}\right)^n $$

Megnézem, hogyan kell megoldani

A témakör tartalma

Itt röviden és szuper-érthetően megnézheted, mik azok a hálózati folyamok, hogyan lehet megtalálni a maximális folyamot, hogyan működik a Ford-Fulkerson algoritmus, mi az a javító gráf és hogyan kell használni. Hogyan lehet megtalálni a maximális folyamot és a minimális vágást. Megnézzük a Ford-Fulkerson tételt. Készítettünk egy kis összefoglalót a hálózati folyamokról, a minimális vágásról és maximális folyamról, a Ford-Fulkerson algoritmus működéséről és a javító gráfok használatáról. Végezetül pedig elmeséljük, hogy mi az a kritikus út, mi a CPM módszer és a PERT módszer. Példák kritikus út keresésére, legkorábbi és legkésőbbi bekövetkezések, tartalékidő.



Hálózati folyamok, Ford-Fulkerson algoritmus

Itt ez a vízvezeték hálózat, amin keresztül víz áramlik S-ből T-be.

A zárójelben lévő számok a csövek kapacitását jelentik.

Vagyis azt jelentik, hogy mennyi víz képes rajtuk átfolyni.

A zárójel előtti szám pedig azt mondja meg, hogy éppen mennyi víz folyik most a csőben.

Hát, vannak itt még kihasználatlan részek.

A kérdés az, hogyan tudnánk még egy kicsit növelni az átfolyó víz mennyiségét.

Kell hozzá egy kis trükk.

Ezt a csövet itt elzárjuk.

Most rosszabb…

Viszont szabaddá tettük a jobb oldali ágat.

Ahol le tudunk engedni 10 egység vizet.

És így az eddigi 10 helyett most már 15 egység víz folyik S-ből T-be.

Remek hír, de két kínzó kérdés merül föl.

Az egyik: Hogyan lehet rájönni ezekre a javítási lehetőségekre az ennél bonyolultabb esetekben?

A másik: Honnan lehetünk biztosak benne, hogy a legjobb megoldást találtuk meg?

Hát, ezekre a kérdésekre fogunk most válaszolni.

Itt van egy másik hálózat…

ez már egy kicsit bonyolultabb.

És a csőrendszert egy irányított gráffal fogjuk jelölni.

Úgy tűnik, hogy 5+2=7 egység víz indul útnak S-ből…

és 0+3+4=7 egység is érkezik meg.

Próbáljunk meg ezen javítani.

A javításhoz egy úgynevezett javító gráfot fogunk használni.

Nézzük, hogyan készül a javító gráf.

Itt van ez az él…

szabad kapacitással.

 Ezt az élt így tesszük be a javító gráfba.

A zöld nyíl azt jelenti, hogy ennyivel tudjuk még a csőben növelni a vizet.

A piros nyíl pedig azt mutatja, hogy jelenleg mennyi folyik át, de szaggatott vonallal, és visszafelé mutat.

A zöld nyíl túl sok magyarázatot nem igényel.

De mire jó a piros nyíl szaggatott vonallal és visszafelé?

A piros nyíl egy zseniális terv része. És hamarosan az is kiderül, hogy mi ez a terv.

Most menjünk szépen tovább.

Ennek az élnek a szabad kapacitása       .

Berakjuk ezt is a javító gráfba szépen.

A zöld nyíl azt jelenti, hogy 6-tal tudjuk még a csőben növelni a vizet.

A piros nyíl pedig azt mutatja, hogy jelenleg 2 egység folyik át ezen a csövön,

de már megint ez a rejtélyes szaggatott vonal, és megint visszafelé.

Itt van aztán az A-ból B-be vezető cső.

Ez fullon van, úgyhogy a javító gráfban ide nem rakunk zöld nyilat.

De a rejtélyes piros nyíl itt is kell.

Mivel jelenleg 2 egység víz folyik át a csövön, ezért így:

Most lássuk, mi a helyzet az A-ból C-be vezető csővel.

Ez a cső teljesen üres.

A zöld nyíl tehát megegyezik a cső teljes kapacitásával…

Piros nyíl pedig itt nincs.

Ugyanez a helyzet az A-ból D-be vezető csőnél is.

És szépen lépésről lépésre elkészítjük a javító gráfot.

Elkészült a javító gráf.

A javító gráf megmutatja nekünk, hogy milyen útvonalon tudjuk növelni a meglévő folyamot.

Ezen az útvonalon például tudjuk.

Mégpedig 3 egységgel.

De van még itt más javító út is…

Ezen az útvonalon a szűk keresztmetszet a 3…

Így aztán ennyivel tudunk javítani.

Hát, eddig megvolnánk.

A kérdés, hogy tudunk-e még ezen is javítani.

Készítsük el az ehhez tartozó új javító gráfot, és nézzük meg.

És most nézzük, van-e még itt javító út.

Olyan már nincs, ami csupa zöld éleken keresztül vezet S-ből T-be.

De itt az ideje felfedni a titkos terv részleteit.

Létezik ugyanis még egy javító út…

ami piros élen is halad.

A szűk keresztmetszet ezúttal 2, vagyis 2 egység vizet tudunk még ezen az útvonalon szállítani.

A piros élen történő szállítás pedig azt jelenti…

hogy ezt a csövet elzárjuk.

A bal oldali ágról másfelé tereljük a vizet…

és így a jobb oldali ágon tudjuk növelni 2-vel.

De az egészben az a legjobb, hogy nekünk ezen nem kell gondolkodnunk.

Minden ki fog jönni szépen magától.

Nem kell mást tennünk, csak egyszerűen alkalmazni a hálózatra a javítást.

Ahol zöld élen mentünk a javító úton, ott hozzáadunk…

ahol piros élen, ott levonunk.

Most újra elkészítjük a javító gráfot a szokásos módon.

És úgy tűnik, hogy ez már tovább nem javítható.

Azért nem, mert nincsen a javító gráfban S-ből T-be vezető út.

Szerencsére létezik egy tétel, ami végérvényesen el tudja dönteni, hogy létezik-e még további javító út vagy sem.

Ezt a tételt Ford-Fulkerson tételnek nevezzük, és ezzel fogjuk folytatni...


A maximális folyam és a minimális vágás, Ford-Fulkerson tétel

Van itt ez a hálózat az élek kapacitásaival…

és egy hálózatban futó folyammal.

Ebből a folyamból kiindulva keressük meg az S-ből T-be vezető maximális folyamot.

A módszert, amit a maximális folyam megkeresésére fogunk használni, Ford-Fulkerson algoritmusnak hívják.

Az algoritmus lényege pedig az a javító gráf, amit az eredeti hálózat alapján készítünk el.

A javító gráf megmutatja nekünk, hogy milyen útvonalon tudjuk növelni a meglévő folyamot.

A szűk keresztmetszet pedig 2, vagyis maximum 2-vel tudunk növelni.

Ahol zöld élen mentünk a javító úton, ott hozzáadunk…

ahol piros élen, ott levonunk.

Most újra elkészítjük a javító gráfot, hátha még mindig lehet a folyamon javítani.

De, nem úgy néz ki.

Itt nem jutunk át…

Ezeknél a csúcsoknál ugyanis a javító út elakad.

A piros csúcsokból most már lehetetlen átjutni…

a sárga csúcsokba.

A problémát egy kicsit precízebben a Ford-Fulkerson tétel fogalmazza meg.

Ehhez be kell vezetnünk egy új fogalmat, amit vágásnak fogunk hívni.

Már jön is.

A hálózat csúcsainak halmazát V(G)-vel jelöljük.

Legyen X a V(G)-nek egy olyan részhalmaza, ami S-t tartalmazza.

A többi csúcs pedig, amik nincsenek benne az X-ben a V(G)\X halmazt alkotják.

Az X és a V(G)\X halmazok közötti éleket vágásnak nevezzük.

Vágás:

Legyen X a V(G)-nek egy olyan részhalmaza, ami S-t tartalmazza.

Ekkor az X-ből a V(G)\X-be vezető éleket (S,T) vágásnak nevezzük.

A vágás szemléletes jelentése ez…

elvág minden utat S és T között.

A vágás kapacitása pedig azt mondja meg, hogy hány sávot robbantottak föl a terroristák.

Most éppen egy 10 sávos utat és két 4 sávos utat robbantottak föl.

Tehát a vágás kapacitása 10+4+4=18.

Vágás kapacitása:

Egy (S,T) vágás kapacitása, a vágásban szereplő élek kapacitásainak összege.

Vagy éppen ennek a másik vágásnak itt…

ennek a kapacitása 11+4+4=19.

És ennek pedig…

Hát, ennek még több: 4+16=20.

Maximális folyam, minimális vágás, Ford-Fulkerson algoritmus

Vagyis keressük meg azt a vágást, amihez a lehető legkevesebb sávot kell felrobbantani, de mégis teljesen megszűnik az összeköttetés S és T között.

Ezt a vágást minimális vágásnak nevezzük.

Lássuk, mekkora a kapacitása például ennek a vágásnak itt.

Na, ez éppen egy trükkös eset.

Az egyik él ugyanis visszafelé megy.

Amikor egy vágás kapacitását számoljuk, csak az X-ből V(G)\X-be vezető élek számítanak…

ha van olyan él, ami V(G)\X-ből X-be vezet, az nem.

Így aztán ennek a vágásnak a kapacitása 10+9+5=24.

Ami biztosan nem minimális, mert volt már az előbb olyan vágás is, aminek a kapacitása 18.

Ez volt az.

Kérdés: van-e még ennél is kisebb?

És itt kerül képbe a Ford-Fulkerson tétel.

Ha találunk egy tetszőleges folyamot a hálózatban, akkor a folyam értéke egészen biztosan kisebb bármely vágás kapacitásánál.

És fordítva, egy tetszőleges vágás kapacitása biztosan nagyobb, mint bármely folyam értéke.

A Ford-Fulkerson tétel azt mondja, hogy a maximális folyam mindig megegyezik a minimális vágással.

Lássuk, hogyan használhatnánk ezt a tételt a mi kis hálózatunkra.

Az biztos, hogy találtunk egy olyan vágást, aminek a kapacitása 18.

És az is biztos, hogy van egy olyan folyam, aminek az értéke 18.

Hiszen 18 egység indul S-ből…

és annyi is érkezik T-be.

Mivel van 18 kapacitású vágás, nem lehet 18-nál nagyobb értékű folyam.

Vagyis a maximális folyam értéke 18.

És mivel van 18 értékű folyam, nem lehet 18-nál kisebb kapacitású vágás.

Tehát a minimális vágás kapacitása 18.


Egy kis összefoglaló hálózati folyamokból

Itt az ideje, hogy egy kicsit precízebbé tegyük a hálózatokkal kapcsolatos fogalmakat.

Legyen G egy irányított gráf és értelmezzünk a gráf élein egy  függvényt, ami minden élhez hozzárendeli a nem negatív számot, amit az él kapacitásának nevezünk.

Van továbbá két kitüntetett pont a gráfban, S (source=forrás) és T (target=cél).

Ekkor a (G, S, T, c) egy hálózat.

A hálózatban folyamnak nevezünk egy olyan  függvényt, amire teljesül, hogy bármely e élre  és bármely T-től és S-től különböző V csúcsra

Vagyis egy csúcsba befolyó mennyiség…

mindig megegyezik a csúcsból kifolyóval.

A két kivétel S és T. S-ből csak kifelé folyik…

T-be csak befelé.

Egy folyam értékének az

számot nevezzük.

Most éppen…

Végül még egy fontos definíció: a vágás.

Legyen X a V(G)-nek egy olyan részhalmaza, ami S-t tartalmazza.

Ekkor az X-ből a V(G)\X-be vezető éleket (S,T) vágásnak nevezzük.

Egy (S,T) vágás kapacitása, a vágásban szereplő élek kapacitásainak összege.

A Ford-Fulkerson tétel azt mondja ki, hogy egy hálózatban a maximális folyam mindig megegyezik a minimális vágással.

És most pedig lássunk egy mindent összefoglaló példát.

Itt van ez a hálózat, benne egy folyammal.

Készítsük el a javító gráfot.

Most nézzük, lehet-e még javítani…

Úgy tűnik, igen.

Ezen az ágon a szűk keresztmetszet 1…

és a másik ágon hozzájön még plusz 3.

Nézzük, tudjuk-e ezt még javítani…

Megint elkészítjük a javító gráfot.

És úgy tűnik, már nem lehet tovább javítani.

Találtunk egy minimális vágást.

Ennek a vágásnak a kapacitása 14.

Ez azt jelenti, hogy minden folyam értéke maximum 14 lehet.

Ennek a folyamnak az értéke szintén 14.

Ez azt jelenti, hogy minden vágás kapacitása minimum 14 kell, hogy legyen.

A minimális folyam értéke és a maximális vágás kapacitása tehát 14.


FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

CPM és PERT, kritikus út