Buna seara
Am si eu patru probleme din grafuri.
Stiu ca poate deranjul este prea mare si nu intra in domeniul Dvs.dar m-am gandit sa incerc si eu la Dvs.(suntem doi colegi fiecare avem cate doua probleme).
Deci ne-am gandit sa incercam.
Pentru o cerecta redactare a problemelor ne-am gandit sa va trimitem SITE-urile cu problemele respective si cu ucrsul respectiv si anume:
http://profs.info.uaic.ro/~croitoru/ag/ag%2013-14%20allinone.pdf
http://profs.info.uaic.ro/~croitoru/ag/homework1.pdf
Imi cer scuze de deranj daca puteti sa ne ajutati ?Bineinteles daca intra in domeniul Dvs.
Multumiri!

http://profs.info.uaic.ro/~croitoru/ag/homework1.pdf
Tocmai am citit prima problema.
Bun, nu am avut timp sa o rezolv, dar de fapt nu sunt eu cel ce trebuie sa o rezolve. Sa incercam sa o rezolvam de aceea pe un caz particular, ca sa vedem care sunt problemele.
Propun sa ne uitam la graful cu varfurile
1,2,3,4, 1a,1b,1c, 2a,2b,2c, 3a,3b,3c
in care 1,2,3,4 sunt unite in cerc (un patrat cu latruile 1-2, 2-3, 3-4, 4-1)
si in care din fiecare varf pleaca radial
1-1a-1b-1c
2-2a-2b-2c
3-3a-3b-3c
4-4a-4b-4c .

Ce vrea problema de la noi in acest caz.

Am aranjat mai sus sa avem doar un ciclu.
Aceeasi problema daca avem 1,2,3,4 subgraf complet, deci avem si diagonalele 1-3 si 2-4.

Nota: Rezolvarea de cazuri particulare este parte din problemele de grafuri.
Explicarea solutiei este deseori imposibila fara a avea exemplele de grafuri in care o anumita constructie / solutie "e neasteptata".

Nota: Matematica a luat-o razna oricum - stiu de cand cu olimpiadele, dar informatica face pasi giganti pentru a o ajunge din urma.

Multumesc pentru intentie
Totusi poate aveti timp sa incercati o rezolvare?
Daca bineinteles intra in domeniul Dvs de activitate

Pai pentru a vedea unde e problema, trebuie sa rezolvam problema pe cazul banal prezentat mai sus. Am uitat sa orientez graful...
Il iau cu una din cele cateva orientari ale ciclului cu varfurile 1,2,3,4 si celelalte laturi de la ciclu spre in afara.

Nota:
Un om "normal" nu vorbeste despre o partitie in S si T ci eventual despre o colorare in doua culori, de exemplu Senin si Tulburat.
Ce vrea problema de la noi in acesti termeni?
(Trebuie sa fie in primul rand clar ce vrea enuntzul de la noi...)

Pai nu ma descurc.
Daca este posibil sa imi aratati cum se rezolva problemele?Eu nu inteleg!

Multumiri

?i, în general, dac? a?i putea s? ne scrie?i direct rezolv?rile, f?r? întreb?ri din astea, la mi?to, ar fi grozav.

Mul?umim anticipat

Eu nu inteleg ce ati vrut sa spuneti dar oricum pentru a nu va supara renunt la a va mai cere rezolvarile respective
Cu stima

Renuntzarea chiar aici cred ca nu e buna.
Sa mai incercam macar o data.

Mai sus avem un mic graf cu cateva varfuri (vertices) si cu cateva laturi (edges) orientate.
Putem colora cumva varfurile in culorile S si T (toate varfurile se coloreaza, fiecare varf primeste exact o culoare, fie S, fie T), astfel incat macar o patrime din laturile orientate sa plece dintr-o culoare si sa ajunga in cealalta?

(In cazul de mai sus putem face mult mai bine decat o patrime. Idea mea era de a vedea solutia in acest caz simplu, apoi de a mai "umple imaginea cu mai multe laturi" care sa nu schimbe culoarea fata de solutia gasita, atat de multe laturi noi, pana ce colorarea nu mai e buna si poate ca trebuie sa o schimbam. In noua situatie trebuie desigur sa ne reorientam si sa gasim o strategie. Fie de ajustare a colorarii, fie poate o strategie complet noua.)

Pe marginea acestei probleme putem pune cateva intrebari,
ne raportam activ cu propria fantazie pe marginea unei probleme pe care o avem acum in limbaj de clasa a IV-a (nu exagerez, am vazut astfel de probleme propuse pentru a IV-a si a V-a, in cazul de fatza motivul pentru care problema este una de a V-a este faptul ca... impartim la patru pe drum, dar altfel stiu cativa autori de probleme care dupa indelungate eforturi de simplificat solutia proprie greu gasita o declara accesibila pentru gimnaziu, in definitiv pe a II-a s-a invatat lucrul manual cu creioane colorate si plastilina).

O prima intrebare: Conteaza faptul ca avem un graf orientat? In ce masura?

Alte intrebari:

Daca luam un graf complet, neorientat, fiecare varf este legat de fiecare varf cu exact o latura, cum coloram incat sa rezolvam cerintele problemei?

Care sunt caracteristicile unui graf care "ne face probleme"? (Intrebare nematematica, dar tematica, ne ajuta sa cautam solutia problemei, deoarece stim sa ne construim exemple cu caracteristici critice...)

Daca avem trei multimi de puncte, A, B, C si unim cu cate o latura
fiecare varf in A cu fiecare din B,
fiecare varf in B cu fiecare din C,
fiecare varf in C cu fiecare din A,
care este solutia?

In ce cazuri nu putem face "mai bine de o patrime", exista grafuri cu numari mic de varfuri in care sa mergem la cazul limita?

Nota: Nu punerea de intrebari ne supara, ci renuntarea la orice efort de gandire, de raportare activa la problema propusa. Daca -- sa zicem -- vine solutia, cum o percepe creierul daca nu are nici cel mai mic suport intuitiv? Care este sensul parcurgerii unei astfel de solutii? Nu ne aflam cu problema intr-o situatie complicata a unei integrale care merge atacata doar printr-o substitutie si noi trebuie sa stim substitutia, in asa cazuri am da imediat substitutia, ci ne aflam in cadrul unei structruri simple, structura care apare asa sau analog in programare, in cautarea de algoritmi, in etablarea unui mod schematic de organizare... Aici incercarea de rezolvare conteaza cel mai mult, solutia este inutila, conduce doar la o nota buna. Foarte probabil in situatia in care profesorul stie bine daca solutia e copiata sau gandita/digerata.
Ese posibil ca o solutie perfecta sa primeasca nota 10, dar nu se creaza nici un fel de legatura umana, daca as fi eu la catedra m-as bucura de o solutie "umpluta de sange" care se termina undeva cu sau fara rezultat partial. Poate ca solutia primeste nota 5 sau 6, dar din propozitiile scrise cel ce corecteaza stie cum gandeste cel ce a incercat sa solutioneze, data viitoare va face intr-o situatie asemanatoare legatura, va face o aluzie sau o observatie, acel punct de rationament se impregneaza si mai bine. Daca nu, e ca si cum avem doua multimi disjuncte, totul merge dupa motto-ul "Unii predau, altii redau, dar nu dau unii de altii"...

Buna ziua
Va multumesc foarte mult pentru raspunsul primit dar problema nu mai este de actualitate pentru mine.
Voi cerceta totusi cu atentie toate cele aratate de Dvs care imi vor fi utile in viitor