Grafuri hamiltoniene si trasabile

GRAFURI HAMILTONIENE SI TRASABILE




















CUPRINS:


INTRODUCERE
Scurt istoric al teoriei grafurilor

NOTIUNI INTRODUCTIVE
Un vocabular al teoriei grafurilor

GRAFURI ORIENTATE SI NEORIENTATE
Grafuri orientate
Grafuri neorientate


































CAPITOLUL 1

INTRODUCERE


1.1 SCURT ISTORIC AL TEORIEI GRAFURILOR


Originile teoriei grafurilor se g?sesc ?n rezolvarea unor probleme de jocuri ?i amuzamente matematice, care au atras aten?ia unor matematecieni de seama, cum ar fi: Euler, Hamilton, Cazlyley, Sylvester, Birkoff.
Data na?terii teoriei grafurilor este considerat? a fi anul 1736, c?nd matematicianul Leonhard Euler a publicat o lucrare numit?: Problema Podurilor din Königsberg, ?n care a clarificat problema celor ?apte poduri ?i a prezentat o metod? pentru rezolvarea altor probleme de acela?i tip. Articolul, ?n limba latin?, avea titlul: Solutio problematis and geometriam situs pertinentis (Solu?ia unei probleme legate de geometria pozi?iei) ?i a ap?rut ?n revista Comentarii Academiae Scietiarum Imperialis Petropolitanae.
Cu 200 de ani mai t?rziu, ?n 1936, ap?rea la Leipzic prima carte de teoria grafurilor, al c?rui autor este matematicianul maghiar Denes Konig. ?n amintirea contribu?iei lui Euler, unele no?iuni ?i tipuri de grafuri de care acesta s-a ocupat sunt denumite de c?tre Konig lan? (ciclu) eulerian, graf eulerian , etc.
Un alt matematician care s-a ocupat de acelea?i probleme ca ?i Euler dar care ?i-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 ?i publicat ?n revista Nouvelles Annales de Mathematiques, iar rezultatele sale au fost ?mbog??ite, fiind studiate ?n clase speciale de grafuri.
Alte izvoare ale teoriei grafurilor sunt: studiul re?elelor electrice, problema celor patru culori, aplica?iile teoriei grafurilor in chimie (ini?iate de Cayley), probleme hamiltoniene, grafuri planare, etc.
Fizicianul Kirchoff a studiat la mijlocul secolului trecut re?elele electrice cu metode care apar?in 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 no?iune 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 aplica?ii ?n chimie, cercet?ri privind determinarea num?rului de izomeri ai compu?ilor organici contribuind ?n mare m?sur? la rezolvarea problemelor de num?rare a grafurilor apar?in?nd unor clase speciale.


,, Azi teoria grafurilor a devenit o disciplin? major?, de?i nu-?i g?se?te locul ?ntr-o clasificare dogmatica a capitolelor matematicii.
Folosirea teoriei grafurilor ?n domenii variate, de la chimie la economie, de la studiul re?elelor electrice la critica textelor ?i la politic?, ?i dau azi un prestigiu de care cel ce clasific? ?tin?ele trebuie s? ?in? seama ,,

(Grigore C. Moisil)


NO?IUNI INTRODUCTIVE

?n general, pentru situa?iile care nece...