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


Grafuri tranzitiv orientabile


Autor: Grigoriu Nicolae
Gradul:doctor în ştiinţe fizico-matematice
Specialitatea: 01.01.09 - Cibernetică matematică şi cercetări operaţionale
Anul:2016
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 13 aprilie 2016 în CSS
şi aprobată de CNAA pe 3 iunie 2016

Autoreferat

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

Teza

CZU 519.83

Adobe PDF document 2.13 Mb / în română
143 pagini

Cuvinte Cheie

graf tranzitiv orientabil, subgraf stabil, lanț netriangulat, graf factor, orientare tranzitivă, graf de comparabilitate

Adnotare

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

Scopul și obiectivele lucrării. Caracterizarea structurală a grafurilor tranzitiv orientabile și elaborarea în baza acesteia a algoritmilor de construire a orientărilor tranzitive pentru grafurile neorientate cu restricții asupra muchiilor. Obiective: determinarea rolului lanțurilor netriangulate în construirea orientărilor tranzitive a grafurilor; examinarea proprietăților subgrafurilor B-stabile și rolul acestora la construirea grafurilor factor; studierea șirului complet de grafuri factor pentru descrierea problemei orientărilor tranzitive ale unui graf neorientat; determinarea formulei recurente de calcul a numărului de orientări tranzitive ale grafului; elaborarea algoritmilor pentru construirea orientărilor tranzitive cu restricții asupra muchiilor orientabile.

Noutatea și originalitatea științifică constă în studierea unei clase noi de grafuri stabile și construirea în baza proprietăților acestora a șirului complet de grafuri factor, folosit la soluționarea problemei orientării tranzitive a grafurilor neorientate, precum și la soluționarea problemei de enumerare a acestor orientări prin deducerea unei formule recurente.

Problema științifică importantă soluționată constă în determinarea unei clase de subgrafuri stabile folosite la studierea problemei de orientare tranzitivă și caracterizarea structurală a grafurilor tranzitiv orientabile, care au condus la obținerea unei metode eficiente pentru construirea orientărilor tranzitive și calcularea numărului acestor orientări.

Semnificația teoretică este determinată de obținerea unei caracterizări structurale a grafurilor tranzitiv orientabile. Se propune o metodă eficientă de studiere a orientărilor tranzitive în baza unui șir complet de grafuri factor.

Valoare aplicativă. Se propun algoritmi de construire a orientărilor tranzitive ale unui graf neorientat ce completează aspectul aplicativ al problemei studiate la soluționarea problemelor practice: testarea codului sursă al programelor, decompoziția rețelelor Petri, etc.

Implementarea rezultatelor științifice. Rezultatele obținute pot servi pentru inițierea unor cercetări în domeniu pentru studenții și masteranzii universităților, pot servi drept suport pentru unele cursuri opționale, pentru soluționarea problemelor practice. Algoritmii elaborați sunt realizați sub formă de programe în limbajul Javascript.

Cuprins


1. EVOLUȚIA CERCETĂRILOR ÎN DOMENIUL STUDIERII GRAFURILOR TRANZITIV ORIENTABILE ȘI ASPECTELE APLICATIVE ALE ACESTORA
  • 1.1. Rolul grafurilor în soluționarea problemelor teoretico-aplicative
  • 1.2. Grafurile de comparabilitate a mulțimilor parțial ordonate
  • 1.3. Clase de implicații și orientarea tranzitivă a grafurilor
  • 1.4. Aplicații ale grafurilor tranzitiv orientabile
  • 1.5. Concluzii la capitolul 1

2. ORIENTAREA TRANZITIVĂ A GRAFURILOR NEORIENTATE
  • 2.1. Subgrafuri stabile și lanțuri netriangulate
  • 2.2. Subgrafuri B-stabile
  • 2.3. Construirea orientărilor tranzitive
  • 2.4. Numărul de orientări tranzitive
  • 2.5. Concluzii la capitolul 2

3. GENERALIZĂRI ALE PROBLEMEI ORIENTĂRII TRANZITIVE A GRAFULUI
  • 3.1. Reorientarea unei mulțimi minimale de arce într-o orientare tranzitivă a grafului
  • 3.2. Reorientarea tranzitivă a grafului forțată de un arc apriori dat
  • 3.3. Reorientarea tranzitivă a grafului forțată de o mulțime de arce apriori dată
  • 3.4. Construirea unei orientări tranzitive având un arc dat
  • 3.5. Construirea unei orientări tranzitive având o mulțime de arce date
  • 3.6. Concluzii la capitolul 3

CONCLUZII GENERALE ȘI RECOMANDĂRI