Previzualizare referat:

Extras din referat:

Def: Se numeste graf neorientat o pereche ordonata g= (X, U) , unde X este o multime finita si nevida cu elemente numite noduri sau varfuri, iar U este o multime de perechi neordonate din X numite muchii.

Teorema: In orice graf (X, U) suma gradelor varfurilor este de doua ori numarul de muchii, adica ?d (x) =d (x1) +d (x2) + +d (xn) =2*m, x ? X, m-nr de muchii, n-nr de varfuri.

Dem: Fiecare muchie (x, y) contribuie cu o unitate la gradul lui x si cu o unitate la gradul lui y=>contribuie cu 2 unitati la suma gradelor, si atunci fiind m muchii inseamna ca suma gradelor este de 2 ori nr de muchii.

Reprezentarea grafurilor neorientate 1. Cu ajutorul matricei de adiacenta (matricei adiacente). A ? M (m, n), n-nr de varfuri, m-nr de muchii., unde A (i, j) =1, daca exista muchia (i, j) 0, daca nu exista OBS! Matricea de adiacenta este simetrica fata de diagonala principala: A (i, j) =A (j, i). OBS! Gradul unui varf x se poate determina calculand suma pe linia x.

Citirea unui graf memorat cu ajutorul matricei de adiacenta!

Varianta 1: Citirea numarului de varfuri, citirea regiunii de deasupra diagonalei principale urmata de simetrizare.

var a: array[1. 120, 1. 120] of 0. 1; x, d, i, j, n: byte; begin write (nr de varfuri: =); readln (n); for i: =1 to n-1 do for j: =i+1 to n do begin write (a[, i, , , j,]: =); readln (a[i, j]); a[j, i]: =a[i, j]; end; end.

Varianta 2: Se citesc n-nr de varfuri, m-nr de muchii; -initializarea matricei de adiacenta cu zero; -citirea extremitatii fiecarei muchii; -completarea matricei de adiacenta.

var a: array[1. 120, 1. 120] of 0. 1; x, d, i, j, n: byte; begin write (n: =); readln (n); write (m: =); readln (m); for i: =1 to n do for j: =1 to n do a[i, j]: =0; for i: =1 to m do begin writeln (Muchia, i, este: ); readln (x, y); a[x, y]: =1; a[y, x]: =1; end; end.

Cate grafuri neorientate cu n varfuri exista?

R: 2 la C din n luate cate 2. Graf partial si subgraf Def! Fie graful G= (X, U). Un graf partial al lui G, este un graf G1= (X, V) , cu V=U (inclus). Altfel spus, un graf partial se obtine pastrand toate varfurile si eliminand niste muchii.

Def! Fie graful G= (X, U). Un subgraf al lui G, este un graf S= (Y, T), unde Y=X si T=V, iar T va contine numai acele muchii care au ambele extremitati in Y.

Altfel spus, un subgraf S al lui G se obtine din G eliminand niste varfuri si odata cu acestea acele muchii care au cel putin o extremitate in submultimea eliminata.

Graf complet si graf bipartit Se numeste graf complet cu n varfuri, notat K indice n (Kn), un graf G= (X, U) cu proprietatea ca oricare doua varfuri sunt adiacente, adica oricare cuplu x, y ? X, esista muchia [x, y] ? U.

Teorema! Un graf complet cu n varfuri are n (n-1) /2 muchii.

Definitie! Se numeste graf bipartit, un graf G= (X, U) cu proprietatea ca exista doua multimi distincte A si B incluse in X, astefel incat: -AnB=multime vida, A+B=X. (+ este reunit); -toate muchiile grafului au o extremitate in A si cealalta in B.

Definitie! Se ...

Download referat

Primești referatul în câteva minute,
cu sau fără cont

Alte informații:
Tipuri fișiere:
doc
Diacritice:
Nu
Nr fișiere:
1 fisier
Pagini (total):
29 pagini
Imagini extrase:
29 imagini
Nr cuvinte:
4 431 cuvinte
Nr caractere:
21 395 caractere
Marime:
24.84 KB (arhivat)
Nivel studiu:
Liceu
Tip document:
Referat
Materie:
Informatica
Tag-uri:
grafuri, programare
Data publicare:
26.12.2009
Structură de fișiere:
  • Grafuri - Varianta 2
    • Referat.doc
Predat:
la liceu
Te-ar putea interesa și:
Un graf orientat reprezinta o pereche ordonata de multimi G=(X,U), unde X este o multime finita...
GRAFURI. TRAVERSARI PE GRAFURI Definitie: Fie G = (V, E) o multime, in care V 3/4 este o...
SCURT ISTORIC AL TEORIEI GRAFURILOR Originile teoriei grafurilor se gasesc in rezolvarea unor...
In informatica grafurile pot fi: neorientate si orientate.Un graf neorientat G este o pereche...
Definitii - Se numeste graf sau graf neorientat o structura G=(V,E), unde V este o multime...
Sus!