Problema comisului voiajor

I. Noţiuni fundamentale

Originile teoriei grafurilor se găsesc în rezolvarea unor probleme de jocuri şi amuzamente matematice,care au atras atenţia unor matematicieni de seamă cum ar fi: Euler, Hamilton, Cayley, Sylvester, Birkoff.

Data naşterii teoriei grafului este considerată a fi anul 1736, când matematicianul Leonhard Euler a publicat un articol în care a clarificat problema celor 7 poduri şi a prezentat metode pentru rezolvarea altor probleme de acelaşi tip.

Cu 200 ani mai târziu apărea la Leipzic prima carte de teorie a grafurilor al cărei autor este matematicianul maghiar Denes Koreg. În amintirea contribuţiei lui Euler unele noţiuni şi tipuri de grafuri de care acesta s-a ocupat sunt denumite de către Koreg lanţ eulerian ,graf eulerian,etc. Un alt matematician care s-a ocupat de aceleaşi probleme ca şi Euler, dar care şi-a publicat rezolvările cercetărilor sale în anul 1873 a fost Carl Hierholzer.

Alte izvoare ale teoriei grafurilor sunt:studiul reţelelor electrice, problema celor 4 culori, aplicaţiile teoriei grafurilor în chimie(iniţiate de Cayley), probleme hamiltoniene, grafuri planare.

Fizicianul Kirchoff a studiat la mijlocul secolului al XIX-lea reţele electrice cu metode care aparţin astăzi teoriei grafului contribuind la dezvoltarea acestei teorii.

Termenul graf a fost folosit pentru prima dată în sensul său actual în 1878 de matematicianul Sylvester. Teoria grafurilor este folosită în domenii variate: de la chimie la economie, de la studiul reţelelor electrice la critica textelor de politică, devenind o disciplină majoră.

În general, pentru situaţiile care necesită la rezolvare un oarecare efort mintal (şi un caz tipic este cel al celor din economie), se caută, în primul rând, o metodă de reprezentare a lor care să permită receptarea întregii probleme dintr-o privire (pe cât posibil) şi prin care să se evidenţieze cât mai clar toate aspectele acesteia.

În acest scop se folosesc imagini grafice gen diagrame, schiţe, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate în special pentru vizualizarea sistemelor şi situaţiilor complexe. În general, reprezentăm componentele acestora prin puncte în plan iar relaţiile (legăturile, dependenţele, influenţele etc) dintre componente prin arce de curbă cu extremităţile în punctele corespunzătoare. Între două puncte pot exista unul sau mai multe segmente (în funcţie de câte relaţii dintre acestea, care ne interesează, există) iar segmentelor li se pot asocia sau nu orientări (după cum se influenţează cele două componente între ele), numere care să exprime intensitatea relaţiilor dintre componente etc.

Este evident, totuşi, ca această metodă are limite, atât din punct de vedere uman (prea multe puncte şi segmente vor face desenul atât de complicat încât se va pierde chiar scopul pentru care a fost creat – claritatea şi simplitatea reprezentării, aceasta devenind neinteligibilă) cât şi din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).

Din acest motiv, se impune atât o definiţie riguroasă cât şi alte modalităţi de reprezentare a acestora, adecvate în general rezolvărilor matematice.

Definiţia 1 Se numeşte multigraf un triplet G = (X, A, f) în care X şi A sunt două mulţimi iar f este o funcţie, definită pe produsul vectorial al lui X cu el însuşi (X2 = XX), care ia valori în mulţimea părţilor mulţimii A (notată P(A))

Mulţimea X se numeşte mulţimea nodurilor multigrafului şi elementele sale se numesc noduri (sau vârfuri) ale multigrafului, iar A reprezintă mulţimea relaţiilor (legăturilor) posibile între două noduri ale multigrafului.

Definiţia 2 Se numeşte graf orientat un multigraf în care mulţimea A are un singur element: A = {a}.

În acest caz mulţimea părţilor mulţimii A are doar două elemente: mulţimea vidă  şi întreaga mulţime A. Dacă unei perechi orientate (xi, xj) din X2 i se asociază prin funcţia f mulţimea A atunci spunem că există arc de la nodul xi la nodul xj iar perechea (xi,xj) se va numi arcul (xi,xj). Nodul xi se numeşte nod iniţial sau extremitate iniţială a arcului (xi,xj) iar nodul xj se numeşte nod final sau extremitate finală a arcului (xi,xj). Arcul (xi,xj) este incident spre interior vârfului xj şi incident spre exterior vârfului xi. Dacă pentru un arc nodul iniţial coincide cu nodul final atunci acesta se numeşte buclă. Nodurile xi şi xj se vor numi adiacente dacă există cel puţin unul din arcele (xi,xj) şi (xj,xi).