Bine ai venit guest
 
User:
Pass:

[Creare cont]
[Am uitat parola]
iBac = materialul ULTRACOMPLET de pregătire pentru bac la mate. Dacă vrei poţi.
Forum pro-didactica.ro  [Căutare în forum]

Forum » Problema săptămânii » Problema de colorare
[Subiect nou]   [Răspunde]
[1]
Autor Mesaj
Blaugranas
Grup: membru
Mesaje: 69
09 Oct 2012, 23:47

[Trimite mesaj privat]

Problema de colorare    [Editează]  [Citează] 

Consideram un graf complet cu N varfuri in care muchiile sunt colorate fie in rosu, fie in negru. In acest graf se pot forma triunghiuri monocromatice (3 varfuri conectate prin muchii colorate cu aceeasi culoare). Stiind ca varful 1 are c1 vecini (muchii care pleaca de la varful 1 la varful vecin) colorati in rosu, varful 2 are c2 vecini colorati in rosu,..., varful N are cN vecini colorati in rosu gasiti numarul de triunghiuri formate din totalul lor... dar care sa nu fie monocromatice (adica sa aibe 2 varfuri rosii si un varf negru sau un varf rosu si 2 varfuri negre). Se stie ca c1<N,c2<N,...,cN<N.

gauss
Grup: Administrator
Mesaje: 6933
09 Oct 2012, 22:05

[Trimite mesaj privat]


Reformulez, sper ca am inteles bine despre ce este vorba.
[Citat]

Consideram un graf complet cu N varfuri in care muchiile sunt colorate fie in rosu, fie in negru.

In acest graf se pot forma triunghiuri monocromatice
(3 varfuri conectate prin muchii colorate cu aceeasi culoare).

Stiind ca
- varful 1 este extremitate a c1 muchii colorate in rosu,
- varful 2 este extremitate a c2 muchii colorate in rosu,
:
:
- varful N este extremitate a cN muchii colorate in rosu,

gasiti numarul de triunghiuri monocromatice.
(Restul sunt ne-monocromatice.)

Se stie ca c1<N, c2<N, ..., cN<N .


Problema sugereaza ca putem calcula acest numar de triunghiuri (nedegenerate) care au toate laturile de aceeasi culoare (fie toate rosii, fie toate negre) doar in dependenta de c1, c2, ... , cN.

Am inteles bine?


---
df (gauss)
Blaugranas
Grup: membru
Mesaje: 69
09 Oct 2012, 22:17

[Trimite mesaj privat]


1. Pai eu vreau triunghiurile nemonocromatice nu monocromatice.
Observatie: Toate muchiile din graf sunt colorate ... fie in negru fie in rosu e graf complet... eu am zis doar pe alea in rosu... restul sunt muchii negre.
2. In rest e ok. Deci vreau numarul triunghiurilor nemonocromatice in functie de N,c1,c2,...,cN.

Euclid
Grup: Administrator
Mesaje: 2659
09 Oct 2012, 23:18

[Trimite mesaj privat]


Daca se numara pentru fiecare varf perechile de muchii de culori diferite si se aduna, am gasit dublul numarului de triunghiuri ne-monocromatice.


---
Euclid
gauss
Grup: Administrator
Mesaje: 6933
09 Oct 2012, 23:28

[Trimite mesaj privat]


EDIT: Tocmai am comis, am vazut apoi ca solutia simpla e cea de mai sus...



---
df (gauss)
Blaugranas
Grup: membru
Mesaje: 69
09 Oct 2012, 23:47

[Trimite mesaj privat]


Da avetzi ambii dreptate! Deci solutia este
daca am inteles bine de la amandoi. FELICITARI. V-a placut?

[1]


Legendă:  Access general  Conţine mesaje necitite  47488 membri, 58464 mesaje.
© 2007, 2008, 2009, 2010 Pro-Didactica.ρ