română | русский | english

Autor: Nadejda Sur Gradul: doctor în ştiinţe fizico-matematice Specialitatea:  01.01.09 - Cibernetică matematică şi cercetări operaţionale Anul: 2009 Conducător ştiinţific: Sergiu Cataranciuc doctor habilitat, profesor universitar, Universitatea de Stat din Moldova Instituţia: CSS:

Statut Teza a fost susţinută pe 23 decembrie 2008 în CSS şi aprobată de CNAA pe 26 februarie 2009 Autoreferat – 0.26 Mb / în română Teza CZU 519.17 0.85 Mb / în română 111 pagini

Cuvinte Cheie

Adnotare

Teza este consacrată studiului d-convexităţii pe structuri discrete prin intermediul grafurilor, atât a celor neorientate cât şi a celor orientate.

Se rezolvă problema, apărută în anii 60-70 ai secolului trecut, de caracterizare a mulţimii de grafuri d-convex simple neorientate. Aceste grafuri sunt descrise printr-o metodă iterativă. Sunt introduse un şir de operaţii algebrice pe mulţimea grafurilor d-convex simple neorientate, care permit atât extinderea unor clase de grafuri cunoscute, cât şi depistarea unor grafuri primare, din care, cu ajutorul operaţiilor introduse se formează clase noi de grafuri d-convex simple. Astfel se determină structura grafurilor d-convex simple neorientate, ceea ce este important din punct de vedere al fundamentării teoriei convexităţii pe structuri discrete cât şi din punct de vedere aplicativ. Se demonstrează teorema de existenţă a grafurilor d-convex simple bipartite cu numărul de vârfuri şi muchii fixate. Se arată că problemele metrice, în grafurile d-convex simple de forma L(G, G0) se reduc la aceleaşi probleme în graful G. Se determină dimensiunea de scufundare în spaţiile Euclidiene a grafurilor d-convex simple planare şi se descrie algoritmul de scufundare a acestor grafuri în spaţiul respectiv.

Analogic cazului grafurilor d-convex simple, grafurile d-convex quasi-simple neorientate sunt descrise printr-o metodă iterativă. Se definesc toate operaţiile care au fost introduse pentru grafurile d-convex simple neorientate. Cu ajutorul lor, se face studiul pe clase speciale a mulţimii de grafuri d-convex quasi-simple şi se depistează generatorii pentru careva din clasele depistate. Se determină dimensiunea de scufundare în spaţiile Euclidiene a grafurilor d-convex quasi-simple planare şi se descrie algoritmul de scufundare a acestor grafuri în spaţiul respectiv.

Cu ajutorul noţiunii de distanţă, definită într-un mod obişnuit asupra grafurilor orientate, care este o semi-metrică pe această mulţime de grafuri, se defineşte noţiunea de mulţime d-convexă în grafurile orientate, noţiune care este în concordanţă cu axiomatica teoriei convexităţii. Se definesc grafurile d-convex simple orientate, ca grafurile cu un număr minim de mulţimi d-convexe. Grafurile d-convex simple orientate sunt descrise printr-o metodă iterativă. Operaţiile, care au fost definite deja pentru grafurile d-convex simple şi d-convex quasi-simple neorientate, la care se adaugă operaţia de transpoziţie şi operaţia L, sunt definite asupra grafurilor d-convex simple orientate. Se demonstrează că aceste operaţii sunt algebrice şi pe mulţimea grafurilor d-convex simple orientate. Toate acestea sunt necesare atât pentru a evidenţia structura grafurilor d-convex simple orientate şi modul de construcţie al lor, cât şi pentru a arătă că pentru orice graf d-convex simplu neorientat, structura căruia este cunoscută, există cel puţin un graf d-convex simplu orientat corespunzător lui, corespunderea fiind căutată în mulţimea orientărilor grafului neorientat iniţial. Astfel se poate de afirmat că mulţimea grafurilor d-convex simple orientate conţine, în acest sens, mulţimea grafurilor d-convex simple neorientate cunoscute.

Cuprins

Referenţi Oficiali

• Dumitru Lozovanu
  doctor habilitat, profesor universitar, Universitatea de Stat din Moldova
• Dumitru Zambiţchi
  doctor, conferenţiar universitar

 Teze

[...] Acte Normative