CATEGORII DOCUMENTE |
Astronomie | Biofizica | Biologie | Botanica | Carti | Chimie | Copii |
Educatie civica | Fabule ghicitori | Fizica | Gramatica | Joc | Literatura romana | Logica |
Matematica | Poezii | Psihologie psihiatrie | Sociologie |
TEORIA PROBABILITATILOR
Teoria probabilitatilor este teoria fenomenelor aleatoare (intamplatoare).
1. Definitia clasica a probabilitatii
Camp finit de evenimente
1.1 Experienta, proba,eveniment
Definitie. Se numeste experienta in teoria probabilitatilor, orice act care poate fi repetat in conditii date.
Definitie. Probele sunt rezultatele posibile ale unei experiente.
Experientele pot avea un numar finit sau infinit de probe.
Definitie. Se numeste eveniment, orice situatie legata de o experienta, despre care putem spune ca s-a produs sau nu, dupa efectuarea experientei.
Evenimentele aleatoare se pot nota cu A, B,
Csau A
Definitie. Se numeste experienta aleatoare orice experienta care fiind repetata in aceleasi conditii conduce la rezultate diferite.
Probele unei experiente se mai numesc si cazuri posibile ale experientei.
Prin eveniment se intelege realizarea sau nerealizarea unei probe (de exemplu, obtinerea fetei cu numarul 3 la aruncarea unui zar constitue un eveniment).
Definitie. Se numeste eveniment aleator, un rezultat posibil al unei experiente aleatoare.
Exemplu
Definitie. Evenimentul care poate fi realizat printr o singura proba, se numeste eveniment elementar.
Definitie. Evenimentul care poate fi realizat prin doua sau mai multe probe se numeste eveniment compus.
Definitie. Se numeste spatiu de selectie, multimea evenimentelor elementare asociate experientei respective.
Definitie. Se numeste eveniment sigur, notat cu
Definitie. Se numeste eveniment imposibil, notat cu
Exemple.
Definitie. Se numeste evenimentul contrar evenimentului
Exemple.
Evenimentul sigur consta in nerealizarea evenimentului imposibil si reciproc.
Definitie. Doua evenimente se numesc compatibile daca se pot realiza simultan, ceea ce inseamna exista cel putin un rezultat care favorizeaza pe fiecare din aceste evenimente. In caz contrar se numesc incompatibile.
Exemplu.
Observatie. Evenimentele contrare sunt incompatibile.
In general, un numar finit de evenimente
Observatie. Daca evenimentele
Exemplu.
Definitie. Se spune ca evenimentul
Se noteaza
Exemple. Observatie. Daca
Orice eveniment implica evenimentul sigur.
Evenimentul imposibil implica orice eveniment.
Evenimentele pot fi reprezentate ca multimi, ceea ce inseamna ca atunci cand ne fixam atentia asupra unui eveniment, este vorba despre o parte din multimea probelor experientei.
Considerand experienta aruncarii unui zar si notand cu A evenimentul care consta in aparitia fetelor cu 1,2 sau 5 puncte, identificam acest eveniment cu multimea probelor care il realizeaza :
Evenimentul
1.2. Operatii cu evenimente.
Reuniunea. Fiind date doua evenimente
Intersecta. Fiind date doua evenimente
Observatie.
Doua
evenimente
Observatie. Operatiile de reuniune si intersectie se extind pentru orice numar finit de evenimente.
Fiind
date n evenimente
Diferenta. Numim diferenta evenimentelor
Fie
.........................
Un camp de evenimente contine
Definitie. Se numeste camp finit de evenimente, perechea
1)
2)
Daca
3)
Observatie. Un camp finit de evenimente
este format din multimea tuturor submultimilor lui
Din definitia de mai sus deriva cateva proprietati
ale campului de evenimente
1)
2)
Fiind date
3) Daca
4) Fiind date
5) Fiind date
6)
7)
8) Fiind date
9) Fiind date
10) Fiind date
Camp de probabilitate finit
Fie o experientacu n evenimente egal posibile
(evenimentele considerate au aceeasi sansa de a se realiza) si
Definitie. Se numeste probabilitatea evenimentului
Numarul
2)
3) Daca
4)
5)
Generalizare (formula lui Poincar sau principiul includerii-excluderii):
6)
Daca
Observatie. Daca
Exemple.
1.O urna contine 5 bile albe si 10 bile negre. Care este probabilitatea ca sa extragem o bila alba ? Dar o bila neagra ?
2. Se arunca doua zaruri. Care ste probabilitatea ca suma punctelor obtinute sa fie egala cu 8 ?
3. Daca se arunca de patru ori un zar, care este probabilitatea sa obtinem o data fata cu sase puncte ?
4. Daca se arunca de 24 de ori o pereche de zaruri, care este probabilitatea sa apara o dubla de sase puncte ?
Daca A si B sunt multimi finite, numarul elementelor produsului cartezian AxB este egal cu produsul dintre numarul elementelor lui A si numarul elementelor lui B. Se scrie card(AxB)=card(A).card(B).
Prin inductie
In cazul de mai sus E=[1,2,3,4,5,6], ca urmare a
celor 4 aruncari se obtine un sistem ordonat de 4 numere din E, adica un
element al produsului cartezian ExExExE al carui numar de elemente este
6.6.6.6=
Intr-o serie de aruncari nu apare niciodata fata
sase daca de fiecare data se obtine un numar din multimea [1,2,3,4,5]. Numarul
acestor rezultuate este
Daca notam cu A evenimentul care consta in
aparitia cel putin o data a fetei cu sase puncte, atunci avem probabilitatea lui A
data de
Notam cu B evenimentul ca in 24 de aruncari sa apara cel putin o data dubla de sase puncte.
In cazul celor 24 de aruncari avem 36 de cazuri posibile, deoarece fiecare din cele sase fete ale primului zar se pot combina cu oricare din cele sase fete ale celui de-al doilea zar, deci in total36.
In cele 24 de aruncari avem
La fiecare aruncare a celor doua zaruri sunt 35 de
cazuri nefavorabile, ceea ce inseamna
Probabilitatea ca aruncand de 24 de ori sa nu apara
dubla este
2. Definitia axiomatica a probabilitatii
Definitia clasica a probabilitatii poate fi
acceptata numai in cazul cand numarul cazurilor posibile este finit. Daca
numarul evenimentelor elementare este infinit (Card
Definitie. Fiind data o multime
2) Pentru orice
3) Daca
De aici se desprind urmatoarele consecinte :
Daca
Daca
Observatie. Proprietatile 1-10 ale campului finit de evenimente sunt valabile si in cazul campului borelian.
Definitie. Fiind dat un
1)
2) Daca
3)
Definitie. Tripletul
Observatie.Proprietatile 1-6 de la definitia clasica a probabilitatii sunt valabile si in plus avem :
2)
Daca
3)
Daca
Probabilitati conditionate
Sa consideram experiensa aruncarii aruncarii uni zar si sa notam cu A evenimentul care constam in aparitia uneia din fetele 1,2,3, iar cu B evenimentul care consta in aparitia uneia din fetele 2,3,4.
P(A)=P(B)=3/6=1/2
Ne propunem sa evaluam probabilitatea evenimentului B in ipoteza ca A s-a
realizat. Aceasta probabilitate o numim probabilitatea evenimentului B
conditionata de A si se noteaza cu
In ipoteza ca A s-a realizat, inseamna ca a aparut una din fetele 1,2,3; din aceste cazuri numai doua sunt favorabile evenimentului B: 2,3.
Rezulta P(B)=2/3.
Fie o experienta cu un numar finit de cazuri egal posibile.
Notam: n - numarul cazurilor egal posibile ale experientei.
m - numarul cazurilor favorabile evenimentului A.
p - numarul cazurilor favorabile evenimentului B.
q - numarul cazurilor favorabile
evenimentului
Atunci
Dar
Definitie. Probabilitatea
evenimentului
Definitie. Doua evenimente A si B sunt independente daca fiecare dintre ele nu isi modifica probabilitatea in functie de realizarea sau nerealizarea celuilalt, ceea ce inseamna ca
In practica notiunea de independenta comporta doua aspece.
In unele situatii nu este cunoscuta si ea trebuie dovedita.
Exemplu.Se arunca un zar o singura data. Notam:
A aparitia uneia din fetele cu 1,2,3 puncte.
B aparitia uneia din fetele cu 2,3,4,5 puncte.
Cele doua evenimente sunt independente ?
P(A)=1/2 , P(B)=4/6=2/3
P(A si B)=2/6=1/3
P(A si B)=1/3=1/2.2/3=P(A)P(B)
Evenimentele A si B sunt independente.
In cele mai multe cazuri, independenta este necunoscuta, ea reiesind din context.
Exemplu.Sa presupunem ca se arunca doua zaruri, unul de culoare alba, iar celalalt de culoare neagra. Consideram evenimentele:
A apariia fetei cu 4 puncte pe zarul alb;
B aparitia fetei cu 6 puncte pe zarul negru.
Evenimentele A si B sunt independente.
Fie urnele U
Notam cu A evenimentul care consta in extragerea unei bile albe din prima urna, iar cu B evenimentul care consta in extragerea unei bile negre din a doua urna. Cele doua evenimente sunt independente.
Tema de casa nr. 9
O urna contine 10 bile albe si 6 bile negre. Din aceasta urna se extrag 2 bile, nepunandu-se inapoi prima bila extrasa.
Se cere:
a) probabilitatea ca cele doua bile sa fie albe;
b) probabilitatea ca cele doua bile sa fie negre;
c) probabilitatea ca prima bila sa fie alba si a doua sa fie neagra;
d) probabilitatea ca prima bila sa fie neagra si a doua sa fie alba;
e) probabilitatea ca bilele sa fie de aceeasi culoare;
f) probabilitatea ca bilele sa fie de culori diferite.
Intr-un lot de 100 de piese 5 sunt diferite. Se aleg la intamplare 5 piese din lot. Care este probabilitatea ca printre piesele alese cel putin una sa fie diferita?
Intr-un container se afla 25 de piese bune si 5 defecte. In alt container se afla 25 de piese bune si 4 defecte. Din fiecare container se ia cate o piesa.
Care este probabilitatea ca:
a) obtinerii a doua piese bune?
b) obtinerii a doua piese defecte?
c) obtinerii cel putin unei piese bune?
d) Obtinerii a doua piese de acelasi tip (defecte sau bune)?
O urna contine 3 bile albe si 4 bile negre. Din aceasta urna se extrag succesiv doua bile (fara intoarcerea bilei extrase).
Consideram evenimentele:
A: prima bila extrasa este alba; B: a doua bila extrasa este alba.
Care este probabilitatea ca a doua bila extrasa sa fie alba daca prima este alba?
se arunca un zar o singura data si se considera evenimentele:
A: aparitia uneia din fetele 1, 2, 3. B: aparitia uneia din fetele 2, 3, 4, 5.
Sunt aceste evenimente independente?
Da.
Cursul nr. 10 Matematici speciale
3. Scheme si formule clasice de probabilitate.
Schema lui Bernoulli
In urma efectuarii unei experiente poate sa apara evenimentul cu probabilitatea p sau contrariul sau cu probabilitatea q=1-p.
Se repeta experienta de n ori in conditii
identice. Probabilitatea ca in cele n experiente evenimentul
Exemplu. Se arunca o pereche de zaruri de sase ori. Care este probabilitatea ca exact de patru ori sa obtinem un total de sapte puncte ?
Exemplu. Se trunca o moneda de 6 ori. Care este probabilitatea sa apara de 4 ori prima fata si de 2 ori a doua fata ?
Schema lui Bernoulli cu mai multe Stari
In urma efectuarii unei experiente pot aparea
evenimentele
Se repeta experienta de n ori.
Probabilitatea ca in cele n experiente evenimentele
Exemplu. Se arunca un zar de 5 ori. Care este probabilitatea ca de doua ori sa obtinem fata cu un punct, de doua ori fata cu doua puncte si o data nici una din aceste doua fete ?
Exemplu. Probabilitatile ca diametrul unei piese de masina sa fie intre limite mai mici, respectiv mai mari decat cele admisibile sunt 0.05 si 0.10, iar probabilitatea ca diametrul unei piese sa fie intre limite admisibile este de 0.85.
Din intreg lotul se extrag la intamplare 100 piese. Care este probabilitatea intre piesele alese, 5 sa fie cu diametrul mai mic, iar 5 cu diametrul mai mare decat cel admis ?
Schema lui Poisson
Se fac n experiente
independente. In urma experientei de rang k poate sa apara evenimentul
Probabilitatea ca in cele n
experiente evenimentul
unde
Exemplu. Se considera
urnele :
Care este probabilitatea ca lund la intamplare cate o bila din fiecare urna sa obtinem 2 bile albe si una neagra ?
Exemplu. Se experimenteaza 4 prototipuri de aparate, cate unul din fiecare prototip. Probabilitatea ca un prototip sa corespunda este 0.8, 0.7, 0.9 si respectiv 0.85.
Se cere probabilitatea ca toate cele 4 aparate experimentate sa corespunda.
Schema bilei nerevenite
O urna contine a
bile albe si b bile negre. Din
aceasta urna se se extrag n bile fara a pune bila extrasa inapoi in urna,
Probabilitatea ca
Consideram o urna care contine biele de m culori:
Exemplu. Intr-un lot de 100 piese, 6 piese au defecte remediabile, 4 piese sunt rebuturi, iar restul sunt piese bune. Din acest lot au fost luate la intamplare 10 piese. Care este probabilitatea ca din aceste piese 7 sa fie bune, 2 sa aiba defecte remediabile si una sa fie rebut.
Formula inmultirii probabilitatilor
Teorema. Daca
Demonstratie. Folosind probabilitatile conditionate, avem:
pe care inmultindu-le membru cu membru se obtine formula de mai sus.
Exemplu. O urna contine 4 bile albe si 6 bile negre. Se cere probabilitatea ca extragand de trei ori cate o bila (fara a pune bila extrasa inapoi), sa obtinem la prima extragere o bila alba, iar la urmatoarele extrageri cite o bila neagra.
Formula probabilitatii totale
Definitie. O multime de evenimente formeaza un sistem complet de evenimente daca acestea sunt incompatibile doua cate doua si reuniunea lor este evenimentul sigur.
Teorema. Daca
Demonstratie. Din faptul ca
iar
Conform regulii inmultirii probabilitatilor, avem :
care inlocuite mai sus, conduc la demonstrarea formulei.
Exemplu. Fie trei urne continand bile albe si negre, dupa cum urmeaza :
Dintruna din aceste urne se extrage la intamplare o bila. Care este probabilitatea ca bila extrasa sa fie alba ?
Formula lui Bayes
Teorema. Daca
Demonstratie. Aplicand formula inmultirii probabilitatilor, se obtine:
De aici rezulta ca
Pentru
calculul lui
si inlocuind, se obtine:
care se mai poate scrie
Exemplu. Fie doua urne care
contin bile albe si negre:
Variabile aleatoare
Frecvent, in viata de toate zilele, intalnim marimi ale caror valori se schimba sub influenta unor factori intamplatori.
Definitie. O marime asociata unei experiente aleatoare si care ia valori la intamplare, in functie de rezultatul experientei, se numeste variabila aleatoare.
De aici se poate desprinde concluzia ca o variabila aleatoare reprezinta o corespondenta intre multimea rezultatelor posibile ale unei experiente aleatoare si multimea numerelor reale.
Definitie. O variabila aleatoare este o functie care asociaza fiecarui eveniment elementar (fiecarui eveniment al spatiului de selectie) un numar real.
Definitie. Fiind dat un camp de
probabilitate
Observatie. Unele variabile aleatoare pot lua un numar finit de valori, iar altele pot lua orice valoare dintrun interval.
Definitie. O variabila aleatoare este discreta daca multimea valorilor sale este o multime discreta (finita sau numarabila).
Observatie. Daca multimea valorilor unei variabile aleatoare este finita, variabila aleatoare se numeste simpla.
Definitie. Ovariabila aleatoare este continua daca multimea valorilor sale este o submultime a lui R
Variabile aleatoare discrete
Tinand seama de faptul ca valorile unei variabile aleatoare sunt influentate de cauze aleatoare, iar unele valori pot aparea mai des decat altele, rezulta ca o variabila aleatoare este mult mai bine precizata daca se cunoaste si probabilitatea cu care este luata fiecare valoare.
sau
Operatii cu variabile aleatoare discrete
Fie
Suma si produsul cu o constanta se prezinta astfel:
Suma celor doua variabile se calculeaza dupa cum urmeaza:
unde
Daca variabilele aleatoare sunt independente, atunci
Produsul celor doua doua variabile are urmatoarea distributie:
unde
Exemple.
Fie
Suma este
data de
Produsul este dat de
deoarece
Independenta variabilelor aleatoare
Fie
Definitie. Variabilele aleatoare
simple
Observatie. Cu alte cuvinte, doua variabile aleatoare sunt independente daca probabilitatea ca una din variabile sa ia o anumita valoare nu depinde faptul ca cealalta a luat o alta valoare.
In cazul variabilelor aleatoare discrete care iau o multime numarabila de valori, distributia se prezinta astfel:
Observatie. Operatiile cu variabile discrete care iau o multime numarabila de valori se efectueaza la fel ca operatiile cu variabile aleatoare simple.
Media unei variabilei
aleatoare discrete simple
Media unei variabilei
aleatoare discrete
Proprietati. Daca
1.
Se stie ca
2.
Se
observa ca
3.
Fie
4. Daca
Fie
Definitie. Se numeste moment de ordinul
Dispersia variabilelor aleatoare discrete
Pentru caracterizarea unei variabile aleatoare, valoarea medie este, in general, insuficienta. Doua variabile aleatoare simple pot lua acelasi numar de valori si pot avea aceeasi medie, dar in timp ce una ia valori apropiate de valoarea medie, cealalta poate sa ia valori foarte departate de aceasta medie.
Exemplu.
Fie
De aici rezulta necesitatea introducerii unui indicator numeric, care sa masoare gradul de imprastiere a valorilor unei variabile aleatoare in jurul valorii medii.
Dispersia unei variabile aleatoare discrete
iar abaterea
medie patratica este
Dispersia se mai noteaza si calculeaza astfel:
Proprietati
1.
2. Doua
variabile care difera printr-o constanta au dispersii egale. Daca
3.
4. Dispersia unei sume finite de variabile aleatoare independente doua cate doua este egala cu suma dispersiilor variabilelor considerate.
Exemplu. Fie variabila aleatoare
Sa se calculeze
Variabile aleatoarede tip continuu
Definitie. Se numeste lege de probabilitate, o corespondenta intre valorile posibile ale unei variabile aleatoare si probabilitatile corespunzatoare.
In cazul variabilelor de tip continuu, legea de probabiltate este corespondenta dintre intervalele dreptei reale si probabilitatile corespunzatoare acelor intervale.
Definitie. Se numeste functie de repartitie a variabilei
aleatoare
Functia de repartitie se poate calcula pentru variabile de tip discret, dar ea prezinta mare interes pentru variabile de tip continuu.
Exemplu.
Fie variabila aleatoare simpla:
Proprietati
1. Pentru orice variabila
aleatoare
deoarece
2.
Evenimentul
3.
4.
Daca
Definitie. Spunem ca
unde
Definitie. Functia
: R → R este densitate de repartitie a variabilei aleatoare
a)
b)
este integrabila pe R si
Observatii.
Exemplu.Sa se determine
constantele
sa fie densitate de repartitie.
Exemplu. Fie
Media si dispersia unei variabile aleatoare de tip continuu
Fie
Definitie. Se numeste valoare
medie a variabilei
Observatie. Definitia se
pastreaza si pentru
Proptietati.
Daca
2.
3. Daca
4. Daca
Definitie.Se numeste
dispersia variabilei aleatoare
sau
Proprietati.
2.
3.
4. Daca variabilele aleatoare sunt independente doua cate doua, atunci
Tema de casa nr. 10
Fie
Sa se calculeze
Se considera trei urne:
Din fiecare din aceste urne se extrage cate o bila. Se cere valoarea medie si abaterea medie patratica a numarului de bile albe obtinute din cele trei urne.
Fie
Se cere:
a)
distributia sumei
b)
distributia produsului
Se considera variabilele aleatoare independente.
Sa se calculeze
Se arunca un zar de 120 de ori. Sa
se gaseasca o margine inferioara pentru probabilitatea
Cursul nr. 11 Matematici speciale
Repartitii clasice de probabilitate
Repartitii clasice discrete
Repartitia uniforma discreta pe
X :
Repartitia binomiala de parametri n
X
Repartitia geometrica de parametru p
X :
Repartitia Poisson de parametru >0:
X :
Repartitii clasice continue
Repartitia uniforma pe (a,b) are functia de densitate
f(x) =
Repartitia exponential negativa de parametru >0
f(x) =
Repartitia normala
(Gauss) de parametri m>0 si σ
f(x) =
. Repartitia uniforma pe (a,b) are functia de densitate
f(x) =
Media variabilei aleatoare X ce are functia de densitate f x) este
M[X] =
Pentru calculul dispersiei folosim tot proprietatea D [X] = M[X ] - M [X], unde
M[X ] =
si deci
D [X] = M[X ] - M [X] =
2.Repartitia exponential negativa de parametru >0 are functia de densitate
f(x) =
M[X]=
Cum
rezulta ca
M[X]
= 0 - 0 +
Pentru calculul dispersiei folosim tot proprietatea D [X] = M[X ] - M [X], unde
M[X ]=
Cum
rezulta ca
M[X ] = 0 - 0 + 2
Revenind,
D2[X] = M[X ] - M [X] =
De exemplu, variabila aleatoare X ce reprezinta durata de functionare a unei lampi are repartitie exponential negativa.
c) Repartitia normala (Gauss) de parametri m>0 si σ
f(x) =
M[X]=
=
=
=
Dar
I∙I =
unde se face schimbarea de variabila
Jordanianul schimbarii de variabile este
Deci
I∙I =
De unde
I =
Revenind,
M[X]
=
D [X]
=
Tema de casa nr. 11
Fie
a) Sa se verifice ca
b) Sa se calculeze functia de repartitie corespunzatoare.
c) Sa se calculeze
Fie
a) Sa se determine constanta c astfel incat
b) Sa se determine functia de repartitie corespunzatoare.
c) Sa se calculeze probabilitatea ca variabila aleatoare X sa ia valori intre
Fie
a) Sa se determine
b) Sa se calculeze functia de repartitie corespunzatoare.
c) Sa se calculeze
d) Daca X si Y sunt variabile aleatoare independente
avand densitatea de repartitie f, sa
se calculeze
Fie
a) Sa se determine
b) Sa se determine densitatea de repartitie corespunzatoare.
c) Sa se calculeze
Cursul nr. 12+13 Matematici speciale
GRAFURI
Grafuri neorientate
Definitie. Un graf neorientat este definit
de perechea ordonata
Graful poate fi descris in plan printr-o figura in care nodurile sunt reprezentate prin puncte, iar muchiile prin segmente de dreapta sau arce de curba.
Fie
Intrun graf neorientat notatia
Multe realitati din jurul nostru se pot reprezenta prin grafuri : reteaua cailor de transport intre localitatile unei tari (localitatile sunt reprezentate prin noduri, iar soselele prin muchii), sustemul energetic, sistemul de comunicatii etc.
Ploiesti Brasov
Bucuresti Sibiu
Pitesti Rm. Valcea
|
Fig.FF
Figura 1
* * * * * *
Furnizor Depozit Sectia 2 Asamblare Control Beneficiar
*
Sectia 3
* Sectia 1 * * * * * * Furnizor Depozit Sectia 2 Asamblare Control Beneficiar * Sectia 3 |
Figura 2
X2 X5 * *
X1 *
* *
X3 X4
X2 X5 X1 X3 X4 |
Figura 3
Observatie Prin reprezentarea unor retele sau sisteme sub forma unor grafuri avem avantajul ca le putem studia mai usor, utilizand tehnica modelarii matematice si/sau simularii.
Definitie. Se spune ca varfurile
Altfel spus, doua varfuri sunt adiacente daca sunt extremitatile aceluiasi arc.
Gradul unui nod
Definitie. Un graf se numeste complet daca oricare doua noduri ale sale sunt adiacente.
De exemplu, graful din figura 3 este complet.
Propozitie. Pentru un graf cu n noduri si m muchii are loc relatia :
Demonstratie. Fiecare muchie se numara de doua ori, cate o data pentru fiecare din nodurile sale.
Definitie. Se numeste subgraf al
grafului
Definitie. Se numeste lant, o
succesiune de varfuri
Varfurile
Definitie. Un lant ale carui varfuri sunt toate distincte, se numeste lant elementar.
Exemple. Fie grafurile :
SHAPE * MERGEFORMAT
X2 X5 X8 X9 X1 X3 X4 X7 X10 X6 X11
Lanturile
Definitie Se numeste ciclu, un lant in care primul vtrf coincide cu ultimul si toate muchiile sunt distincte.
Definitie. Un ciclu se numeste elementar, daca toate varfurile sale, cu exceptia primului si ultimului varf, sunt distincte.
Exemplu Fie graful neorientat :
SHAPE * MERGEFORMAT X2
X1 X3
X5
X6 X4
Definitie Un graf se numeste conex daca pentru oricare doua varfuri distincte ale grafului exista un lant avand ca extremitati acele varfuri.
X3
X1
X4 X5 X6 X5 X4
Graful nu este conex Graful este conex
Observatie. In cazul unui graf care nu este conexse poate pune problema determinarii componentelor sale conexe.
O componenta conexa se defineste ca un subgraf conex maximal.
X1 X2 X3 X2 X3 X1 X4 X5 X6 X5 X4 Graful nu este conex Graful este conex Observatie In cazul unui graf
care nu este conex se poate pune problema determinarii componentelor sale
conexe. O componenta conexa se defineste ca un subgraf conex maximal.
Exemple
Grafuri orientate
Definitie. Un graf orientat este definit de
perechea ordonata
Fie
Observatie In cazul grafurilor
neorientate
Un graf orientat are arcele reprezentate prin sageti orientate de la extremitatea initiala spre extremitatea finala a arcului respectiv.
Exemplu Graful orientat
SHAPE * MERGEFORMAT
X2 X4
X1 X6
X3 X5
Definitie. Se numeste graf partial
al unui graf orientat
Definitie. Se numeste subgraf al
grafului orientat
Definitie. Un graf orientat se numeste complet daca oricare doua varfuri ale sale sunt adiacente (sunt legate printr-un arc).
Observatie. In cazul grafurilor orientate, notiunilor de lant si ciclu le corespund notiunile de drum si circuit.
Exemplu.
X1 X2 *
* *X3 * X4 *
* X5 X6 SHAPE * MERGEFORMAT
Definitie. Un graf se numeste simetric daca pentru fiecare peeche de
varfuri din
Exemplu. Graf simetric
X1 *
X2 * * * ** X3 X4
Definitie. Se numeste bucla un arc ale carui extremitati (initiala si finala) coincid.
Exemplu. SHAPE * MERGEFORMAT
X2 X5 *
* X1* *
* X3 X4
Definitie. Se numeste drum, un sir de varfuri
Definitie. Un drum se numeste elementar daca toate varfurile sale sunt distincte.
Definitie Se numeste circuit un drum ale carui extremitati coincid, iar arcele sale sunt distincte.
Definitie Se numeste circuit elementar un circuit ale carui varfuri sunt distincte, cu exceptia extremitatilor.
Exemplu. Fie graful
SHAPE * MERGEFORMAT X2 X4
* *
X1* *X6
* *
X3 X5
Definitie. Un graf (orientat sau neorientat) se numeste conex daca pentru oricare doua varfuri distincte ale grafului exista un lant avand ca extremitaai acele varfuri.
Definitie. Un graf orientat se numeste
semi-tare conex daca oricare ar fi doua varuri
Definitie. Un graf orientat se numeste tare
conex daca oricare ar fi doua varuri
Exemple.
SHAPE * MERGEFORMAT
X2 X2 X1 X2 * * * * *X4 * * * X1 * X1 X4 X3 * X4 * * * * X3 X5 X3 X5 * X5
Graf conex Graf semi-tare conex Graf tare conex
Definitie. Un drum intr-un graf se numeste hamiltonian daca trece
prin toate varfurile grafului dat o singura data.
Matrice asociate unui graf
Pentru a fi mai usor de studiat, adeseori grafurilor li se asociaza matrice, care au avantajul ca faciliteaza studiul proprietatilor grafului.
Matricea conexiunilor(tranzitiilor):
Este o matrice booleana care are valoarea 1 daca
in graf exista arcul
Exemplu.
SHAPE * MERGEFORMAT
*
Matricea ponderilor(capacitatilor)
unde
Matricea ponderilor difera de matricea conexiunilor prin aceea ca in locul lui 1 se pune ponderea arcului respectiv.
Matricea latina
Matricea latina contine pozitiile varfurilor conectate prin arcul respectiv.
Matricea de incidenta
Matricea de
incidenta
X2 a1 a2 a3 a4 a5 a6 a7
X1 +1 -1 0 0 0 0 0
X2 -1 0 -1 +1 +1 0 0
X1
X3 0 0 0 0 -1 -1 0 X3
X4 0 0 0 -1 0 +1 -1
X5 0 +1 +1 0 0 0 +1
X5 X4
Exemplu.Matricea drumurilor
Aceasta matrice este patraatica, avand ordinul
egal cu numarul varfurilor grafului. Elementele
Exemplu.
SHAPE * MERGEFORMAT
X2 X3
X1 X2 X3 X4 X5 X1 0 1 1 1 1 X2 0 0 1 1 1 X1 X3 0 0 0 1 0 X5 X4 X4 0 0 0 0 0 X5 0 0 0 1 0
1.4. Drumuri de valoare optima
Rezolvarea problemelor care se pot reprezenta sub forma unor grafuri se reduce la determinarea drumurilor maxime sau minime.
Algoritmul lui Ford
Fie
Pentru un arc al grafului
Xj
Xh
Xk
a)
b)
c)
Din a) rezulta ca
Din b) rezulta ca
Din c) rezulta ca drumul de la
Cautand drumulde valoare minima constatam ca in situatia c) exista un drum
Marcajul varfului
Dupa un numar finit de asemenea comparatii, lund
in consderatie celelalte varfuri ale grafului, se obtine valoarea minima a
drumurilor de la
Algoritmul lui Ford pentru determinarea drumului
de valoare minima intre varfurile
Fiecarui varf al grafului
ise asociaza un marcaj
Se compara diferentele
dintre marcajul varfului final si marcajul varfului initial pe fiecare arc
Procedeul continua pana cand dupa s ajustari ale marcajului varfurilor se obtin numai inegalitati de forma:
In acest moment,
Fie
Adunand aceste egalitati membru cu membru se obtine:
si cum
Exemplu. Sa se determine drumul de
valoare minima intre
SHAPE * MERGEFORMAT
X2 3 X5 * * 3 1 2 5 2 2 1 5 X1* * * X3 X6 3 * X8 3 2 4 1 3 * * X4 X7 X4 X7
Alegem:
Consideram tabelul:
|
|
|
|
|
| ||||
| ||||
| ||||
| ||||
| ||||
| ||||
| ||||
|
3
|
(1)
|
||
| ||||
| ||||
| ||||
| ||||
|
4
| |||
| ||||
|
2
|
Drumul minim este
Tema de casa.
Metoda drumului critic
Teoria grafurilor are aplicatii in diverse ramuri de activitate. De exemplu, o lucrare complexa la a carei realizare concura mai multe activitati se poate reprezenta printr-un graf orientat care descrie esalonarea in timp si interconditionarea actiunilor necesare. Intr-un asemenea graf arcele indica etapele sau activitatile elementare ale lucrarii respective. Fiecarui arc i se asociaza o valoare care reprezinta durata realizarii activitatii asociate arcului respectiv, exprimata in unitati de timp sau alte unitati de masura. Extremitatea initiala a unui arc reprezinta momentul inceperii activitatii, iar extremitatea finala momentul terminarii activitatii.
Exemplu.
SHAPE * MERGEFORMAT
C E 3 6 2 A B G 3 4 D 5 H 3 4 F t
Inceperea activitatii este marcata de nodul sau varful A, iar terminarea ei de varful H.
Activitatile reprezentate de arcele (BC) si (BD) sau (DE) si (DF), (FG) se desfasoara in acelasi timp.
Un graf de activitati are proprietatea ca nu contine circuite, deoarece o activitate incepe dupa terminarea celei precedente. In cazul circuitelor o activitate incepe dupa terminarea ei insasi.
Drumul critic este acela care se obtine ca insumare a tuturor timpilor si are lungimea maxima.
Drumul critic reuneste activitati de a caror realizare la timpul prevazut depinde realizarea la timp a intregii lucrari.
Se considera un graf de activitati G, ale carui
varfuri reprezinta evenimentele
Presupunem ca
Lungimea maxima a drumurilor de forma
De exemplu, data asteptata a evenimentului B este
Pentru fiecare eveniment
Data limita a evenimentului
De exemplu,
Data
Intervalul
Daca notam cu
Notam cu
Cu aceste notatii, determinarea momentelor si respectiv
unde
Exemplu. Sa se determine drumul critic in urmatorul graf:
SHAPE * MERGEFORMAT 5 4
6 4 4
6
3 2
3 5 5
Data terminarii lucrarii
Calculam datele limita:
Evenimentele pentru care
In exemplul de mai sus toate evenimentele sunt critice, cu exceptia evenimentului 2.
Arcele critice compun drumul sau drumurile critice ale activitatilor.
In exemplul de mai sus, drumul critic este (1,3,4,5,6).
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2356
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved