Grafuri neorientate

2x puncte

categorie: Informatica

nota: 9.15

nivel: Liceu

Graf = orice mulțime finită V prevăzută cu o relație binară internă E. Notăm graful cu G=(V, E).

Graf neorientat = un graf G=(V, E) în care relația binară este simetrică: (v,w)ÎE atunci (w,v) ÎE.

Nod = element al mulțimii V, unde G=(V, E) este un graf neorientat.

Muchie = element al mulțimii E ce descrie o relație existentă între două vârfuri din V[...]
DOWNLOAD REFERAT

Preview referat: Grafuri neorientate

Graf = orice mulțime finită V prevăzută cu o relație binară internă E. Notăm graful cu G=(V, E).

Graf neorientat = un graf G=(V, E) în care relația binară este simetrică: (v,w)ÎE atunci (w,v) ÎE.

Nod = element al mulțimii V, unde G=(V, E) este un graf neorientat.

Muchie = element al mulțimii E ce descrie o relație existentă între două vârfuri din V, unde G=(V, E) este un graf neorientat;

In figura alaturata:
V={1,2,3,4,5,6} sunt noduri
E={[1,2], [1,4], [2,3],[3,4],[3,5]} sunt muchii
G=(V, E)=({1,2,3,4,5,6}, {[1,2], [1,4], [2,3],[3,4],[3,5]})


Adiacenta: Într-un graf neorientat existența muchiei (v,w) presupune că w este adiacent cu v și v adiacent cu w.
În exemplul din figura de mai sus vârful 1 este adiacent cu 4 dar 1 și 3 nu reprezintă o pereche de vârfuri adiacente.

Incidență = o muchie este incidentă cu un nod dacă îl are pe acesta ca extremitate. Muchia (v,w) este incidentă în nodul v respectiv w.

Grad = Gradul unui nod v, dintr-un graf neorientat, este un număr natural ce reprezintă numărul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv)

Nod izolat = Un nod cu gradul 0.

Nod terminal= un nod cu gradul 1

Nodul 5 este terminal (gradul 1).

Nodul 6 este izolat (gradul 0)

Nodurile 1, 2, 4 au gradele egale cu 2.


Lanț = este o secvență de noduri ale unui graf neorientat G=(V,E), cu proprietatea că oricare două noduri consecutive din lant sunt adiacente:
L=[w1, w2, w3,. . ,wn] cu proprietatea că (wi, wi+1)ÎE pentru 1Łi
Lungimea unui lanț = numărul de muchii din care este format.

Lanț simplu = lanțul care conține numai muchii distincte

Lanț compus= lanțul care nu este format numai din muchii distincte

Lanț elementar = lanțul care conține numai noduri distincte

Ciclu = Un lanț în care primul nod coincide cu ultimul.

Ciclul este elementar dacă este format doar din noduri distincte, excepție făcând primul și ultimul. Lungimea unui ciclu nu poate fi 2.


Succesiunea de vârfuri 2, 3, 5, 6 reprezintă un lanț simplu și elementar de lungime 3.
Lanțul 5 3 4 5 6 este simplu dar nu este elementar.
Lanțul 5 3 4 5 3 2 este compus și nu este elementar.
Lanțul 3 4 5 3 reprezintă un ciclu elementar

Graf partial = Dacă dintr-un graf G=(V,E) se suprimă cel puțin o muchie atunci noul graf G’=(V,E’), E’Ì E se numește graf parțial al lui G.

G G1 este graf partial al lui G

Subgraf = Dacă dintr-un graf G=(V,E) se suprimă cel puțin un nod împreună cu muchiile incidente lui, atunci noul graf G’=(V’,E’), E’Ì E si V’ÌV se numește subgraf al lui G.
G G1 este subgraf al lui G

Graf regulat = graf neorientat în care toate nodurile au același grad;
« mai multe referate din Informatica

CAUTA REFERAT

TRIMITE REFERAT CERE REFERAT
Referatele si lucrarile oferite de E-referate.ro au scop educativ si orientativ pentru cercetare academica.
Confidentialitatea ta este importanta pentru noi

E-referate.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat termenii si conditiile de utilizare pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles