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...

Laborator SDA

LISTE SIMPLU ÎNLANTUITE 1. Continutul lucrarii În lucrare sunt prezentate operatiile importante asupra listelor simplu înlantuite si...

AutoCad

APERTURE - controleazã mãrimea cursorului selector, caracteristic modului object snap. ARC - traseazã un arc de cerc de orice dimensiune. A -...

Grafuri Orientate

Un graf orientat G este format dintr-o pereche ordonata de multimi G=(X,U). ca si in cazul grafurilor neorientate, X este multimea varfurilor sau...

Biblioteca de Șabloane Standard

Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala...

Clase Derivate

1. Clase derivate. Prin mostenire, atributele unei clase de baza sunt transmise unor clase derivate. Derivarea permite definirea unor clase noi,...

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?