Pune o întrebare

Ştiinţă şi Filosofie

în 7 Martie 2011 | anonim_4396 a întrebat:

Salut.
Curand o sa dau test la info din G. N. (Grafuri neorientate) si este ceva ce nu am inteles.

Cum poti calcula cate noduri izolate are un G. N. cu n noduri si m muchii? Daca este, de exemplu, 10 noduri si 15 muchii, pot sa desenezi si imi dau seama. Dar am vazut undeva: Sa secalzuleze numarul de noduri izolate al unui G. N. cu 400 de noduri si 500 muchii.

Va rog mult, ajutati-ma! Vot si funda!:*

5 Raportează Evaluează

Răspuns Câştigător

în 8 Martie 2011 | a răspuns:

Trebuie o formulă.
atunci ma gandesc ca se refera la numarul maxim(sau minim) de noduri izolate fiind date nr. de noduri si nr. de muchii.

pentru numarul maxim de noduri punem cat mai multe muchii pe cat mai putine noduri. ne folosim de asta "numarul de muchii intr-un graf complet este nr(nr-1)/2"
in cazul de faţă egalăm nr(nr-1)/2 cu 500. de aici rezulta ca avem 32 de noduri pe care putem cele 500 de muchii. restul de 400-32=368 sunt noduri izolate. deci putem avea maxim 368 de noduri izolate.

pentru numarul minim de noduri izolate inmultim nr de muchii la 2. deoarece punem o muchie la fiecare 2 noduri. rezulta pot fi acoperite toate. deci minimul = 0

Răspunde

Ordonare:

4 răspunsuri:

Expert TPU

în 8 Martie 2011 | a răspuns:

Măcrin ţi-a dat răspunsul cel mai exact.
Da' la voi în liceu se practică lucrările scrise la programare?
Când eram în liceu toate astea se făceau la calculator.
Nu de alta dar voi nu sunteţi compilere ambulante şi nu poţi da ctrl+F9 în minte ca să vezi dac-ai scris corect thinking
În fine, baftă la lucrare.

Răspunde Raportează Evaluează

în 7 Martie 2011 | a răspuns:

Sa se calzuleze numarul de noduri izolate al unui G.N. cu 400 de noduri si 500 muchii.
Pentru 400 de noduri ai minim 200 de muchii (din fiecare nod pleaca minim o muchie spre alt nod). Iar apoi pentru aceste 400 de noduri atinse mai poti trasa inca o gramada de muchii, mai mult decat 300. Deci cred ca poti avea intre 0 si 300 de noduri izolate. E o logica de moment, nu stau sa aprofundez...

Răspunde Raportează Evaluează

în 7 Martie 2011 | a răspuns:

Parcurgi matricea de adiacenta(sau ce primesti la intrare) si vezi care n-are niciun vecin. marchezi intr-un vector de la 1 la n care are vecin. si cele care raman nemarcate sunt noduri izolate

Răspunde Raportează Evaluează

în 7 Martie 2011 | a răspuns:

@Lora.ti-a zis cineva ca asta e tema?
Nu e, stai linistit.

Răspunde Raportează Evaluează

Întrebări similare

trimisă pe 30 August 2012
lucigabi întreabă:

Câte grafuri neorientate, distincte, cu 4 vârfuri, se pot construi? cu ce formula se calculeaza si de ce? funda

1 răspuns
trimisă pe 15 Mai 2012
Andrei_Pintilie_1994 întreabă:

Grafuri orientate si neorientate - istoric, probleme celebre ce au stat la baza, probleme deosebite legate de grafuri orientate/neorientate. Ma poate ajuta cineva?

4 răspunsuri
trimisă pe 7 Martie 2017
Emilian_Marco_1992 întreabă:

Care este diferenta dintre * drum * si * lant * la grafuri? Lantul e pentru grafurile neorientate pe cand drumul e pentru cele orietante? Sau cum

