se considera un graf neorientat cu 50 noduri si 32 muchii. Care este numarul maxim de varfuri cu gradul 0 pe care le poate avea graful. +explicatie va rog, ca nu prea inteleg grafurile.
Răspunsuri la întrebare
Răspuns de
21
41 de noduri.
Explicatie:
numarul maxim de noduri dintre cele 50 cu care putem forma un subgraf complet este 8 - se afla pe baza nr. de muchii si noduri (32/50) rezolvand inecuatia: combinari de n luate cate 2 = C(n,2)<=32 ->n*(n-1)/2<=32 -> n*(n-1)<=64 - >n<=8. Luand n maxim (8), C(8,2)=28 muchii, mai raman -> 32-8=4 muchii si 50-8=42 varfuri. Mai legam unul dintre cele 42 de noduri ramase la 4 dintre cele 8 noduri ale subgrafului complet, "consumand" astfel si ultimele 4 muchii. Mai raman 42-1=41 noduri izolate. Deoarece am unit un numar minim de noduri(8+1=9) prin cele 32 muchii disponibile - >nr. de npduri ramas - 41 - este maxim.
Explicatie:
numarul maxim de noduri dintre cele 50 cu care putem forma un subgraf complet este 8 - se afla pe baza nr. de muchii si noduri (32/50) rezolvand inecuatia: combinari de n luate cate 2 = C(n,2)<=32 ->n*(n-1)/2<=32 -> n*(n-1)<=64 - >n<=8. Luand n maxim (8), C(8,2)=28 muchii, mai raman -> 32-8=4 muchii si 50-8=42 varfuri. Mai legam unul dintre cele 42 de noduri ramase la 4 dintre cele 8 noduri ale subgrafului complet, "consumand" astfel si ultimele 4 muchii. Mai raman 42-1=41 noduri izolate. Deoarece am unit un numar minim de noduri(8+1=9) prin cele 32 muchii disponibile - >nr. de npduri ramas - 41 - este maxim.
Răspuns de
54
O să încerc să dau un răspuns mai mult intuitiv decât teoretic.
Un graf neorientat e o chestie formată din buline (noduri) conectate prin muchii.
Vârf = Nod
Gradul unui Vârf/Nod e, de fapt, numărul de conexiuni ale acelui nod. De exemplu, dacă ai avea 3 noduri conectate între ele (ca un triunghi), fiecare dintre ele ar avea gradul 2, pentru că fiecare dintre ele are 2 muchii conectate cu el.
Ce înseamnă să aibă gradul 0? Înseamnă că acel nod, cu gradul 0, nu are nicio conexiune, nicio muchie cu nimeni. Un graf poate avea și astfel de noduri, pur și simplu, singure, deconectate de restul, sau chiar mai multe grupuri de noduri conectate.
Un alt exemplu de graf poate fi văzut în figura 1 (atașată). Acolo, fiecare nod are următoarele grade:
Nodul 1 este de gradul 2 (are 2 muchii, e conectat cu 3 și cu 4).
Nodul 2 tot gradul 2.
Nodul 4 este de gradul 3 (are 3 muchii, conectat cu 1, 2 și 7)
Nodul 6 are gradul 0. E singur, nu e conectat cu nimeni.
Sper că până aici ai înțeles ideea.
Să trecem la rezolvare:
Se știe că graful trebuie să aibă fix 50 de noduri și fix 32 de muchii. Și scopul este obținerea a cât mai multe vârfuri de grad 0, adică cât mai multe noduri singure.
Păi, să vedem cum am putea face asta.
Încercarea 1: (Fig. 2)
Păi, am putea lua 33 dintre noduri, și să facem un lanț lung, să folosim toate cele 32 de muchii. Iar restul de 17 ar rămâne singure, de gradul 0. Ceva de genul:
1 -- 2 -- 3 -- ... -- 33 (conectate între ele, doar 1 cu 2, apoi 2 cu 3, apoi 3 cu 4, șamd.)
34 35 36 .... 50 (singure)
17 e un număr bunicel, dar totuși, am putea obține unul mai bun?
Încercarea 2: (Fig. 3)
Dacă am face cumva triunghiuri, câte 3 noduri conectate între ele, până epuizăm muchiile, hmm:
1 -- 2 .... (1, 2 și 3 conectate între ele. 4, 5, și 6 conectate între ele, etc)
| /
3
Păi, la 10 seturi de astea, avem 30 de muchii și 30 de noduri luate. Mai luăm 3 noduri ce le conectăm între ele cu două muchii, gen primul cu al doilea, și al doilea cu al 3-lea. Și așa avem cam 33 de noduri cu grad 1 sau 2, toate cele 32 de muchii folosite. Și deeeeci, au rămas 17 de noduri singure.. Dubios, la fel. Cam puțin.
Încercarea 3: (Fig 4.)
Dacă, totuși, încercăm să grupăm mai multe, să zicem câte 4. Am putea, la fiecare grup de 4 să punem, în total 4+2 = 6 muchii (4 pe laterale, ca pătrat + 2 diagonale). Deci 6 muchii la fiecare 4 noduri. Astea înseamnă că pentru 30 de muchii de trebuie 5 seturi de astea (5*6 = 30). Deci cu 5*4 = 20 de noduri, obținem un total de 30 de muchii. Ne mai trebuie 2. Le punem la fel, 3 noduri conectate în serie, și am făcut toate cele 32 de muchii. Și câte noduri au rămas? Păi 20+3 folosite (cu grad > 0). Așadar rămââân... :D 27 de noduri, ooo, mai bine :)
1 -- 2
| x |
3 -- 4 ....
Și în acest punct observăm că, totuși, dacă am grupa mai multe noduri, poate am putea să punem și mai multe muchii într-un set de ăsta mic, și să ne rămână mai multe noduri libere, deci să ajungem la acel maxim.
Încercarea 4: (Fig 5.)
Bun.. Dacă grupăm câte 5 noduri și facem toate muchiile posibile, păi să vedem, cam câte ar fi...
Din 1, putem merge la 2, 3, 4, 5 (deci 4 muchii)
Din 2, mai putem merge la 3, 4, 5 (deci 3 muchii)
Din 3, mai putem merge la 4, 5 (deci încă 2 muchii)
Din 4, mai putem conecta doar 5-ul (deci încă o muchie)
Deci, pentru 5 noduri, maximul de muchii dintre ele poate fi 4+3+2+1 = 10.
** Dacă nu înțelegi ce am făcut aici, ia o foaie și încearcă să desenezi pe ea 5 noduri și să vezi câte muchii poți face maxim între ele, toate posibile.
Deci, dacă grupăm 5 noduri, facem 10 muchii. Bun, deci cu 15 noduri am rezolvat deja 30 de muchii. Mai sunt încă 2, cu care facem la fel, 3 noduri conectate în serie, 2 muchii. Și aici iesee un total de 15+3 = 18 noduri cu conexiuni/muchii, și în rest, toate celelalte 32 de muchii libere :D Și mai tare..
Dar hai să mergem mai departe... Am putea face la fel și cu 6, 7.. Dar să încercăm să ne dăm seama unde trebuie să ne oprim... Am observat că formula de calcul ar fi, pentru un grup de n noduri, (n+1) + (n+2) + ... + 2 + 1 muchii.. (Ex, pt 10 noduri, nr maxim de muchii dintre ele ar fi 9+8+...+2+1).
Noi am vrea cumva un grup care să acopere toate cele 32, sau chiar mai multe, pentru că pur și simplu putem să nu punem unele muchii ca să păstrăm numărul de 32 și în rest să rămână la fel.
Păi, să vedem, cu 7 noduri:
6+5+4+3+2+1 = 21 de muchii maxim
Cu 8 noduri:
7+6+...+1 = 21+7 = 28 de muchii maxim
Cu 9 noduri:
8+7+...+1 = 28+8 = 36 de muchii, yaaayy
Deci cu 9 noduri, dacă le conectăm pe toate între ele, avem 36 de muchii. Doar că nu punem toate muchiile, putem pune oricare din ele, până la 32. Și rămân toate celelalte, 41 de noduri, libere, de grad 0. :) Deci un nou record. 41 de noduri libere.
(continuarea în comentarii...)
Un graf neorientat e o chestie formată din buline (noduri) conectate prin muchii.
Vârf = Nod
Gradul unui Vârf/Nod e, de fapt, numărul de conexiuni ale acelui nod. De exemplu, dacă ai avea 3 noduri conectate între ele (ca un triunghi), fiecare dintre ele ar avea gradul 2, pentru că fiecare dintre ele are 2 muchii conectate cu el.
Ce înseamnă să aibă gradul 0? Înseamnă că acel nod, cu gradul 0, nu are nicio conexiune, nicio muchie cu nimeni. Un graf poate avea și astfel de noduri, pur și simplu, singure, deconectate de restul, sau chiar mai multe grupuri de noduri conectate.
Un alt exemplu de graf poate fi văzut în figura 1 (atașată). Acolo, fiecare nod are următoarele grade:
Nodul 1 este de gradul 2 (are 2 muchii, e conectat cu 3 și cu 4).
Nodul 2 tot gradul 2.
Nodul 4 este de gradul 3 (are 3 muchii, conectat cu 1, 2 și 7)
Nodul 6 are gradul 0. E singur, nu e conectat cu nimeni.
Sper că până aici ai înțeles ideea.
Să trecem la rezolvare:
Se știe că graful trebuie să aibă fix 50 de noduri și fix 32 de muchii. Și scopul este obținerea a cât mai multe vârfuri de grad 0, adică cât mai multe noduri singure.
Păi, să vedem cum am putea face asta.
Încercarea 1: (Fig. 2)
Păi, am putea lua 33 dintre noduri, și să facem un lanț lung, să folosim toate cele 32 de muchii. Iar restul de 17 ar rămâne singure, de gradul 0. Ceva de genul:
1 -- 2 -- 3 -- ... -- 33 (conectate între ele, doar 1 cu 2, apoi 2 cu 3, apoi 3 cu 4, șamd.)
34 35 36 .... 50 (singure)
17 e un număr bunicel, dar totuși, am putea obține unul mai bun?
Încercarea 2: (Fig. 3)
Dacă am face cumva triunghiuri, câte 3 noduri conectate între ele, până epuizăm muchiile, hmm:
1 -- 2 .... (1, 2 și 3 conectate între ele. 4, 5, și 6 conectate între ele, etc)
| /
3
Păi, la 10 seturi de astea, avem 30 de muchii și 30 de noduri luate. Mai luăm 3 noduri ce le conectăm între ele cu două muchii, gen primul cu al doilea, și al doilea cu al 3-lea. Și așa avem cam 33 de noduri cu grad 1 sau 2, toate cele 32 de muchii folosite. Și deeeeci, au rămas 17 de noduri singure.. Dubios, la fel. Cam puțin.
Încercarea 3: (Fig 4.)
Dacă, totuși, încercăm să grupăm mai multe, să zicem câte 4. Am putea, la fiecare grup de 4 să punem, în total 4+2 = 6 muchii (4 pe laterale, ca pătrat + 2 diagonale). Deci 6 muchii la fiecare 4 noduri. Astea înseamnă că pentru 30 de muchii de trebuie 5 seturi de astea (5*6 = 30). Deci cu 5*4 = 20 de noduri, obținem un total de 30 de muchii. Ne mai trebuie 2. Le punem la fel, 3 noduri conectate în serie, și am făcut toate cele 32 de muchii. Și câte noduri au rămas? Păi 20+3 folosite (cu grad > 0). Așadar rămââân... :D 27 de noduri, ooo, mai bine :)
1 -- 2
| x |
3 -- 4 ....
Și în acest punct observăm că, totuși, dacă am grupa mai multe noduri, poate am putea să punem și mai multe muchii într-un set de ăsta mic, și să ne rămână mai multe noduri libere, deci să ajungem la acel maxim.
Încercarea 4: (Fig 5.)
Bun.. Dacă grupăm câte 5 noduri și facem toate muchiile posibile, păi să vedem, cam câte ar fi...
Din 1, putem merge la 2, 3, 4, 5 (deci 4 muchii)
Din 2, mai putem merge la 3, 4, 5 (deci 3 muchii)
Din 3, mai putem merge la 4, 5 (deci încă 2 muchii)
Din 4, mai putem conecta doar 5-ul (deci încă o muchie)
Deci, pentru 5 noduri, maximul de muchii dintre ele poate fi 4+3+2+1 = 10.
** Dacă nu înțelegi ce am făcut aici, ia o foaie și încearcă să desenezi pe ea 5 noduri și să vezi câte muchii poți face maxim între ele, toate posibile.
Deci, dacă grupăm 5 noduri, facem 10 muchii. Bun, deci cu 15 noduri am rezolvat deja 30 de muchii. Mai sunt încă 2, cu care facem la fel, 3 noduri conectate în serie, 2 muchii. Și aici iesee un total de 15+3 = 18 noduri cu conexiuni/muchii, și în rest, toate celelalte 32 de muchii libere :D Și mai tare..
Dar hai să mergem mai departe... Am putea face la fel și cu 6, 7.. Dar să încercăm să ne dăm seama unde trebuie să ne oprim... Am observat că formula de calcul ar fi, pentru un grup de n noduri, (n+1) + (n+2) + ... + 2 + 1 muchii.. (Ex, pt 10 noduri, nr maxim de muchii dintre ele ar fi 9+8+...+2+1).
Noi am vrea cumva un grup care să acopere toate cele 32, sau chiar mai multe, pentru că pur și simplu putem să nu punem unele muchii ca să păstrăm numărul de 32 și în rest să rămână la fel.
Păi, să vedem, cu 7 noduri:
6+5+4+3+2+1 = 21 de muchii maxim
Cu 8 noduri:
7+6+...+1 = 21+7 = 28 de muchii maxim
Cu 9 noduri:
8+7+...+1 = 28+8 = 36 de muchii, yaaayy
Deci cu 9 noduri, dacă le conectăm pe toate între ele, avem 36 de muchii. Doar că nu punem toate muchiile, putem pune oricare din ele, până la 32. Și rămân toate celelalte, 41 de noduri, libere, de grad 0. :) Deci un nou record. 41 de noduri libere.
(continuarea în comentarii...)
Anexe:
Deeeeeci, yay, nu este nicio altă metodă mai bună: răspunsul este 41.
** Nota 1: legat de acele sume 1+2+3+....+n, există o formulă de calcul prescurtată, 1+2+3+....+n = ((n+1)*n)/2. Gen 1+2+3+4+5+6 = 7*6 / 2
Dacă nu reușești să o memorezi așa, îți pot explica și intuiția pentru asta. :))
Dacă nu reușești să o memorezi așa, îți pot explica și intuiția pentru asta. :))
** Nota 2: dacă nu reușești să vezi celelalte figuri, am senzația că pe unele dispozitive nu apar alte imagini, încearcă pe PC, iar dacă tot nu funcționează, anunță-mă, și ți le trimit altfel
** Nota 3: Sorry de calitate, înafară de prima, care e de pe net (+ mic edit), celelalte le-am făcut în Paint cu touchpad-ul. :))
** Nota 3: Sorry de calitate, înafară de prima, care e de pe net (+ mic edit), celelalte le-am făcut în Paint cu touchpad-ul. :))
Scuze, nu mă lăsase să pun și astea în comentarii, cică era prea lung. Dacă ai întrebări, întreabă. :D
Alte întrebări interesante
Matematică,
8 ani în urmă
Limba română,
8 ani în urmă
Matematică,
8 ani în urmă
Limba română,
9 ani în urmă
Limba română,
9 ani în urmă
Matematică,
9 ani în urmă
Daaar, am putea încerca cu 8? Păi, da, într-un fel, doar că nu ar fi destul, adică cu 8 acoperim 28 de muchii, apoi va trebui să mai folosim noduri ca să rezolvăm și cu restul de 4 muchii până la 32, și iar ajungem sub 41.