Comisia de atestare
Comisia de acreditare
Comisiile de experţi
Dispoziţii, instrucţiuni
Acte normative
Nomenclator
Instituţii
Consilii
Seminare
Teze
Conducători de doctorat
Deţinători de grad
Doctoranzi
Postdoctoranzi
CNAA logo

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


Grafuri cu mulţimi d-convexe apriori date


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, conferenţiar universitar, Universitatea de Stat din Moldova
Instituţia: Universitatea de Stat din Moldova
CSS: DH 30-01.01.09
Universitatea de Stat din Moldova

Statut

Teza a fost susţinută pe 23 decembrie 2008 în CSS
şi aprobată de CNAA pe 26 februarie 2009

Autoreferat

Adobe PDF document0.26 Mb / în română

Cuvinte Cheie

amplasarea(scufundarea) grafurilor, d-segment neorientat, d-segment orientat, graf d-convex simplu neorientat, graf d-convex simplu orientat, graf d-convex quasi-simplu neorientat, învelitoare d-convexă, mulţime d-convexă, vârf anticopie, vârf copie.

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


CAPITOLUL 1. Grafuri d-Convex Simple Neorientate
  • 1.1 Concepte Preliminare
  • 1.2 O Metodă Iterativă de Descriere a Grafurilor d-Convex Simple Neorientate
  • 1.3 Operaţii Algebrice în Mulţimea Grafurilor d-Convex Simple Neorientate
  • 1.4 Extinderi de Clase de Grafuri d-Convex Simple Neorientate
  • 1.5 Mulţimi Inchise şi Complete. Generatori de Clase de Grafuri d-Convex Simple
  • 1.6 Grafuri d-Convex Simple Bipartite cu Numărul de Vârfuri şi Muchii Fixate
  • 1.7 Raza şi Diametrul în Grafurile d-Convex Simple Neorientate L(G, G0)
  • 1.8 Amplasarea Grafurilor d-Convex Simple Planare în R3

CAPITOLUL 2. Grafuri d-convex quasi-simple neorientate
  • 2.1 O Metodă Iterativă de Descriere a Grafurilor d-Convex Quasi-Simple Neorientate
  • 2.2 Operat¸ii Algebrice în Mulţimea Grafurilor d-Convex Quasi-Simple Neorientate
  • 2.3 Clase de Grafuri d-Convex Quasi-Simple
  • 2.4 Amplasarea Grafurilor d-Convex Quasi-Simple Planare în R3

CAPITOLUL 3. Grafuri d-Convex Simple Orientate
  • 3.1 O Metodă Iterativă de Descriere a Grafurilor d-Convex Simple Orientate
  • 3.2 Operaţii Asupra Grafurilor d-Convex Simple Orientate
  • 3.3 Relaţia dintre Grafurile d-Convex Simple Orientate şi Grafurile d-Convex Simple Neorientate.