PROIECT MATEMATICĂ

GRAFURI

Realizat de: Martinaş Petruţa

Păduraru Elisa

Colegiul Naţional Calistrat Hogaş

Cuprins:

1.Scurt istoric 2.Definiţia grafului3.Graf ul parţial4.Subgraful5.Lanţ 6.Graful conex7.Graful complet8.Gradul unui graf9.Probleme

Scurt istoric

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.

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.

Definiţia grafului

Un grafic neorientat (G) este o pereche de forma X,U.

Unde: X- o multime de numere

U- o multime formata din perechi neordonate de elemente distincte din X

Multimea X se numeste multimea varfurilor (nodurilor) lui G

Multimea U se numeste multimea muchiilor lui G

Reprezentare vizuală a grafurilor:

Fiecărui vârf din graf îi corespunde unpunct în plan care are asociat numărul vârfului.Pentru o mai mare lizibilitate, un vârf se reprezintă ca un cerc sau pătrat în interiorul căruia se specifică numărul vârfului.

Dacă graful este neorientat, vom reprezenta fiecare muchie ca o linie (dreaptă sau curbă), care uneşte cele două extremități ale muchiei.

Dacă graful este orientat, vom reprezenta fiecare arc ca o săgeată (dreaptă sau curbă) dinspre

extremitatea iniţială către extremitatea finală a arcului.

Graful parţial

Definitie: Fie G=(X,U). Un graf partial al lui G, este un graf G1=(X,V), cu V Í U. Altfel spus, un graf partial G1 este chiar G, sau se obtine din G pastrând toate vârfurile si suprimând niste muchii.

Exemplu:

Pentru graful G=(X,U) de mai jos, construim alaturat graful partial obtinut prin eliminarea muchiilor ce trec prin vârful 4. Acesta este G1=(X,V), unde X=, iar V=(s-au eliminat muchiile u3 si u4 care trec prin nodul 4).

Subgraful

Definitie: Fie graful G=(X,U). Un subgraf al lui G, este un graf G1=(Y,T), unde Y Ì X si T Ì U, iar V va contine numai muchiile care au ambele extremitati în Y. Altfel spus, un subgraf G1 se obtine din G eliminând niste vârfuri si pastrând doar acele muchii care au ambele extremitati în multimea vârfurilor ramase.

Exemplu:

Pentru graful G=(X,U) din figura 3.a, construim subgraful obtinut prin eliminarea vârfurilor 1 si 6 (figura 4). Acesta este G1=(Y,T), unde Y=, iar T= (s-au eliminat nodurile 1 si 6, precum si muchiile u1 si u5 care trec prin aceste noduri).

LanţSe numeşte lanţ într-un graf neorientat, o secvenţă de vârfuri , cu

proprietatea că oricare două vârfuri consecutive din secvenţă sunt adiacente.

Un lanţ este elementar dacă el nu conţine de mai multe ori acelaşi vârf.

Un lanţ este simplu dacă el nu conţine de mai multe ori aceeaşi muchie.

Se numeşte ciclu un lanţ simplu pentru care extremitatea iniţială coincide cu extremitatea finală.

Ciclul se numeşte elementar dacă nu conţine de mai multe ori acelaşi vârf (exceptând extremităţile sale).

Se numeşte lungimea unui lanţ numărul de muchii conţinute.

Un lanţ/drum/ciclu/circuit elementar se numeşte hamiltonian dacă el trece prin toate vârfurile grafului.

Un lanţ/drum/ciclu/circuit elementar se numeşte eulerian dacă el trece prin fiecare muchie/arc a/al grafului o singură dată.

Graful conex

Un graf este conex daca este format dintr-un singur nod sau daca intre oricare doua noduri ale sale exista cel putin un lant.

Aplicand algoritmul de parcurgere in latime a unui graf putem stabili daca un graf este conex sau nu astfel:daca in urma parcurgerii vor fi vizitate toate nodurile grafului atunci graful este conex, in caz contrar nu este conex.

Pentru grafuri neorientate:

Pentru grafuri orientate:

Graful complet

Un graf este complet daca oricare doua varfuri distince sunt adiacente.

Proprietăţi:

1. Un graf neorientat cu n noduri are n(n-1)/2 muchii. 2. Exista un singur graf complet neorientat cu n noduri. 3. Exista mai multe grafuri orientate complete cu n noduri.

Gradul unui graf

Gradul unui vârf reprezintă numărul muchiilor incidente cu vârful respectiv.

Fie un graf neorientat. Se numeşte gradal unui vârf x numărul de muchii incidente cu vârful respectiv. Gradul vârfului x se notează d(x).Se numeşte vârf izolat un vârf care are grad 0.Se numeşte vârf terminal un vârf cu gradul 1.

Fie un graf orientat şi xun vârf din graf.Gradul exterioral vârfului x se notează : d+(x) şi este egal cu numărul de arce care au ca extremitate iniţială pe x.

Gradul interior al vârfului x se notează: d-(x) şi este egal cu numărul de arce care au ca extremitate finală pe x.

Probleme

1. Se considera graful G=(X,U) din desenul alaturat. Sa se scrie multimile X si U.

x={1,2,3,4,5,6}

U={ [1,2], [2,3], [3,5], [2,4], [4,6], [6,5] }

2. Se considera grafurile G=(X,U) reprezentate in desenul urmator. a. Sa se scrie pentru fiecare graf multimea X a varfurilor si multimea U a

muchiilor. b. Sa se scrie pentru fiecare graf perechile de varfuri adiacente si perechile

de varfuri neadiacente.

X= { 1,2,3,4,5,6 }U={ [1,2], [1,3], [3,6], [6,5], [5,4], [2,5], [2,4], [2,6] }

X= { 1,2,3,4,5,6 }U= { [1,2], [2,3], [3,5], [5,6], [2,6], [4,6], 1,4] }

X= { a,b,c,d }

U= { [a,b], [b,c], [a,c], [c,d] }