4 răspunsuri
trimisă pe 8 Octombrie 2013
Madalyna29 întreabă:

De curand la matematica am inceput sa lucrez cu logaritmi, dar nu- i inteleg mai deloc. Ok, am invatat fromule, proprietati, tot, dar nu- mi pot da seama cum sa- i calculez. Spre exemplu,...? (mai mult)

1 răspuns
trimisă pe 8 Ianuarie
Dfghhghu întreabă:

Salut! In iulie dau bacul, vreau sa dau bacul la informatica (sunt pe mate info), stiu programare, rezolv probleme de informatica cu vextori, matrici etc, dar cand vine vorba de backtracking si grafuri...? (mai mult)

3 răspunsuri

Zelist Monitor

Întrebări recente

trimisă acum 29 minute
Sportacus123 întreabă:

Ce simbolizează un pescăruș la tine pe balcon?

0 răspunsuri
trimisă pe 20 Mai
SingleForOne întreabă:

Am urmărit o postare pe Facebook, în care se discuta despre faptul că scheletul aripioarei delfinilor arată foarte similar cu scheletul mâinii oamenilor. Mai departe, discutau despre posibilitatea...? (mai mult)

1 răspuns
trimisă pe 20 Mai
RAY întreabă:

Economic vorbind în ce buget ar trebui hainele sa se incadreze? Mă refer cam cat 100% din venituri? Sau mai bine aduni și cumperi de calitate prin economie?

6 răspunsuri
trimisă pe 19 Mai
sabin89 întreabă:

Idealul omului este să trăiască bine, vorba unui fost președinte. Sau, parafrazând un personaj caragialesc, în lume să fie bine și tot omul să prospere. De- a lungul timpului s- au făcut pași...? (mai mult)

13 răspunsuri

Cele mai vizionate întrebări

trimisă pe 25 Ianuarie
sabin89 întreabă:

Totul este în mișcare. Dacă te- ai putea situa undeva în spațiu, ai vedea Pământul cum se învârte în jurul axei și cum aleargă în mare viteză pe traiectorie în jurul Soarelui. Ai vedea ...? (mai mult)

16 răspunsuri
trimisă pe 9 Februarie
sabin89 întreabă:

"Din haos, Doamne, am apărut..." - Ca întotdeauna, se pare că Eminescu a avut dreptate și de data asta. Păi, ce a fost la început de tot? Nu haos? Înainte să fi apărut singularitatea ce era?...? (mai mult)

32 răspunsuri
trimisă pe 30 Aprilie
Răzvănykă întreabă:

Specia umana a dezvoltat constiinta pe parcursul adaptarii evolutioniste?

61 răspunsuri
trimisă pe 15 August
sabin89 întreabă:

Unii afirmă că nu e bine ca tot omul să gândească cu propriul său cap, pentru că aceasta duce la haos, ci mult mai bine este să se țină toată lumea de autoritatea recunoscută. Sunteți sau...? (mai mult)

22 răspunsuri

Remarcate de editori

RoxanaIoana108 a primit o monedă TPU pentru răspunsul:

Buna, Darius! Vreau sa îți spun pentru început ca ești un baiat minunat și ca ai tot viitorul in fata. Parintii tai se vor descurca, sunt convinsă de asta. Dacă nu ai un telefon de ultima generație,...... (mai mult)
Miruna333 a primit o monedă TPU pentru răspunsul:

Prin comunicare, comunici frumos cu persoana respectiva si vezi semne de la primele intalniri, ii descoperi personalitatea, comportamentul, cat si planurile de viitor si vezi daca acestea coincid cu...... (mai mult)
TheGentleman a primit o monedă TPU pentru răspunsul:

A încercat Ilia Ivanovici Ivanov acest lucru și parțial a reușit. A eșuat în a obține hibrizi om- cimpanzeu, dar a reușit în schimb să obțină calul Przewalski (Equus caballus przewalskii),...... (mai mult)

Categorii