Grafuri Neorientate Flashcards
(23 cards)
Cine este un vecin al until varf x?
Vârful y cu proprietatea ca exista muchie intre x si y
Ce înseamnă doua muchii incidente?
Au un varf comun
!OBS: un varf este incident cu o muchie dacă au o extremitate comună
Care sunt proprietățile unui grad?
— grad=0 => nod izolat
— grad=1 => nod terminal
— gradul maxim al unui varf este n-1
Care este teorema gradelor?
Suma gradelor tuturor vârfurilor este dublul numărului de muchii
Care sunt consecințele teoremei gradelor?
— suma gradelor tuturor vârfurilor este un număr par
— numărul de vârfuri de grad impar este întotdeauna par
Ce este un graf parțial?
Un graf cu aceleași vârfuri din care se elimina muchii
Ce este un graf complementar?
Un graf care are aceleași vârfuri si toate muchiile pe care graful inițial nu le are
Care sunt formulele pentru grafuri parțiale, subgrafuri si grafuri complementare?
— graful admite 2^m grafuri parțiale
— graful admite 2^n -1 subgrafuri
— graful are grad complementar unic
Care este formula pentru a afla numărul de grafuri neorientate distincte cu n varfuri?
2^ [n*(n-1)/2]
Ce este un graf regulat?
Un graf in care toate nodurile au același grad
Ce este un graf bipartit?
Un graf care, având două mulțimii A și B, are muchii formate doar intre elemente din mulțimi diferite.
Ce este un lanț?
O succesiune de vârfuri in care oricare doua vârfuri consecutive sunt adiacente
Ce este un lanț simplu si un lanț compus?
— simplu=numai muchii distincte
— compus=muchiile nu sunt distincte
Ce este un lanț elementar?
Lanț care conține numai varfuri distincte
Ce este un ciclu?
Un lanț simplu in care primul varf este identic cu ultimul
Ce este un ciclu elementar?
Un ciclu cu vârfuri distincte
Cum se afla lungimea unui ciclu?
Numărul de muchii din ciclu, lungime minima = 3
Ce este un graf conex?
Dacă exista cel puțin un lanț pentru oricare doua varfuri din graf
Ce este o componenta conexa?
O componenta a unui graf cu proprietatea ca nu exista nici un lanț care sa lege muchiile acesteia de alte vârfuri decât cele din interiorul componentei
Când este un graf biconex?
Graf conex si pentru orice care orice varf eliminat subgraful generat rămâne cu aceleași componente conexe.
Ce este un ciclu eulerian?
Ciclu cu toate muchiile grafului.
!OBS: muchiile nu se pot repeta, vf da
Ce este un ciclu eulerian?
Ciclu cu toate muchiile grafului.
!OBS: muchiile nu se pot repeta, vf da
Ce este un ciclu hamiltonian?
Ciclu cu toate vârfurile grafului
!OBS: vârfurile nu se pot repeta, muchiile da
