Grafuri

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.