7/24/2019 Lab1_I21_IA21,MNI21

1/7

I21, IA21; MNI21

LUCRAREA DE LABORATOR 1.

TEMA: MULIMI STABILE NTR-UN GRAF

1.Elaborai un program pentru gsirea mulii stabile interior maxime cu algoritmul indicat.

Datele pentr pn!tele " #$ % &nt la &'(r#$tl '$#$erl$

".Pentru graul G)n*ta+$ ,(r'r$le ra'l$ ! )x1x" /0 #$ !2$$le ! )u1 u" /00:

2.1. !escriei matricea de adiacen, matricea de inciden "i matricea #irc$$go;2.2. !eterminai numerele %&G "i %&G ;2.'. (onstruii graul complementar lui G;2.). !escriei un subgra complet cu numrul maxim de *+ruri a luiG;2.. Indicai un lan elementar de lungime maxim si un ciclu elementar &dac exist%;2.-. !escriei toate mulimilea% stabile interior maximale, b% mulimile stabile exterior minimale, c% clicele maximale,d% acoperirile de *+ruri minimale, e% acoperirile de muc$ii minimale, % cupla/ele maximale.2.0. !eterminai numerele .,,,, 11 2.. !escriei pe pa"i aplicarea algoritmului din primul punct la graul G.

%.3e4ol*ai problemele indicate 5n *ariant

Grpa I"1 3ar$antele

3ar$anta 1. 1.Algoritmul lui 6ednare7 "i 8aulbee ".G1-; %.1), 2.

3ar$anta ". 1.Algoritmul Malgrange. ".G10; %.1', 29

3ar$anta %. 1.Algoritmul 6ron "i #erbosc$. ".G1; %.12, '

3ar$anta 4. 1.Algoritmul lui 6ednare7 "i 8aulbee".G19; %.11, '1

3ar$anta 5. 1.Algoritmul Malgrange.".G2; %.1, '2

3ar$anta 6. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G1; %.9, 1

3ar$anta 7. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G2; %., 1-

3ar$anta 8. 1.Algoritmul 6ron "i #erbosc$. ".G'; %.-, 10

3ar$anta 9. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G); %.0, 1

3ar$anta 1. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G; %.d%, 19

3ar$anta 11. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G-; %.), 2

3ar$anta 1". 1.Algoritmul Malgrange. ".G0 %.', 2)

3ar$anta 1%. 1.Algoritmul 6ron "i #erbosc$. ".G %.), 2

3ar$anta 14. 1.Algoritmul 6ron "i #erbosc$..".G9 %.1, 2-

7/24/2019 Lab1_I21_IA21,MNI21

2/7

I21, IA21; MNI21

3ar$anta 15. 1.Algoritmul Malgrange. ".G1 %.2, 20

Grpa IA"1 3ar$antele

3ar$anta 1. 1.Algoritmul lui 6ednare7 "i 8aulbee ".G1; %.1, 1.

3ar$anta ". 1.Algoritmul Malgrange. ".G2; %.2, 1-

3ar$anta %. 1.Algoritmul 6ron "i #erbosc$. ".G'; %.', 10

3ar$anta 4. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G); %.), 1

3ar$anta 5. 1.Algoritmul 6ron "i #erbosc$. ".G; %.a%b%, 1

3ar$anta 6. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G-; %.c%, 19

3ar$anta 7. 1.Algoritmul Malgrange. ".G0; %.d%, 23ar$anta 8. 1.Algoritmul 6ron "i #erbosc$. ".G; %.-, 21

3ar$anta 9. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G9; %.0, 22

3ar$anta 1. 1.Algoritmul 6ron "i #erbosc$. ".G1; %., 2'

3ar$anta 11. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G11; %.9, 2)

3ar$anta 1". 1.Algoritmul Malgrange. ".G12 %.1, 2)

3ar$anta 1%. 1.Algoritmul 6ron "i #erbosc$.".G1' %.11, 2

3ar$anta 14. 1.Algoritmul lui 6ednare7 "i 8aulbee".G1) %.12, 2-

3ar$anta 15. 1.Algoritmul 6ron "i #erbosc$. ".G1 %.1', 20

Grpa MNI"1 3ar$antele

3ar$anta 1. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G1; %.1), 2.3ar$anta ". 1.Algoritmul Malgrange. ".G2; %.1', 10

3ar$anta %. 1.Algoritmul 6ron "i #erbosc$. ".G1; %.12, 2

3ar$anta 4. 1.Algoritmul Malgrange. ".G11; %.11, 1-

3ar$anta 5. 1.Algoritmul lui 6ednare7 "i 8aulbee ".G9; %.1, 1

3ar$anta 6. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G12; %.9, 21

3ar$anta 7. 1.Algoritmul Malgrange. ".G1'; %., 2'

7/24/2019 Lab1_I21_IA21,MNI21

3/7

I21, IA21; MNI21

3ar$anta 8. 1.Algoritmul 6ron "i #erbosc$. ".G1); %.-, 22

3ar$anta 9. 1.Algoritmul Malgrange. ".G1; %.0, 2)

3ar$anta 1. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G19; %.c%, 19

3ar$anta 11. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G0; %.), 2-

3ar$anta 1". 1.Algoritmul Malgrange. ".G %.', 1-

3ar$anta 1%. 1.Algoritmul 6ron "i #erbosc$.".G' %.), 29

3ar$anta 14. 1.Algoritmul Malgrange. ".G %.1, '

3ar$anta 15. 1.Algoritmul lui 6ednare7 "i 8aulbee. ".G- %.2, '2

Gra'r$le pentr pn!tl "

G1 G"

G% G4

G5 G6

G7 G8

7/24/2019 Lab1_I21_IA21,MNI21

4/7

I21, IA21; MNI21

G9 G1

G11 G1"

G1% G14

G15 G16

G17 G18

7/24/2019 Lab1_I21_IA21,MNI21

5/7

I21, IA21; MNI21

G19 G"

;r*

7/24/2019 Lab1_I21_IA21,MNI21

6/7

I21, IA21; MNI21

9.

7/24/2019 Lab1_I21_IA21,MNI21

7/7

I21, IA21; MNI21

"".