Download - Lab1_I21_IA21,MNI21
-
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
"".