Scurt istoric al teoriei grafurilor

1. Scurt istoric al teoriei grafurilor

Originile teoriei grafurilor se gasesc in rezolvarea unor probleme de jocuri si amuzamente matematice, care au atras atentia unor matematicieni de seama cum ar fi: Euler, Hamilton, Cayley, Sylvester, Birkoff.

Data nasterii teoriei grafului este considerata a fi anul 1736, cand matematicianul Leonhard Euler a publicat un articol in care a clarificat problema celor 7 poduri si a prezentat metode pentru rezolvarea altor probleme de acelasi tip.

Cu 200 ani mai tarziu aparea la Leipzic prima carte de teorie a grafurilor al carei autor este matematicianul maghiar Denes Koreg. In amintirea contributiei lui Euler unele notiuni si tipuri de grafuri de care acesta s-a ocupat sunt denumite de catre Koreg lant eulerian, graf eulerian etc. Un alt matematician care s-a ocupat de aceleasi probleme ca si Euler, dar care si-a publicat rezolvarile cercetarilor sale in anul 1873 a fost Carl Hierholzer.

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

Fizicianul Kirchoff a studiat la mijlocul secolului al XIX-lea retele electrice cu metode care apartin astazi teoriei grafului contribuind la dezvoltarea acestei teorii.

Termenul graf a fost folosit pentru prima data in sensul sau actual in 1878 de matematicianul Sylvester. Teoria grafurilor are numeroase apeluri in chimie, contribuind in mare masura la rezolvarea problemelor de numarare a grafurilor apartinand unor clase speciale.

Teoria grafurilor este folosita in domenii variate: de la chimie la economie, de la studiul retelelor electrice la critica textelor de politica, devenind o disciplina majora.

2. Grafuri neorientate

Definitie : Se numeste graf neorientat o pereche de multimi G = (A,B) in care A este multimea nodurilor (este finita si nevida) si B este multimea relatiilor/muchiilor.

B = { (x,y) / x apartine lui A, y apartine lui A }

Definitie : O muchie a apartine de B este deci o submultime cu elemente {x,y} de varfuri distincte din A si o vom nota (x,y) - notatie muchie. Vom spune ca varfurile x si y sunt adiacente in G si ca ambele sunt incidente cu muchia (x,y).

Varfurile x si y se mai numesc si extremitatile muchiei (x,y).

Daca B1 si B2 sunt 2 muchii care au o extremitate comuna,ele vor fi numite de asemenea incidente.

A = {1,2,3,4,5}

B = {(1,2),(1,3),(2,3),(2,5)}

Exemplu:

-1 este adiacent cu 2 si 3

-1 si 2 sunt extremitatile (1,2)

- nodul 1 este incident cu (1,2)

- (5,2) si (2,3) sunt incidente

2.1. Gradul unui nod la grafurile neorientate

Gradul unui nod x , notat cu d(x), reprezinta numarul muchiilor care trec prin nodul x (incidente cu nodul x).

Exemplu:

- d(1)=2

Nodul care are gradul 1 se numeste nod terminal.

Nodul care are gradul 0 se numeste nod izolat.

Proprietati:

1. d + (x) + d - (x) = d(x)

2. Daca un graf are m muchii sau arce atunci: d( x1 )+d(x2 ) + ... + d(xn ) = 2m

2.2. Lanturi

Se numeste lant o succesiune de noduri x1 ... xk , cu proprietatea ca oricare doua noduri vecine (xi, xi+1 ) apartin de B.

x1, xk sunt extremitatile lantului

Lungimea lantului este egala cu numarul de muchii care il compun, k-1.

Daca nodurile din lant sunt distincte, atunci lantul este elementar, in caz contrar este neelementar.

Exemplu:

1,2,3,1,4 - Lant neelementar (lungime 4)

1,2,3,4 - Lant elementar (lungime 3)

1,2,3,1,2,5 - Lant neelementar (lungime 5)

1,2,3,5 - Nu este lant

2.3. Cicluri

Se numeste ciclu intr-un graf neorientat un lant x1, x2 ... xk cu proprietea ca x1=xk si oricare 2 muchii (xi, xi+1) sunt distincte.

Daca un ciclu are toate nodurile distincte 2 cate 2 cu exceptia capetelor, atunci el se numeste ciclu elementar, in caz contrar neelementar.

Exemplu:

1,2,3,4,1 - Ciclu elementar

2,3,4,1,2 - Ciclu elementar

1,2,3,4,2,3,1 - Nu este ciclu

1,2,3,4,2,5,1 - Ciclu neelementar