Grafuri

Curs
7.7/10 (3 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 16 în total
Cuvinte : 3289
Mărime: 19.49KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Pop Ion
teorie despre grafuri

Extras din document

SCURT ISTORIC AL TEORIEI GRAFURILOR

Originile teoriei grafurilor se gãsesc în rezolvarea unor probleme de jocuri si amuzamente matematice,care au atras atentia unor matematecieni de seama,cum ar fi:Euler,Hamilton,Cazlyley,Sylvester,Birkoff.

Data nasterii teoriei grafurilor este consideratã a fi anul 1736,cãnd matematicianul Leonhard Euler a publicat un articol în care a clarificat problema celor sapte poduri si a prezentat o metodã pentru rezolvarea altor probleme de acelasi tip.Articolul,în limba latinã,avea titlul:Solutio problematis ad geometriam situs pertinentis(Solutia unei probleme legate de geometria pozitiei) si a apãrut în revista Comentarii Academiae Scietiarum Imperialis Petropolitanae.

Cu 200 de ani mai tãrziu,în 1936,apãrarea la Leipzic prima carte de teoria grafurilor, al cãrui autor este matematicianul maghiar Denes Konig.(n

amintirea contributiei lui Euler,unele notiuni si tipuri de grafuri de care acesta s-a ocupat sunt denumite de cãtre Konig lant(ciclu) eulerian, graf eulerian , etc.

Un alt matematician care s-a ocupat de aceleasi probleme ca si Euler dar care si-a publicat rezultatele cercetãrilor sale în anul 1873, a fost Carl Hierholzer.Acesta a demonstrat în plus unele rezultate care lui Euler I se pãruse evidente.

(n 1851 articolul lui Euler a fost tradus si publicat în revista Nouvelles Annales de Mathematiques,iar rezultatele sale au fost îmbogatite, fiind studiate în clase speciale de grafuri.

Alte izvoare ale teoriei grafurilor sunt: studiul retelelor electrice , problema celor patru culori, aplicatiile teoriei grafurilor in chimie (initiate de Cayley), probleme hamiltoniene, grafuri planare, etc.

Fizicianul Kirchoff a studist la mijlocul secolului trecut retelele electrice cu metode care apartin astãzi teoriei grafurilor, contribuind la dezvoltarea acestei teorii.

Termenul de graf a fost folosit prima data in sensul sãu actual (fiind derivat din termenul notiune graficã din chimie) într-un articol publicat în 1878 de matematicianul J.Sylvester, articol ce a apãrut în primul numãr al revistei American Journal of Mathematics.Teoria grafurilor are numeroase aplicatii în chimie, cercetãri privind determinarea numului de izomeri ai compusilor organici contribuind în mare mãsurã la rezolvarea problemelor de numare a grafurilor apartind unor clase speciale.

,, Azi teoria grafurilor a devenit o disciplinã majorã, desi nu-si gãseste locul într-o clasificare dogmatica a capitolelor matematicii.

Folosirea teoriei grafurilor în domenii variate, de la chimie la economie, de la studiul retelelor electrice la critica textelor si la politicã, îi dau azi un prestigiu de care cel ce clasificã stintele trebuie sã tinã seama,,

(Grigore C. Moisil)

GRAFURI NEORIENTATE

NOTIUNI INTRODUCTIVE

Definitia.Se numeste graf neorientat o pereche ordonatã de multimi(X,U),X fiind o multime finitã si nevidã de elemente numite noduri sau vãrfuri , iar U o multime de perechi neordonate din X , numite muchii.

Vom nota cu G=(X,U) un graf neorientat.Multimea X se numeste multimea nodurilor sau vãrfurilor grafului G iar U,multimea muchiilor.

O muchie uU este deci o submultime (x,y) de vãrfuri distincte din X si se noteazã u=(x,y).Vom spune despre vãrfutile x si y cã sunt adiacente în G iar despre u si x cã sunt incidente la fel ca si u si x .Se mai spune cã x si y sunt extremitãtile muchiei u.

Dacã u1 si u2 sunt douã muchii care au o extremitate comunã, ele vor fi numite deasemenea incidente.

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
Grafuri - Pagina 15
Grafuri - Pagina 16

Conținut arhivă zip

  • Grafuri.DOC

Alții au mai descărcat ș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...

Metoda Backtracking

Metoda backtracking se utilizeaza pentru rezolvarea unor probleme in care: - se obtin mai multe solutii; -solutia este formata din unul sau mai...

Algoritmica Grafurilor

Curs 1 1.Notatii.Definitii Multiset – S multime finita, S!=VID R=(S,r) r:S->N³0, r=functie multiplicitate r:S->{0,1} => def partilor lui S (R)...

Sisteme de Prelucrare Grafică

Curs nr. 1 Evolutia graficii: Se pot distinge mai multe etape: - grafica simpla care sa fie printata; - modele sau obiecte care trebuiau...

Curs Practic HTML

Culoarea de fond O culoare poate fi precizata in doua moduri: Printr-un nume de culoare.Sunt disponibile cel putin 16 nume de culori: aqua,...

Ai nevoie de altceva?