Grafuri

Referat
8/10 (2 voturi)
Conține 1 fișier: doc
Pagini : 14 în total
Cuvinte : 2115
Mărime: 33.08KB (arhivat)
Publicat de: Noemi Nechita
Puncte necesare: 6

Extras din referat

In informatica grafurile pot fi: neorientate si orientate.Un graf neorientat G este o pereche ordonata de multimi (X,U),unde X este o multime finita, iar U este formata din perechi neordonate de elemente din X. Vom nota G=(X,U).

Multimea X se numeste multimea vârfurilor sau a nodurilor grafului G si multimea U se numeste multimea muchiilor grafului G.

O muchie, fiind un element din U, ea este o multime cu doua elemente din X, deci are forma {x,y},unde x,y sunt din X.Vom nota muchia {x,y} prin [x,y] si spunem ca ea uneste vârfurile x si y.

Tipurile de grafuri neorientate sunt:

-graf partial;

-subgraf;

-graf complet;

-graf bipartit;

-graf bipartit complet;

Un graf partial al unui graf G=(X,Y) este un graf G1=(X,V), care are aceeasi multime de vârfuri cu G, iar VU.

Un subgraf al unui graf G=(X,U) este un graf U=(Y,V),unde YX, iar muchiile din multimea V sunt toate muchiile din U, care au ambele extremitati in multimea de vârfuri Y.

Un graf complet cu n vârfuri si care se noteaza cu Kn este un graf pentru care oricare doua vârfuri sunt adiacente.

Un graf G se numeste graf bipartit daca exista o partitie a multimilor vârfurilor, astfel încât fiecare muchie a grafului uneste un vârf din X1 cu un vârf din Xn.

Un graf orientat G este format dintr-o pereche ordonata de multimi G=(X,U),unde X este multimea vârfurilor sau a nodurilor grafului.Multimea U este formata din perechi ordonata de elemente distincte din X, numite arce. Orice arc u din U va fi notat prin u=(x,y), cu x,y din X si x<>y.

Tipuri de grafuri orientate sunt:

-graf partial;

-subgraf;

-graf complet;

Un graf partial al unui graf orientat G=(X,U) se defineste in acelasi mod ca si in cazul celui neorientat.El este un graf G=(X,V), unde VU, deci este graful G insusi sau se obtine din G prin suprimarea anumitor arce.

Un subgraf al lui G este un graf H=(Y,V) unde YX, iar arcele din V sunt toate arcele din U, care au ambele extremitati in multimea de vârfuri Y. Deci, un subgraf H al unui graf orientat G este graful G insusi sau se obtine din G prin suprimarea anumitor vârfuri si a tuturor arcelor incidente cu acestea. Vom spune ca subgraful H este indus sau generat de multimea de vârfuri Y.

Un graf orientat este complet daca oricare doua vârfuri sunt adiacente.

GRAFURI HAMILTONIENE

Grafurile Hamiltoniene sunt grafuri neorientate.

Un ciclu elementar al unui graf G care trece prin toate vârfurile grafului se numeste ciclu hamiltonian.

Un graf G care are un ciclu hamiltonian se numeste graf hamiltonian.

Originea acestui termen se gaseste intr-un joc inventat in anul 1857 de matematicianul William Hamilton.Partea sa principala este un dodecaedru regulat facut din lemn.

Acesta este un poliedru cu 12 fete care sunt toate pentagoane regulate, in fiecare din cele 20 de vârfuri se întâlnesc cate 3 muchii. Fiecare vârf al dodecaedrului lui Hamilton era marcat cu numele unui oras.Jocul consta in gasirea unui drum de-a lungul muchiilor dodecaedrului, care sa treaca prin fiecare din cele 20 de orase,exact la data si sa se întoarca in orasul din care a plecat.

Problema revine la gasirea unui ciclu hamiltonian in graful format cu vârfurile si muchiile dodecaedrului.O problema mai generala este aceea a voiajorului comercial, care are urmatorul enunt:

Preview document

Grafuri - Pagina 1
Grafuri - Pagina 2
Grafuri - Pagina 3
Grafuri - Pagina 4
Grafuri - Pagina 5
Grafuri - Pagina 6
Grafuri - Pagina 7
Grafuri - Pagina 8
Grafuri - Pagina 9
Grafuri - Pagina 10
Grafuri - Pagina 11
Grafuri - Pagina 12
Grafuri - Pagina 13
Grafuri - Pagina 14

Conținut arhivă zip

Alții au mai descărcat și

Grilă sisteme informaționale de gestiune - Access

Adăugarea de câmpuri la o tabelă se face în modul de vizualizare:...... Previzualizare inaintea imprimarii Aplicarea unei restrictii de...

Hackeri

Hackerii sunt pasionati ai informaticii, care, de obicei au ca scop „spargerea” anumitor coduri, baze de date, pagini web etc. Ei sunt considerati...

Baze de Date

3.Introducere in bd si sgbd-uri Definitie: Numim baza de date o colectie partajata de date aflata in interdependenta logica impreuna cu o...

Te-ar putea interesa și

Elemente de Teoria Grafurilor

INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...

Grafuri Neorientate - Euleriene

’’ Ideile, si daca sunt abstracte si daca nu, ca sa le poti manui, trebuie sa le ai. Calculatorul, ca sa-si faca treaba, trebuie sa inteleaga...

Grafuri Neorientate

GRAFURI NEORIENTATE NOTIUNI INTRODUCTIVE NOTIUNI DE BAZA DEFINITIE: Se numeste graf neorientat o pereche ordonata de multimi(X,U), X fiind o...

Grafuri Neorientate

Grafuri neorientate Definiţie. Se numeşte graf neorientat o pereche ordonată de mulţimi (X, U), X fiind o mulţime finită şi nevidă de elemente...

Grafuri Celebre

1. Introducere Numeroase situatii din viata cotidiana pot fi modelate cu ajutorul teoriei grafurilor. Teoria grafurilor este o importanta...

Manual Grafuri

1. Preliminarii 1.1. Algoritmi Toti algoritmii descrisi în cadrul acestei lucrari folosesc structuri de date de tip graf. Unele descrieri sînt...

Algoritmica grafurilor

Capitolul 1 INTRODUCERE Pentru noţiunile din acest paragraf am consultat Behzad, Chartrand, Foster, Croitoru, Olaru, Tomescu. Alte completări...

Ai nevoie de altceva?