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

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

CNAA / Teze / 2017 / martie /

Acoperirea cu mulțimi d-convexe a grafurilor neorientate


Autor: Buzatu Radu
Gradul:doctor în Matematica
Specialitatea: 01.01.09 - Cibernetică matematică şi cercetări operaţionale
Anul:2017
Conducător ştiinţific: Sergiu Cataranciuc
doctor habilitat, profesor universitar, Universitatea de Stat din Moldova
Instituţia: Universitatea de Stat din Moldova

Statut

Teza a fost susţinută pe 23 martie 2017 în CSS
şi aprobată de CNAA pe 31 mai 2017

Autoreferat

Adobe PDF document – 0.76 Mb / în română

Teza

CZU 519.83

Adobe PDF document 3.58 Mb / în română
149 pagini

Cuvinte Cheie

Graf neorientat, d-convexitate, mulțime d-convexă, segment metric, învelitoare d-convexă, problemă de optimizare, acoperire d-convexă, divizare d-convexă, NP-completitudine, arbore, algoritm

Adnotare

Structura tezei. Teza este scrisă în limba română și conține introducere, trei capitole, concluzii generale și recomandări, bibliografie ce cuprinde 115 de titluri. Lucrarea conține 122 pagini text de bază. Rezultatele obținute sunt publicate în 12 lucrări științifice.

Domeniul de studiu al tezei: Teoria grafurilor

Scopul și obiectivele lucrării. Scopul urmărit prin realizarea tezei constă în studierea și soluționarea problemei de acoperire a unui graf neorientat cu mulțimi d-convexe. Pentru atingerea scopului sunt fixate următoarele obiective: examinarea complexității problemei de acoperire a grafului cu un număr p2 de mulțimi d-convexe; stabilirea condițiilor de existență a unei familii de mulțimi d-convexe, ce formează o acoperire a grafului neorientat; soluționarea problemei de acoperire a grafului cu mulțimi d-convexe netriviale; elaborarea algoritmilor pentru problema de acoperire/divizare a grafului cu mulțimi d-convexe; estimarea numărului de acoperire d-convexă minimă/maximă.

Noutatea și originalitatea științifică constă în obținerea rezultatelor noi de ordin teoretico-aplicativ, grație cărora au fost completate și generalizate cele cunoscute în literatura de specialitate cu referire la problema acoperiri grafului cu mulțimi d-convexe, și demonstrarea că problema în cauză, împreună cu unele variații, este o problemă NP-completă.

Problema științifică importantă soluționată constă în demonstrarea NP-completitudinii problemei de acoperire/divizare a unui graf neorientat cu mulțimi d-convexe, ceea ce a condus la necesitatea studierii condițiilor de existență a p  2 mulțimi d-convexe, ce formează acoperire/divizare unor clase de grafuri pentru implementarea ulterioară în construirea metodelor și algoritmilor eficienți de soluționare a problemelor aplicative.

Semnificația teoretică este determinată de obținerea rezultatelor ce țin de stabilirea NP-completitudinii problemei de acoperire a unui graf cu două mulțimi d-convexe, prin care se completează rezultatele obținute de către alți matematicieni. S-a demonstrat că problema acoperirii grafului cu 2p mulțimi d-convexe, atât în caz general cât și în cazul mulțimilor d-convexe netriviale, este o problemă NP-completă.

Valoare aplicativă constă în posibilitatea utilizării rezultatelor obținute la studierea mulțimilor d-convexe pe structuri discrete, elaborarea algoritmilor pentru problemele de acoperire/divizare a unui graf cu mulțimi d-convexe, ce pot fi folosite la soluționarea problemelor practice, de exemplu probleme de clusterizare a elementelor unei mulțimi pe care sunt definite relații binare.

Implementarea rezultatelor științifice. Rezultatele obținute pot servi drept suport pentru unele cursuri opționale, ce țin de soluționarea problemelor de optimizare pe structuri discrete, pentru studenții și masteranzii universităților. Algoritmii elaborați sunt realizați sub formă de bibliotecă de algoritmi implementată în limbajul C#.

Cuprins


1. EVOLUȚIA CERCETĂRILOR ÎN SOLUȚIONAREA PROBLEMEI DE ACOPERIRE PE STRUCTURI DISCRETE
  • 1.1. Rolul structurilor discrete la soluționarea problemelor teoretico-aplicative
  • 1.2. Convexitatea generalizată și d-convexitatea în grafurile neorientate
  • 1.3. Estimarea complexității problemelor combinatoriale
  • 1.4. Originea problemei de acoperire d-convexă a grafurilor neorientate
  • 1.5. Concluzii la capitolul 1

2. ACOPERIREA GRAFURILOR CU MULȚIMI d-CONVEXE
  • 2.1. Acoperiri d-convexe și caracteristici numerice
  • 2.2. Cazul acoperirii grafului neorientat cu 2p mulțimi d-convexe
  • 2.3. Problema de (2,t)-acoperire și (2,nt)-acoperire d-convexă
  • 2.4. Problema de acoperire/divizare d-convexă netrivială
  • 2.5. Concluzii la capitolul 2

3. PROBLEMA DE ACOPERIRE CONVEXĂ PENTRU CLASE SPECIALE DE GRAFURI
  • 3.1. Acoperirea grafurilor cu două mulțimi d-convexe netriviale
  • 3.2. Acoperirea unui arbore cu mulțimi d-convexe netriviale
  • 3.3. Divizarea unui arbore în mulțimi d-convexe netriviale
  • 3.4. Acoperirea d-convexă minimă pentru grafuri speciale
  • 3.5. Concluzii la capitolul 3

CONCLUZII GENERALE ȘI RECOMANDĂRI